%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% AMSLaTeX file for the paper                                        %
%                                                                    %
% Equivalent Conditions for Regularity\\(Extended Abstract)          %
%                                                                    %
% by Y. Kohayakawa, V. R\"odl, and J. Skokan                         %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Saturday 20 Nov 1999 06:12:46pm EDT yoshi@jaca>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{llncs}
%\usepackage{amsmath,amsthm,amssymb}
\usepackage{amsmath,amssymb}
\newcommand{\BM}[1]{\mbox{\boldmath $#1$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ykcomm#1{\textsf{[#1]}}
\def\Triad{\mathop{\rm Triad}\nolimits}
\let\:=\colon
\let\epsilon=\varepsilon
\def\veps{\vec{\epsilon}}
\def\vlambda{\vec{\lambda}}
\def\ycal#1{\mathcal{#1}}
\def\ind{\mathop{\rm ind}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\tildeex{\widetilde\ex}
\def\Exp{\mathop{\rm Exp}\nolimits}
\def\Prob{\mathop{\rm Prob}\nolimits}
\def\Vol{\mathop{\rm Vol}\nolimits}
\def\disc{\mathop{\rm disc}\nolimits}
\def\dev{\mathop{\rm dev}\nolimits}
\def\Aut{\mathop{\rm Aut}\nolimits}
\def\({\left(}
\def\){\right)}
\def\|{|\!|}
\def\<{\langle}
\def\>{\rangle}
\def\cK{\mathcal K}
\def\cF{\mathcal F}
\def\cE{\mathcal E}
\def\bcE{\mbox{\boldmath $\mathcal E$}}
\def\scriptbcE{\kern.1em\lower.05ex\hbox{\scriptsize\boldmath$\mathcal E$}}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cP{\mathcal P}
\def\cY{\mathcal Y}
\def\cS{\mathcal S}
% \def\bd{\begin{definition}}
% \def\ed{\end{definition}}
% \def\bt{\begin{theorem}}
% \def\et{\end{theorem}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{_theorem}{Theorem}%[section]
\newtheorem{_lemma}[_theorem]{Lemma}
\newtheorem{_proposition}[_theorem]{Proposition}
\newtheorem{_corollary}[_theorem]{Corollary}
\newtheorem{_conjecture}[_theorem]{Conjecture}
\newtheorem{_claim}[_theorem]{Claim}
\newtheorem{_definition}[_theorem]{Definition}
\newtheorem{fact}[_theorem]{Fact}

%\theoremstyle{definition}
%\newtheorem{definition}[theorem]{Definition}
%{\theorembodyfont{\slshape}\newtheorem{definition}[theorem]{Definition}}
% \newtheoremstyle{definition}% name
%   {4pt}%      Space above
%   {4pt}%      Space below
%   {\slshape}%         Body font
%   {}%         Indent amount (empty = no indent, \parindent = para indent)
%   {\bfseries}% Thm head font
%   {.}%        Punctuation after thm head
%   {.5em}%     Space after thm head: " " = normal interword space;
%         %       \newline = linebreak
%   {}%         Thm head spec (can be left empty, meaning `normal')
%\theoremstyle{definition}
%\newtheorem{definition}[theorem]{Definition}
%\theoremstyle{remark}
% \newtheorem*{Note}{Note}
% \newtheorem*{remark}{Remark}
% \newtheorem*{Constants}{Constants}
% \newtheorem{Remark}[theorem]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{Equivalent Conditions for Regularity\\(Extended Abstract)}
\titlerunning{Conditions for Regularity}
\author{%
Y. Kohayakawa\inst{1}\thanks{Partially supported
    by FAPESP (Proc.~96/04505--2), by CNPq (Proc.~300334/93--1), and
    by MCT/FINEP (PRONEX project~107/97).}\and 
V. R\"odl\inst{2}
\and 
J. Skokan\inst{2}
}
\institute{%
Instituto de Matem\'atica e Estat\'\i stica,  
Universidade de S\~ao Paulo,\\
Rua do Mat\~ao 1010, 
05508--900 S\~ao Paulo, Brazil\\
\email{yoshi@ime.usp.br}
\and  
Department of Mathematics and Computer Science,\\ 
Emory University, Atlanta, GA, 30322, USA\\
\email{\{rodl,jozef\}@mathcs.emory.edu}%
}
\authorrunning{Y. Kohayakawa, V. R\"odl, J. Skokan}
% \email{yoshi@ime.usp.br}
% \author[V. R\"odl]{Vojt\v ech R\"{o}dl}
% \institute{Emory University, Atlanta, GA, 30322, USA}
% \email{rodl@mathcs.emory.edu}
% \author[J. Skokan]{Jozef Skokan}
% \institute{Emory University, Atlanta, GA, 30322, USA}
% \email{jozef@mathcs.emory.edu}
% \date{\today}

\maketitle 

\begin{abstract}
  Haviland and Thomason and Chung and Graham were the first to
  investigate systematically some properties of quasi-random
  hypergraphs.  In particular, in a series of articles, Chung and
  Graham considered several quite disparate properties of random-like
  hypergraphs of density $1/2$ and proved that they are in fact
  equivalent.  The central concept in their work turned out to be the
  so called \textit{deviation} of a hypergraph.  Chung and Graham proved that 
  having small deviation is equivalent to a variety of other
  properties that describe quasi-randomness.  In this note, we
  consider the concept of \textit{discrepancy} for $k$-uniform
  hypergraphs with an arbitrary constant density~$d$ ($0<d<1$) and
  prove that the condition of having asymptotically vanishing
  discrepancy is equivalent to several other quasi-random properties
  of~$\cH$, similar to the ones introduced by Chung and Graham.  In
  particular, we give a proof of the fact that having the correct `spectrum'
  of the 
  $s$-vertex subhypergraphs is equivalent to quasi-randomness for
  any~$s\geq2k$.  Our work can be viewed as an extension of the
  results of Chung and Graham to the case of an arbitrary constant
  valued density.  Our methods, however, are based on different ideas.
\end{abstract}

\section{Introduction and the main result}
\label{sec:intro}

The usefulness of random structures in theoretical computer science
and in discrete mathematics is well known.  An important, closely
related question is the following: which, if any, of the almost sure
properties of such structures suffice for a deterministic object to
have to be as useful or relevant?

Our main concern here is to address the above question in the context
of hypergraphs.  
%
We shall continue the study of quasi-random hypergraphs along the lines
initiated by Haviland and Thomason~\cite{haviland89:_pseud,haviland92} and
especially by Chung~\cite{chung90-classes}, and Chung and
Graham~\cite{chung90,chung91-set}.  One of the central concepts of hypergraph
quasi-randomness, the so called \textit{hypergrpahs discrepancy}, was
investigated by Babai, Nisan, and Szegedy~\cite{babai92:_multip}, who found a
connection between communication complexity and hypergraph discrepancy.
%
This connection was further studied by
Chung and Tetali~\cite{chung93:_commun}.  Here, we carry out the
investigation very much along the lines of Chung and
Graham~\cite{chung90,chung91-set}, except that we focus on hypergraphs
of arbitrary constant density, making use of different techniques.
%This is a first step towards understanding the challenging case of
%vanishing density.

In the remainder of this introduction, we carefully discuss a result
of Chung and Graham~\cite{chung90} and state our main result,
Theorem~\ref{main} below.  

\subsection{The result of Chung and Graham}
\label{sec:chung_graham}
We need to start with some definitions.  For a set $V$ and an integer
$k\geq 2$, let $[V]^k$ denote the system of all $k$-element subsets of
$V$.  A~subset $\cG\subset[V]^k$ is called a \textit{$k$-uniform
  hypergraph}.  If $k=2$, we have a \textit{graph}.  We sometimes use
the notation~$\cG=(V(\cG),E(\cG))$.  If there is no danger of
confusion, we shall identify the hypergraphs with their edge sets.
Throughout this paper, the integer~$k$ is assumed to be a fixed
constant.

For any $l$-uniform hypergraph $\cG$ and $k\geq l$, let $\cK_k(\cG)$ be the
set of all $k$-element sets that span a clique $K^{(l)}_k$ on $k$ vertices.
We also denote by $K_k(2)$ the complete $k$-partite $k$-uniform hypergraph
whose every partite set contains precisely two vertices.  We refer to $K_k(2)$
as the \textit{generalized octahedron}, or, simply, the \textit{octahedron}.

We also consider a function $\mu_\cH\: [V]^k \rightarrow \{ -1, 1\}$
such that, for all~$e\in [V]^k$, we have
$$
\mu_\cH(e)=\left\{
\begin{array}{rl}
-1, &\qquad \mbox{if } e\in\cH\\
 1, &\qquad \mbox{if } e\not\in\cH.\\
\end{array}
\right.
$$
Let $[k] = \{1,2,\dots, k\}$, let $V^{2k}$ denote the set of all
$2k$-tuples $(v_1,v_2,\dots,v_{2k})$, where $v_i\in V$ ($1\leq i\leq 2k$), and
let $\Pi^{(k)}_\cH\:V^{2k}\rightarrow\{-1,1\}$ be given by
$$
\Pi^{(k)}_\cH(u_1,\dots, u_k, v_1,\dots, v_k)
 =\prod\nolimits_\epsilon%{\epsilon=(\epsilon_i)_{i=1}^k}
  \mu_\cH(\epsilon_1,\dots, \epsilon_k),
$$
where the product is over all vectors~$\epsilon=(\epsilon_i)_{i=1}^k$ with
$\epsilon_i\in\{u_i,v_i\}$ for all~$i$ and we understand~$\mu_{\cH}$ to be~$1$
on arguments with repeated entries.

Following Chung and Graham (see, e.g., \cite{chung91-set}), we define
the \textit{deviation~$\dev(\cH)$} of $\cH$ by
$$
\dev(\cH)
= \frac{1}{m^{2k}} \sum_{u_i,v_i \in V,\; i\in [k]}
  \Pi^{(k)}_\cH(u_1,\dots, u_k, v_1,\dots, v_k).
$$

For two hypergraphs $\cG$ and $\cH$, we denote by ${\cH\choose\cG}$
the set of all induced subhypergraphs of $\cH$ that are isomorphic to
$\cG$.  We also write ${\cH \choose \cG}^{\rm w}$ for the number of
\textit{weak} (i.e., not necessarily induced) subhypergraphs of~$\cH$
that are isomorphic to~$\cG$.
Furthermore, we need the notion of the \textit{link} of a vertex.

\begin{_definition}\label{def:link}
  Let $\cH$ be a $k$-uniform hypergraph and $x\in V(\cH)$.  We shall call the
  $(k-1)$-uniform hypergraph
  $$
  \cH(x) = \{e\setminus\{x\} \: e\in \cH,\; x\in e \}
  $$
  the \textsl{link} of the vertex $x$ in $\cH$.  For a subset $W\subset
  V(\cH)$, the \textsl{joint $W$-link} is
  $
  \cH(W)=\bigcap_{x\in W}\cH(x).
  $
  For simplicity, if $W=\{x_1,\dots, x_k\}$, we write $\cH(x_1,\dots,x_k)$.
\end{_definition} 

Observe that if $\cH$ is $k$-partite, then $\cH(x)$ is $(k-1)$-partite for
every $x\in V$.  Furthermore, if $k=2$, then $\cH(x)$ may be identified with
the ordinary graph neighbourhood of $x$.  Moreover, $\cH(x,x')$ may be thought
of as the `joint neighbourhood' of $x$ and $x'$.

In \cite{chung90}, Chung and Graham proved that if the density of an
$m$-vertex $k$-uniform hypergraph $\cH$ is $1/2$, i.e.,
$|\cH|=(1/2+o(1)){m\choose k}$, where $o(1)\rightarrow 0$ as $m\rightarrow
\infty$, then the following statements are equivalent:

\begin{description}
\item [(\BM{Q_1(s)})] for all $k$-uniform hypergraphs $\cG$ on
$s\geq2k$ vertices and automorphism group~$\Aut(G)$, 
$$
\left | {\cH \choose \cG}\right |
= (1+o(1)){m\choose s}2^{-{s\choose k}}\frac{s!}{|\Aut(\cG)|},
$$
\item [(\BM{Q_2})] for all $k$-uniform hypergraphs $\cG$ on $2k$
vertices and automorphism group $\Aut(G)$, we have
$$
\left | {\cH \choose \cG}\right |
= (1+o(1)){m\choose2k}2^{-{2k\choose k}}\frac{(2k)!}{|\Aut(G)|},
$$
\item [(\BM{Q_3})] $\dev(\cH)=o(1)$,
\item [(\BM{Q_4})] for almost all choices of vertices $x$, $y\in V$,
  the $(k-1)$-uniform hypergraph $\overline{\cH(x)\triangle\cH(y)}$,
  that is, the \textit{complement}
  $[V]^{k-1}\setminus(\cH(x)\triangle\cH(y))$ of the symmetric
  difference of~$\cH(x)$ and~$\cH(y)$, satisfies $Q_2$ with $k$
  replaced by $k-1$,
\item [(\BM{Q_5})] for $1\leq r\leq 2k-1$ and almost all $x$, $y\in V$,
%  \ykcomm{$r=2k-1$ required?  $1\leq r\leq2(k-1)$ not enough?}
$$
\left | {\cH(x,y) \choose K^{(k-1)}_r}%^{\rm w}
\right|
= (1+o(1)){m\choose r}2^{-{r\choose k-1}}.
$$
\end{description}
The equivalence of these properties is to be understood in the following
sense.  If we have two properties $\BM{P}=\BM{P}(o(1))$ and
$\BM{P^\prime}=\BM{P^\prime}(o(1))$, then ``$\BM{P} \Rightarrow
\BM{P^\prime}$'' means that for every $\epsilon >0$ there is a $\delta >0$ so
that any $k$-uniform hypergraph $\cH$ on $m$ vertices satisfying
$\BM{P}(\delta)$ must also satisfy $\BM{P^\prime}(\epsilon)$, provided
$m>M_0(\epsilon)$.

In~\cite{chung90} Chung and Graham stated that ``it would be profitable to
explore quasi-randomness extended to simulating random $k$-uniform hypergraphs
$G_p(n)$ for $p\neq 1/2$, or, more generally, for $p=p(n)$, especially along
the lines carried out so fruitfully by
Thomason~\cite{thomason87,thomason87:_random}.''  Our present aim is to
explore quasi-randomness from this point of view.  In this paper, we
concentrate on the case in which~$p$ is an arbitrary constant.  In certain
crucial parts, our methods are different from the ones of Chung and Graham.
Indeed, it seems to us that the fact that the density of $\cH$ is $1/2$ is
essential in certain proofs in~\cite{chung90} (especially those involving the
concept of deviation).

\subsection{Discrepancy and the subgraph counting formula}
\label{sec:discrepancy}
The following concept was proposed by Frankl and~R\"odl and later investigated 
by Chung~\cite{chung90-classes} and Chung and Graham
in~\cite{chung90,chung91-set}. 
For an $m$-vertex $k$-uniform hypergraph $\cH$ with vertex set $V$, we
define the \textit{density} $d(\cH)$ and the \textit{discrepancy}
$\disc_{1/2}(\cH)$ of $\cH$ by letting
$
d(\cH)=|\cH|{m \choose k}^{-1}
$
and
\begin{equation}\label{chung1}
\disc_{1/2}(\cH) = \frac{1}{m^k} \max_{\cG\subset [V]^{k-1}}
\left | |\cH\cap\cK_k(\cG)| - |\bar{\cH}\cap\cK_k(\cG)|  \right |,
\end{equation}
where the maximum is taken over all $(k-1)$-uniform hypergraphs $\cG$
with vertex set $V$, and~$\bar{\cH}$ is the
complement~$[V]^{k}\setminus\cH$ of~$\cH$.

To accommodate arbitrary densities, we extend the latter concept as
follows. 
\begin{_definition}\label{def1} Let $\cH$ be a $k$-uniform hypergraph with
  vertex set $V$ with~$|V|=m$.  We define the \textsl{discrepancy}
  $\disc(\cH)$ of $\cH$ as follows:
\begin{equation}\label{def1.1}
  \disc(\cH)=\frac{1}{m^k}\max_{\cG\subset
  [V]^{k-1}}\big||\cH\cap\cK_k(\cG)|-d(\cH)|\cK_k(\cG)|\big|, 
\end{equation}
where the maximum is taken over all $(k-1)$-uniform hypergraphs $\cG$ with
vertex set $V$.  
\end{_definition}

Observe that if $d(\cH)=1/2$, then $\disc(\cH)=(1/2)\disc_{1/2}(\cH)$, so both
notions are equivalent.  Following some initial considerations by Frankl and
R\"odl, Chung and Graham investigated the relation between discrepancy and
deviation.  In fact, Chung~\cite{chung90-classes} succeeded in proving the
following inequalities closely connecting these quantities:
\begin{enumerate}
\item[(\textit{i})] $\dev(\cH)< 4^k(\disc_{1/2}(\cH))^{1/2^k}$, 
\item[(\textit{ii})] $\disc_{1/2}(\cH)< (\dev(\cH))^{1/2^k}$. 
\end{enumerate}
For simplicity, we state the inequalities for the density $1/2$ case.
For the general case, see Section~5 of~\cite{chung90-classes}.

Before we proceed, we need to introduce a new concept.  If the vertex
set of a hypergraph is totally ordered, we say that we have an
\textit{ordered} hypergraph.  Given two ordered hypergraphs~$\cG_\leq$
and~$\cH_{\leq'}$, where~$\leq$ and~$\leq'$ denote the orderings on
the vertex sets of~$\cG=\cG_\leq$ and~$\cH=\cH_{\leq'}$, we say that a
function $f\:V(\cG)\to V(\cH)$ is an \textit{embedding of ordered
hypergraphs} if 
(\textit{i})~it is an injection, 
(\textit{ii})~it respects the orderings, i.e.,
$f(x)\leq'f(y)$ whenever $x\leq y$,
and 
(\textit{iii})~$f(g)\in\cH$ if and only if $g\in\cG$,
where $f(g)$ is the set formed by the images of all the vertices in $g$. 
Furthermore, if $\cG=\cG_\leq$ and~$\cH=\cH_{\leq'}$, we write
$
{\cH\choose\cG}_{\rm ord}%_{\leq'}={\cH_{\leq'} \choose \cG_\leq}_{\leq'}
                    %={\cH_{\leq'}\choose\cG_\leq}
$
for the number of such embeddings.

As our main result, we shall prove the following extension of Chung
and Graham's result.

\begin{_theorem}\label{main}
  Let $\cH=(V,E)$ be a $k$-uniform hypergraph of density~$0<d<1$.  Then the
  following statements are equivalent:
\begin{description}
\item [\BM{(P_1)}] $\disc(\cH)=o(1)$,
\item [\BM{(P_2)}] $\disc(\cH(x))=o(1)$ for all but $o(m)$ vertices $x\in V$
  and $\disc(\cH(x,y))=o(1)$ for all but $o(m^2)$ pairs $x$, $y\in V$,
\item [\BM{(P_3)}] $\disc(\cH(x,y))=o(1)$ for all but $o(m^2)$ pairs $x$, $y\in
  V$,
\item [\BM{(P_4)}] the number of octahedra~$K_k(2)$ in $\cH$ is asymptotically
  minimized among all $k$-uniform hypergraphs of density~$d$; indeed,
  $$
  \left|{\cH\choose K_k(2)}^{\rm w}\right|
    =(1+o(1))\frac{m^{2k}}{2^kk!}d^{2^k},
  $$
\item [\BM{(P_5)}] for any $s\geq 2k$ and any $k$-uniform
  hypergraph~$\cG$ on $s$ vertices with $e(\cG)$ edges and
  automorphism group $\Aut(\cG)$, 
  $$
  \left | {\cH \choose \cG}\right | =(1+o(1)){m\choose s}
  d^{e(\cG)}(1-d)^{{s\choose k} - e(\cG)}\frac{s!}{|\Aut(\cG)|},
  $$
\item [\BM{(P_5')}] for any ordering~$\cH_\leq$ of~$\cH$ and for any
  fixed integer $s\geq 2k$, any ordered $k$-uniform
  hypergraph~$\cG_\leq$ on $s$ vertices with $e(\cG)$ edges is such that 
  $$
  \left|{\cH\choose\cG}_{\rm ord}\right| =(1+o(1)){m\choose s}
  d^{e(\cG)}(1-d)^{{s\choose k} - e(\cG)},
  $$
\item [\BM{(P_6)}] for all $k$-uniform hypergraphs $\cG$ on $2k$ vertices with
  $e(\cG)$ edges and automorphism group $\Aut(\cG)$,
  $$
  \left | {\cH \choose \cG}\right | =(1+o(1)){m\choose 2k}
  d^{e(\cG)}(1-d)^{{2k\choose k} - e(\cG)}\frac{(2k)!}{|\Aut(\cG)|}.
  $$
\item [\BM{(P_6')}] for any ordering~$\cH_\leq$ of~$\cH$, any ordered
  $k$-uniform hypergraph~$\cG_\leq$ on $2k$ vertices with $e(\cG)$
  edges is such that
  $$
  \left|{\cH\choose\cG}_{\rm ord}\right|=(1+o(1)){m\choose 2k}
  d^{e(\cG)}(1-d)^{{2k\choose k}-e(\cG)}.
  $$
\end{description}
\end{_theorem}

Some of the implications in Theorem~\ref{main} are fairly easy or are
by now quite standard.  There are, however, two implications that
appear to be more difficult.

The proof of Chung and Graham that~$\dev_{1/2}(\cH)=o(1)$ implies~$P_5$ (the
`subgraph counting formula') is based on an approach that has its roots in a
seminal paper of Wilson~\cite{wilson72:_cyclot}.  This beautiful proof seems
to make non-trivial use of the fact that~$d(\cH)=1/2$.  Our proof of the
implication that small discrepancy implies the subgraph counting formula
($P_1\Rightarrow P_5'$) is based on a different technique, which works well in
the arbitrary constant density case (see Section~\ref{sec:count}).

Our second contribution, which is somewhat more technical in nature, lies in a
novel approach for the proof of the implication $P_2\Rightarrow P_1$.  Our
proof is based on a variant of the Regularity Lemma of
Szemer\'edi~\cite{szemeredi76} for hypergraphs~\cite{frankl92} (see
Section~\ref{sec:weak_regularity}).

\section{Main steps in the proof of Theorem~\ref{main}}
\label{sec:mainsteps}

\subsection{The first part}
\label{sec:first}
The first part of the proof of Theorem~\ref{main} consists of proving that
properties $P_1,\dots,P_4$ are mutually equivalent.  As it turns out, the
proof becomes more transparent if we restrict ourselves to $k$-partite
hypergraphs.  In the next paragraph, we introduce some definitions that will
allow us to state the $k$-partite version of $P_1,\dots,P_4$ (see
Theorem~\ref{main2}).  We close this section introducing the main tool in the
proof of Theorem~\ref{main2}, namely, we state a version of the Regularity
Lemma for hypergraphs (see Lemma~\ref{prop1}).

\subsubsection{Definitions for partite hypergraphs.}
For simplicity, we first introduce the term \textit{cylinder} to mean partite
hypergraphs.

\begin{_definition} Let $k\geq l\geq 2$ be two integers.  We shall
  refer to any $k$-partite $l$-uniform hypergraph
  $\cH=(V_1\cup\dots\cup V_k,E)$ as a \textsl{$k$-partite
  $l$-cylinder} or \textsl{$(k,l)$-cylinder}.  If $l=k-1$, we shall often
  write $\cH_i$ for the subhypergraph of~$\cH$ induced on $\bigcup_{j\neq
  i}V_j$.  Clearly, $\cH=\bigcup_{i=1}^k\cH_i$.  We shall also denote by
  $K^{(l)}_k(V_1,\dots, V_k)$ the complete $(k,l)$-cylinder with
  vertex partition $V_1\cup\dots\cup V_k$.
\end{_definition}

\begin{_definition} For a $(k,l)$-cylinder $\cH$, we shall denote by
  $\cK_j(\cH)$, $l\leq j\leq k$, the $(k,j)$-cylinder whose edges are
  precisely those $j$-element subsets of $V(\cH)$ that span cliques of order
  $j$ in $\cH$.
\end{_definition}

%Clearly, the quantity $|\cK_j(\cH)|$ counts the total number of cliques of
%order $j$ in~$\cH$.  In the case in which~$l=1$, the
%$(k,j)$-cylinder~$\cK_j(\cH)$ is the complete $k$-partite $j$-uniform
%hypergraph on the vertex set of~$\cH$.

When we deal with cylinders, we have to measure density according to their
natural vertex partitions.

\begin{_definition} Let $\cH$ be a $(k,k)$-cylinder with $k$-partition
  $V=V_1\cup\dots\cup V_k$.  We define the \textsl{$k$-partite density} or
  simply the \textsl{density} $d(\cH)$ of $\cH$ by
$$
  d(\cH)=\frac{|\cH|}{|V_1|\dots|V_k|}.
$$
\end{_definition}

To be precise, we should have a distinguished piece of notation for the notion
of $k$-partite density.  However, the context will always make clear which
notion we mean when we talk about the density of a $(k,k)$-cylinder.

We should also be careful when we talk about the discrepancy of a cylinder. 

\begin{_definition}\label{def1prime} Let $\cH$ be a $(k,k)$-cylinder
  with vertex set $V=V_1\cup\dots\cup V_k$.  We define the
  \textsl{discrepancy} $\disc(\cH)$ of $\cH$ as follows:
\begin{equation}\label{def1.1prime}
\disc(\cH)
=\frac{1}{|V_1|\dots|V_k|} \max_\cG
\big| |\cH\cap\cK_k(\cG)| - d(\cH)| \cK_k(\cG)|  \big|,
\end{equation}
where the maximum is taken over all $(k,k-1)$-cylinders $\cG$ with
vertex set $V=V_1\cup\dots\cup V_k$.
\end{_definition}

We now introduce a simple but important concept concerning the ``regularity''
of a $(k,k)$-cylinder.

\begin{_definition}\label{reg} Let $\cH$ be a $(k,k)$-cylinder with $k$-partition
$V=V_1\cup\dots\cup V_k$ and let $\delta<\alpha$ be two positive real numbers.
We say that $\cH$ is \textsl{$(\alpha, \delta)$-regular} if the following
condition is satisfied: if $\cG$ is any $(k,k-1)$-cylinder such that
$|\cK_k(\cG)|\geq \delta |V_1|\dots|V_k|$, then
%\begin{equation}\label{reg1}
%\end{equation} 
\begin{equation*}%\label{reg2}
  (\alpha - \delta)|\cK_k(\cG)|\leq |\cH\cap \cK_k(\cG)|
    \leq (\alpha + \delta) |\cK_k(\cG)|.
\end{equation*}
\end{_definition}

%The following simple facts hold.

\begin{_lemma}\label{fact:fact1}
  Let $\cH$ be an $(\alpha, \delta)$-regular $(k,k)$-cylinder.  Then
  $\disc(\cH)\leq 2\delta$. 
\end{_lemma}

\begin{_lemma}\label{fact:fact2}
  Suppose $\cH$ is a $(k,k)$-cylinder with $k$-partition $V=V_1\cup\dots\cup
  V_k$.  Put $\alpha=d(\cH)$ and assume that $\disc(\cH)\leq\delta$.
  Then $\cH$ is $(\alpha,\delta^{1/2})$-regular.
\end{_lemma}

\subsubsection{The $k$-partite result.}
\label{sec:reduction}
Suppose~$\cH$ is a $k$-uniform hypergraph and let~$\cH'$ be a
`typical' $k$-partite spanning subhypergraph of~$\cH$.  In this
section, we relate the discrepancies of~$\cH$ and~$\cH'$.

\begin{_definition} Let $\cH=(V,E)$ be a $k$-uniform hypergraph with $m$
  vertices and let $\cP= (V_i)_1^k$ be a partition of~$V$.  We denote by
  $\cH_\cP$ the $(k,k)$-cylinder consisting of the edges $h\in\cH$ satisfying
  $|h\cap V_i|=1$ for all $1\leq i\leq k$.
\end{_definition} 

The following lemma holds.

\begin{_lemma}\label{prop01}
For any partition $\cP=(V_i)_1^k$ of $V$, we have
\begin{enumerate}
\item[{\rm(\textit{i})}]
  $\disc(\cH)\geq|d(\cH_\cP)-d(\cH)||V_1|\dots|V_k|/m^k$, 
\item[{\rm(\textit{ii})}] $\disc(\cH_\cP)\leq 2\disc(\cH)m^k/|V_1|\dots|V_k|$.   
\end{enumerate}
\end{_lemma}

An immediate consequence of the previous lemma is the following.

\begin{_lemma}\label{claim01}
If $ \disc(\cH)=o(1)$, then $\disc (\cH_\cP)= o(1)$ for $(1 - o(1))k^m$
partitions $\cP=(V_i)_1^k$ of $V$.
\end{_lemma}

With some more effort, one may prove a converse to Lemma~\ref{claim01}.

\begin{_lemma}\label{claim02}
  Suppose there exists a real number $\gamma>0$ such that $\disc(\cH_\cP)=
  o(1)$ for $\gamma k^m$ partitions $\cP=(V_i)_1^k$ of $V$.  Then $
  \disc(\cH)=o(1)$.
\end{_lemma}

We now state the $k$-partite version of a part of our main result,
Theorem~\ref{main}. 

\begin{_theorem}\label{main2}
  Suppose $V=V_1\cup\dots\cup V_k$, $|V_1|=\dots=|V_k|=n$, and let $\cH=(V,E)$
  be a $(k,k)$-cylinder with $|\cH|=dn^k$.  Then the following four conditions
  are equivalent:
\begin{description}
\item [\BM{(C_1)}] $\cH$ is $(d,o(1))$-regular;
\item [\BM{(C_2)}] $\cH(x)$ is $(d,o(1))$-regular for all but $o(n)$
  vertices $x\in V_k$ and $\cH(x, y)$ is $(d^2,o(1))$-regular for all
  but $o(n^2)$ pairs $x$, $y\in V_k$;
\item [\BM{(C_3)}] $\cH(x, y)$ is $(d^2,o(1))$-regular for all but $o(n^2)$
  pairs $x$, $y\in V_k$;
\item [\BM{(C_4)}] the number of copies of~$K_k(2)$ in $\cH$ is
  asymptotically minimized among all such $(k,k)$-cylinders of density~$d$,
  and equals $(1+o(1))n^{2k}d^{2^k}/2^k$.
\end{description}
\end{_theorem}
\begin{remark}
  The condition $|V_1|=\dots=|V_k|=n$ in the result above has the sole purpose
  of making the statement more transparent.  The immediate generalization of
  Theorem~\ref{main2} for $V_1,\dots,V_k$ of arbitrary sizes holds.
\end{remark}

\begin{remark}
  The fact that the minimal number of octahedra in a $(k,k)$-cylinder is
  asymptotically $(1+o(1))n^{2k}d^{2^k}/2^k$ is not difficult to deduce from a
  standard application of the Cauchy--Schwarz inequality for counting
  ``cherries'' (paths of length~$2$) in bipartite graphs.
\end{remark}

We leave the derivation of the equivalence of
properties~$P_1,\dots,P_4$ from Theorem~\ref{main2} to the full paper.

\subsubsection{A regularity lemma.}
\label{sec:weak_regularity}
The hardest part in the proof of Theorem~\ref{main2} is the implication
$C_2\Rightarrow C_1$.  In this paragraph, we discuss the main tool used in the
proof of this implication.  It turns out that, in what follows, the notation
is simplified if we consider $(k+1)$-partite hypergraphs.

Throughout this paragraph, we let $\cG$ be a fixed $(k+1,k)$-cylinder
with vertex set $V(\cG)=V_1\cup\dots\cup V_{k+1}$.  Recall that
$\cG=\bigcup_{i=1}^{k+1}\cG_i$, where $\cG_i$ is the corresponding
$(k,k)$-cylinder induced on $\bigcup_{j\neq i} V_j$.  In this section,
we shall focus on ``regularizing'' the $(k,k)$-cylinders
$\cG_1,\dots,\cG_k$, ignoring $\cG_{k+1}$. Alternatively, we may
assume that $\cG_{k+1}=\emptyset$.

\begin{_definition} Let $\cF=\bigcup_{i=1}^k\cF_i$ be a $(k,k-1)$-cylinder with
  vertex set $V_1\cup\dots\cup V_k$. For a~vertex $v\in V_{k+1}$, we define
  the \textsl{$\cG$-link $\cG_{\cF}(x)$ of $x$ with respect to $\cF$} to be
  the $(k,k-1)$-cylinder
$
\cG_{\cF}(x)=\cG(x)\cap\cF.
$ 
\end{_definition}

\begin{_definition}\label{def:weak-regularity}
  Let $W\subset V_{k+1}$ and let $\cF=\bigcup_{i=1}^k\cF_i$ be as above.  We
  shall say that the pair $(\cF, W)$ is \textsl{$(\epsilon,d)$-regular} if
\begin{equation}\label{weaka}
\left | \frac{|\cK_k(\cG_{\cF}(x))|}{|\cK_k(\cF)|}   - d \right | <
\epsilon
\end{equation}
for all but at most $\epsilon |W|$ vertices $x\in W$, and
\begin{equation}\label{weakb}
\left | \frac{|\cK_k(\cG_{\cF}(x))\cap
\cK_k(\cG_{\cF}(y))|}{|\cK_k(\cF)|}   - d^2 \right |
< \epsilon
\end{equation}
for all but at most $\epsilon |W|^2$ pairs $x$, $y\in W$.  
\end{_definition}

\begin{_definition}\label{def:reg1} Let $t$ be a positive integer and let
  $V_{k+1}=W_1\cup\dots\cup W_t$ be an arbitrary partition of~$V_{k+1}$.  For
  every $i\in [k]$, consider a $t$-partition
  $P_i^{(t)}=\{\cE^{(i)}_1,\dots,\cE^{(i)}_t\}$ of $V_1\times\dots\times
  V_{i-1}\times V_{i+1}\times\dots\times V_k=\bigcup_{\alpha=1}^t
  \cE^{(i)}_\alpha$.  Put $P^{(t)}=(P_1^{(t)},\dots,P_k^{(t)})$.  We shall
  write $\bcE(P^{(t)})$ for the collection of all $(k,k-1)$-cylinders $\cE$ of
  the form~$\cE^{(1)}_{\alpha_1}\cup\dots\cup\cE^{(k)}_{\alpha_k}$, where
  $\cE^{(i)}_{\alpha_i}\in P^{(t)}_i$ for all~$1\leq i\leq k$.
\end{_definition}

Clearly, with the notation as above, we have $|\bcE(P^{(t)})|=t^k$.
Moreover, observe that each of the $t^{k+1}$ pairs $(\cE,W_i)$,
where~$\cE\in\bcE(P^{(t)})$ and~$1\leq i\leq t$, may be classified as
$\epsilon$-regular or $\epsilon$-irregular (i.e., not
$\epsilon$-regular), according to
Definition~\ref{def:weak-regularity}.  Also, notice that
each~$v=(v_1,\dots,v_{k+1})\in V_1\times\dots\times V_{k+1}$ is
`covered' by exactly one such pair, that is, $v\in\cK_k(\cE)\times
W_i$ for a unique pair~$(\cE,W_i)$.

\begin{_definition} 
  Let~$P^{(t)}=\big(P_i^{(t)}\big)_1^k$ and~$\big(W_i\big)_1^t$ be as in
  Definition~\ref{def:reg1}.  We shall say that the system of partitions
  $
  \big\{P_1^{(t)},\dots,P_k^{(t)},\{W_1,\dots,W_t\}\big\}
  $
  is \textsl{$\epsilon$-regular} if the number of $(k+1)$-tuples
  $(v_1,\dots,v_{k+1})\in V_1\times\dots\times V_{k+1}$ that are \textsl{not}
  covered by the family of $\epsilon$-regular pairs $(\cE,W_i)$
  with~$\cE\in\bcE(P^{(t)})$ and~$1\leq i\leq t$ is at most
  $\epsilon|V_1|\dots|V_{k+1}|$.
\end{_definition}

The main tool in the proof of $C_2\Rightarrow C_1$ is the following result
(see~\cite{KRoS} for the details).

\begin{_lemma}\label{prop1}
  For every $\epsilon>0$ and $t_0\geq1$, there exist integers $n_0$ and $T_0$
  such that every $(k+1,k)$-cylinder $\cG=\bigcup_{i=1}^{k+1}\cG_i$ with
  vertex set $V_1\cup\dots\cup V_{k+1}$, where $|V_i|\geq n_0$ for all $1\leq
  i\leq k+1$, admits an $\epsilon$-regular system of partitions
  $\{P_1^{(t)},\dots,P_k^{(t)},\{W_1,\dots,W_t\}\}$ with $t_0<t<T_0$.
\end{_lemma}

\subsection{The subgraph counting formula}
\label{sec:count}
In this section, we shall state the main result that may be used to
prove the implication $P_1\Rightarrow P_5'$.  To this end, we need to
introduce some notation.  Throughout this section, $s\geq2k$ is some
fixed integer.

If~$\cH$ and~$\cG$ are, respectively, $k$-uniform and $\ell$-uniform
($k\geq\ell$), then we say that $\cH$ is \textit{supported} on~$\cG$ if
$\cH\subset\cK_k(\cG)$.

Suppose we have pairwise disjoint sets~$W_1,\dots,W_s$, with~$|W_i|=n$ for
all~$i$.  Suppose further that we have a sequence~$\cG^{(2)},\dots,\cG^{(k)}$
of $s$-partite cylinders on~$W_1\cup\dots\cup W_s$, with~$\cG^{(i)}$ an
$(s,i)$-cylinder and, moreover, such that~$\cG^{(i)}$ is supported
on~$\cG^{(i-1)}$ for all $3\leq i\leq k$.  Suppose also that, for all $2\leq
i\leq k$ and for all $1\leq j_1<\dots<j_i\leq s$, the $(i,i)$-cylinder $
\cG[j_1,\dots,j_i]=\cG^{(i)}[W_{j_1}\cup\dots\cup W_{j_i}] $ is
\textit{$(\gamma_i,\delta)$-regular with respect
  to~$\cG^{(i-1)}[j_1,\dots,j_i]=\cG^{(i-1)}[W_{j_1}\cup\dots\cup W_{j_i}]$},
that is, whenever $\cG\subset\cG^{(i-1)}[j_1,\dots,j_i]$ is such that
$|\cK_i(\cG)|\geq\delta|\cK_i(\cG^{(i-1)}[j_1,\dots,j_i])|$, we have
$$
(\gamma_i-\delta)|\cK_i(\cG)|\leq\left|\cG[j_1,\dots,j_i]\cap\cK_i(\cG)\right|
  \leq(\gamma_i+\delta)|\cK_i(\cG)|.
$$
%
Finally, let us say that a copy of $K_s^{(k)}$ in~$W_1\cup\dots\cup W_s$ is
\textit{transversal} if $|V(K_s^{(k)})\cap W_i|=1$ for all $1\leq i\leq s$.

Our main result concerning counting subhypergraphs is then the
following.

\begin{_theorem}\label{thm:complex}
  For any~$\epsilon>0$ and any~$\gamma_2,\dots,\gamma_k>0$, there is
  $\delta_0>0$ such that if $\delta<\delta_0$, then the number of
  transversal $K_s^{(k)}$ in $\cG^{(k)}$ is
  $(1+O(\epsilon))\gamma_k^{{s\choose
      k}}\dots\gamma_2^{{s\choose2}}n^s$.
\end{_theorem}

Theorem~\ref{thm:complex} above is an instance of certain counting lemmas
developed by R\"odl and Skokan for such \textit{complexes}~$\mbox{\boldmath
  $\mathcal G$}=\(\cG^{(i)}\)_{2\leq i\leq k}$ (see, e.g.,
\cite{roedl99:_unifor}).

\section{Concluding remarks}
\label{sec:concluding}
We hope that the discussion above on our proof approach for
Theorem~\ref{main} gives some idea about our methods and techniques.
Unfortunately, because of space limitations and because we discuss the
motivation behind our work in detail, we are unable to give more
details.  We refer the interested reader to~\cite{KRoS}.

It is also our hope that the reader will have seen that many interesting
questions remain.  Probably, the most challenging of them concerns developing
an applicable theory of sparse quasi-random hypergraphs.  Here, we have in
mind such lemmas for sparse quasi-random graphs as the ones
in~\cite{kohayakawa99:_ramsey}.

\bibliographystyle{amsplain}
\bibliography{/home/mac/yoshi/www/tem-fapesp-refs}
%\bibliography{tem-fapesp-refs}

%\tableofcontents
\end{document}


