%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LaTeX file for the paper                                           %
%                                                                    %
% Bounds for Optimal Coverings                                       %
%                                                                    %
% by C.G.T.~de A.~Moreira and Y. Kohayakawa                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 29 Jun 2001 09:44:25am BRST yoshi@jaca>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{elsart}
%\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd,amsbsy}
\usepackage{amsmath,amsfonts}

\def\cC{{\mathcal{C}}}
\def\cB{{\mathcal{B}}}
\def\NN{{\mathbb{N}}}
\def\ZZ{{\mathbb{Z}}}
\def\GF{{\mathrm{GF}}}
\def\FF{{\mathbb{F}}}
\def\tp{\tilde p}
\def\tx{\tilde x}
\def\tA{\tilde A}
\def\ta{\tilde a}
\def\tn{\tilde n}
\def\tcC{\widetilde\cC}
%\def\ykcomm#1{\marginpar{\tiny\textbf{yk.}\enspace #1}}
\def\ykcomm#1{[\textbf{yk.}\enspace\textsl{#1}]}
\let\epsilon\varepsilon
\let\log\ln
\def\({\left(}
\def\){\right)}  

\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}

\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}

\begin{document}
\begin{frontmatter}

%\theoremstyle{plain}
%\newtheorem{prop}{Proposition}

%\theoremstyle{remark}
%\newtheorem{rem}{\sc Remark}[section]
%\newtheorem{prop}{Proposition}[section]
%\newtheorem{rem}{Remark}[section]

\title{Bounds for Optimal Coverings}

\thanks[ack]{Partially supported by MCT/FINEP/CNPq (ProNEx Project 416/96 and
  107/97), FAPESP (Proc.~96/04505--2), CNPq (Proc.~300647/95--6, 300334/93--1,
  and~468516/2000--0), and by FAPERJ.}
%\thanks[b]{The authors gratefully acknowledge the careful work of the
%  referees.}  

\author[A1]{Carlos Gustavo T.~de A.~Moreira} and
\author[A2]{Yoshiharu Kohayakawa}

\address[A1]{IMPA -- Estrada Dona Castorina 110, 22460--320 Rio de
  Janeiro, RJ, Brazil -- e-mail: gugu@impa.br}

\address[A2]{Instituto de Matem\'atica e Estat\'\i stica, USP -- Rua do Mat\~ao
  1010, 05508--900 S\~ao Paulo, SP, Brazil
  -- e-mail: yoshi@ime.usp.br}

\begin{abstract}
  We give bounds for optimal coverings of finite sets by elements of regular
  families of subsets, and show that both upper and lower bounds are
  asymptotically sharp for some families of examples.
\end{abstract}
\begin{keyword} 
  Coverings, set systems, hypergraphs, the probabilistic method
\end{keyword} 
\end{frontmatter}


\section{Introduction}
\label{sec:intro}

We study coverings of finite sets by subsets belonging to a regular family.
By an \textit{$(a,b)$-regular} family of subsets of a finite set~$F$, or an
\textit{$(a,b)$-regular hypergraph on~$F$}, we mean a family~$\cC$ for which
there are integers~$a$ and~$b$ such that for each $C\in\cC$ we have $|C|=a$,
and, for each $x\in F$, we have~$\deg(x)=b$, where as
usual~$\deg(x)=\big|\{C\in\cC\mid x\in C\}\big|$.  Thus $(a,b)$-regular
families are what are sometimes called \textit{$a$-uniform},
\textit{$b$-regular} hypergraphs.  The problem of constructing small covers
for such hypergraphs and of estimating the minimum possible size for such
covers are common, and appear in many contexts, as in the study of covering
codes (see~\cite{Cohe97}), in particular, in football pool problems
(see~\cite{Hama95}), in the study of vertex covers of graphs, and others.
Somewhat surprisingly, some sharp results are known for problems of this kind,
see, e.g., \cite{Alon90}, \cite[Theorem~8.11]{Furedi88}, \cite{Furedi96},
and~\cite{Rodl85}.  In this paper, we prove another result that shows that one
may require strong regularity conditions and still obtain hypergraphs that
behave asymptotically `badly' with respect to the size of covers that they
admit.

Let us now introduce the extremal parameter that we are interested in.
If~$\cC$ is a hypergraph on~$F$, we let~$\alpha(F,\cC)$ be the minimal
integer~$r$ for which there exist~$C_1,\dots,C_r\in\cC$ such
that~$\bigcup_{1\leq j\leq r}C_j=F$.  We are concerned with estimating the
extremal values of~$\alpha(F,\cC)$.

This paper is organized as follows.  In Sections~\ref{sec:upper}
and~\ref{sec:lower}, we prove our upper and lower bounds for~$\alpha(F,\cC)$.
Our proof for the existence of systems~$\cC$ with large covering
number~$\alpha(F,\cC)$ is probabilistic; in Section~\ref{sec:constructive}, we
briefly discuss a construction of Alon~\cite{Alon90} based on finite fields
and character sums.  In Section~\ref{sec:packings} we mention the dual problem
of estimating the packing number of hypergraphs.  We conclude with
some remarks and an open problem.

\section{Upper bounds}
\label{sec:upper}

Our first result is a slight improvement of classical results by Johnson,
Stein, and Lov\'asz~(see \cite{John74}, \cite{Lova75}, and~\cite{Stei74}).
Let us say that a family~$\cC$ of subsets of a set~$F$ is
\textit{$(a,b)$-semiregular} if~$|C|\leq a$ for all~$C\in\cC$ and~$\deg(x)\geq
b$ for all~$x\in F$.

\begin{prop}
  \label{prop:upper_bd}
  Let~$a$ and~$b$ be positive integers and suppose~$\cC$ is an
  $(a,b)$-semiregular family on an $n$-element set~$F$. Let~$m=|\cC|$.  Then,
  for any positive integer $\ell'$,
  $$
  {\frac n a}\le \alpha(F,\cC)\le \frac{\ln(m\ell'/bn)}{\ln(1-b/m)}+ \frac
  mb \sum_{1\le j\le \ell'} \frac 1j.
  $$
  In particular, we have $\alpha(F,\cC)\le f(a,b,m,n)$, where we let
  $\ell=\lceil bn/m\rceil$ and
  \begin{equation}
    \label{eq:upper_bd0}
    f(a,b,m,n)=
    \begin{cases}
      {\displaystyle\frac n\ell+\frac mb\sum_{j=2}^\ell\frac1j}
      &\text{if $b\le m/\sqrt n$}\\
      \vspace{-5\jot}\\
      {\displaystyle\frac mb\(\ln\(\frac{bn}m\)+\gamma\)-\frac12\ln\(\frac{b^2
          n}{m^2}\)+\frac12}&\text{if $b>m/\sqrt n$}.
    \end{cases}
  \end{equation}
  Moreover, if~$b\le m/\sqrt n$, we have
  \begin{equation}
    \label{eq:upper_bd1}
    f(a,b,m,n)\leq{n\over a}+{m\over b}\sum_{2\leq r\leq a}{1\over r}
    \le\frac mb(\ln(a+1)+\gamma),
  \end{equation}
  where~$\gamma=0.5772156649\dots$ is Euler's constant.
\end{prop}

We prove Proposition~\ref{prop:upper_bd} in Section~\ref{sec:proof_upper}
below. 

\begin{cor}
  \label{prop:prop1.1}
  Let~$F$ be an $n$-element set and~$\cC$ an $(a,b)$-regular hypergraph
  on~$F$.  Let also~$\ell=\min\{a,\lceil n/a\rceil\}$.  Then
  \begin{equation}
    \label{eq:prop1.1}
    \left\lceil\frac na\right\rceil\le\alpha(F,\cC)\le
    \frac{\ln(a/\ell)}{\ln{\displaystyle{\frac1{1-a/n}}}}
      +\frac na\sum_{r=1}^\ell\frac1r 
    <\frac na\big(\ln(a+1)+\gamma\big)-\frac12\ln\frac a\ell+\frac12.
  \end{equation}
\end{cor}

Our main result, given in Section~\ref{sec:lower} (see
Proposition~\ref{prop:prop1.2}), shows that the estimates for~$\alpha(F,\cC)$
above are asymptotically sharp for certain regular families of subsets of
finite sets.  

\subsection{Proof of Proposition~\ref{prop:upper_bd}}
\label{sec:proof_upper}

We state and prove two auxiliary lemmas first.  For the remainder of this
section, we fix an $(a,b)$-semiregular family~$\cC$ on a set~$F$, where~$a$
and~$b$ are positive integers.  We also let~$n=|F|$ and~$m=|\cC|$.  Our first
lemma follows from a well known double counting argument.

\begin{lem}
  \label{lem:lemma1}
  We have~$am\geq bn$.  Moreover, given any~$A\subset F$, there is~$C\in\cC$
  such that~$|C\cap A|\geq(b/m)|A|$.
\end{lem}
\begin{pf}
  Indeed, for any~$B\subset F$, we have 
  $$
  ma\geq\sum_{C\in\cC}|C\cap B|=\sum_{C\in\cC}\sum_{x\in
    B}\chi_C(x)=\sum_{x\in B}\sum_{C\in\cC}\chi_C(x)=\sum_{x\in
B}\deg(x)\geq
  b|B|,
  $$
  where, as usual, $\chi_C$ is the characteristic function for the set~$C$,
  that is, $\chi_C(x)=1$ if~$x\in C$ and~$\chi_C(x)=0$ otherwise.
  Taking~$B=F$, we obtain~$am\geq nb$, which proves the first inequality in
  our lemma.  Taking~$B=A$, we deduce that $\sum_{C\in\cC}|C\cap A|\geq b|A|$,
  which implies that there is a set $C\in\cC$ for which $|C\cap
  A|\ge(b/|\cC|)|A|$, as required.\qed
\end{pf}

An immediate corollary to Lemma~\ref{lem:lemma1} is the following.

\begin{cor}
  \label{cor:1st_bd}
  For each positive integer~$k$, there are~$C_1,\dots,C_k\in\cC$ such that
  \begin{equation}
    \label{eq:cover_nicely}
    \Big|F\setminus\bigcup_{1\leq i\leq k}C_i\Big|
    \leq n\(1-{b\over m}\)^k.
  \end{equation}
\end{cor}

A finer corollary to Lemma~\ref{lem:lemma1} is as follows.

\begin{cor}
  \label{cor:finer}
  It is possible to cover any~$A\subset F$ with at most
  \begin{equation}
    \label{eq:finer}
    {r\over\ell}+{m\over b}\sum_{2\leq j\leq\ell}{1\over j}
    \leq{m\over b}\sum_{1\leq j\leq\ell}{1\over j}
  \end{equation}
  members of~$\cC$, where~$\ell=\lceil br/m\rceil$ and~$r=|A|$. 
\end{cor}
\begin{pf}
  We can cover~$A$ by~$C_1,C_2,\ldots\in\cC$ so that, for each~$i$, the
  cardinality of~$C_i\cap(A\setminus\bigcup_{1\leq j<i}C_j)$ is as large as
  possible, given~$C_1,\dots,C_{i-1}$.  For~$1\leq s\leq a$, let~$k_s$ be the
  number of sets~$C_i$ in this covering such
  that~$|C_i\cap(A\setminus\bigcup_{1\leq j<i}C_j)|=s$.  A little thought
  shows that Lemma~\ref{lem:lemma1} implies that
  \begin{equation}
    \label{eq:k_bounds}
    k_1\leq{m\over b},\;
    k_1+2k_2\leq{2m\over b},\;\dots\;,\;
    k_1+2k_2+\dots+sk_s\leq{ms\over b}
  \end{equation}
  for all~$s$.  Moreover, clearly, 
  \begin{equation}
    \label{eq:k_bounds2}
    k_1+2k_2+\dots+sk_s\leq r
  \end{equation}
  for all~$s$ as well.  Of course 
  \begin{equation}
    \label{eq:k_bound3}
    k_1+2k_2+\dots+ak_a=r.
  \end{equation}  
  Note also that~$a\geq\ell$.  From~\eqref{eq:k_bounds}--\eqref{eq:k_bound3}
  it thus follows that
  \begin{multline*}
    k_1+\dots+k_a\\
    ={1\over a}(k_1+2k_2+\dots+ak_a)
    +\sum_{1\leq j<a}{1\over j(j+1)}(k_1+2k_2+\dots+jk_j)\\
    \leq{r\over a}+{m\over b}\sum_{1\leq j<\ell}{1\over j+1}
    +r\sum_{\ell\leq j<a}{1\over j(j+1)}\\
    ={r\over\ell}+{m\over b}\sum_{1\leq j<\ell}{1\over j+1}
    \leq{m\over b}\sum_{1\leq j\leq\ell}{1\over j},
  \end{multline*}
  as required.
  \qed
\end{pf}

We may finally prove Proposition~\ref{prop:upper_bd}.

\begin{pf}
  (Proof of Proposition~\ref{prop:upper_bd}) In the case~$b\leq m/\sqrt n$,
  the result in~\eqref{eq:upper_bd0} follows from Corollary~\ref{cor:finer} by
  taking~$r=n$.  The first inequality in~\eqref{eq:upper_bd1} follows from
  \begin{equation*}
    {n\over\ell}={n\over a}+\sum_{\ell\leq j<a}{n\over j(j+1)}
    \leq{n\over a}+{m\over b}\sum_{\ell\leq j<a}{\ell\over j(j+1)}
    \leq{n\over a}+{m\over b}\sum_{\ell\leq j<a}{1\over j+1},
  \end{equation*}
  and hence
  \begin{equation*}
    {n\over\ell}+{m\over b}\sum_{2\leq j\leq\ell}{1\over j}
    \leq{n\over a}+{m\over b}\sum_{2\leq r\leq a}{1\over r}.
  \end{equation*}
  The second inequality in~\eqref{eq:upper_bd1} is clear.
  
In general, given a positive integer $\ell'$, we take $r=m\ell'/b$, and
apply 
 Corollary~\ref{cor:1st_bd} with the smallest~$k$ that makes the right-hand
  side of~\eqref{eq:cover_nicely} less than or equal to~$r$.  After this
  point, we apply Corollary~\ref{cor:finer}.  This gives us the estimate
  \begin{equation*}
    \alpha(F,\cC)\leq{\ln(r/n)\over\ln\(1-b/m\)}+{m\over b}\sum_{1\leq
      j\leq\ell'}{1\over j}.
  \end{equation*}

In order to prove the inequality $\alpha(F,\cC)\le f(a,b,m,n)$ in the case 
$b> m/\sqrt n$,
we just take $\ell'=\lfloor m/b\rfloor$ and apply the above inequality.

  Some calculations complete the proof.  The two main ingredients in these
  calculations are the inequalities
  \begin{equation*}
    \sum_{1\leq r\leq k}{1\over r}-\ln k-\gamma<{1\over2k}-{1\over12k(k+1)}, 
  \end{equation*}
  which is valid for every positive integer~$k$, and
  \begin{equation*}
    -{1\over\ln(1-x)}<{1\over x}-{1\over2},
  \end{equation*}
  valid for all~$0<x<1$.
  \qed
\end{pf}

\section{Lower bounds}
\label{sec:lower}

We work with families of translations of $a$-element subsets
of~$\Zset/n\Zset$. 

 If $A=\{\bar 0,\bar 1,\dots,\overline{a-1}\}\subset\Zset/n\Zset$ 
and $\cC=\{A+t \mid t\in\Zset/n\Zset\}$, where $A+t=\{x+t \mid x\in A\}$,
 then $\alpha(\Zset/n\Zset,\cC)= \lceil n/a\rceil$.

In the other direction, we have the following proposition.

\begin{prop}
  \label{prop:prop1.2}
  There is $a_0\in\mathbb N$ such that if $n>a\ge a_0$ then, for some
  $A\subset F:=\Zset/n\Zset$ with $|A|=a$, the family~$\cC=\{A+t\mid
  t\in \Zset/n\Zset\}$ is such that 
  \begin{equation}
    \label{eq:prop1.2}
    \alpha(F,\cC)>k_0=\(1-\frac{12\ln\ln a}{\ln a}\)\frac{\ln
      a}{\ln{\displaystyle{\frac1{1-a/n}}}}
    >\(1-\frac{12\ln\ln a}{\ln a}\)\(\frac na-1\)\ln a.
%    >\(1-\frac{12\ln\ln a}{\ln a}\)\(\frac na-1\)\ln a,
%      >\(1-\frac{12\ln\ln a}{\ln a}\)\frac na\ln a,
  \end{equation}
%  where $\cC=\{A+t\mid t\in \Zset/n\Zset\}$.
\end{prop}

% Building on earlier work of R\"odl~\cite{Rodl85}, Spencer and Pippenger proved
% that hypergraphs that present even fairly weak regularity conditions must
% admit small covers (see~\cite[Theorem~8.11]{Furedi88}).  We believe
% Proposition~\ref{prop:prop1.2} is interesting in view of this result.

An interesting feature of Proposition~\ref{prop:prop1.2} is that it claims the
existence of uniform, regular hypergraphs with large~$\alpha$.  More
importantly, the parameters~$n>a$ are free and~\eqref{eq:prop1.2} gives good
estimates regardless of the relation between them.  The reader is invited to
compare the bounds in~\eqref{eq:prop1.1} and~\eqref{eq:prop1.2} for the cases
in which (\textit{i})~$a\sim\ln n$, (\textit{ii})~$a\sim n/\ln n$, and
(\textit{iii})~$a\sim n/2$.  In the course of answering a question of Tuza,
Alon~\cite{Alon90} obtained sharp bounds for case~(\textit{ii}), although,
strictly speaking, the hypergraphs in~\cite{Alon90} are not precisely
$a$-uniform (the hyperedges have average cardinality~$a$).
% Novo
We also observe that, in Proposition~\ref{prop:prop1.2} above, for
simplicity, we restrict ourselves to $(a,b)$-regular hypergraphs
with~$a=b$.   

\subsection{Proof of the lower bound}
\label{sec:proof}

We now prove Proposition~\ref{prop:prop1.2}.  The proof is split into two
cases, according to the size of~$a$.  We deal with the case in which~$a$ is
large first; the other case will require an additional idea.

\subsubsection{Large~$a$}
\label{sec:large_a}
Here, we suppose that~$a\geq n/(\ln n)^3$.  We consider all the $a$-element
subsets of $\Zset/n\Zset$, taken with equal probability.  Let us estimate the
probability that such a set $A$ has $k$ translations that cover~$F$, where $k$
is a given positive integer, i.e., let us estimate the probability $p(n,a,k)$
that there should exist $t_1,\dots,t_k\in\Zset/n\Zset$ such that
$(A+t_1)\cup\dots\cup(A+t_k)=\Zset/n\Zset$.  Note that $1-p(n,a,k)$ is the
probability that $(A+t_1)\cup\dots\cup(A+t_k)\ne\Zset/n\Zset$ for any
$t_1,\dots,t_k\in \Zset/n\Zset$, i.e.,
$(A^c+t_1)\cap\dots\cap(A^c+t_k)\ne\emptyset$ for any
$t_1,\dots,t_k\in\Zset/n\Zset$.  Observe that, given
$t_1,\dots,t_k\in\Zset/n\Zset$, we have
$(A^c+t_1)\cap\dots\cap(A^c+t_k)\ne\emptyset$ if and only if there is
$x\in\Zset/n\Zset$ such that $\{x-t_1,\dots,x-t_k\}\subset A^c$.

Fix~$T=\{t_1,\dots,t_k\}\subset\Zset/n\Zset$.  

\begin{claim}
  \label{claim:disjoint}
  Set $r=\lceil n/k^2\rceil$.  There exist $x_1,\dots,x_r\in\Zset/n\Zset$ such
  that the sets $B_i=x_i-T=\{x_i-t_1,\dots,x_i-t_k\}$ $(1\leq i\leq r)$ are
  pairwise disjoint.
\end{claim}
\begin{pf}
  To prove our claim, take $x_1=0$, and suppose that we have chosen
  $x_1,\dots,x_s$, with $s<n/k^2$, such that $B_1,\dots,B_s$ are pairwise
  disjoint.  Since~$s<n/k^2$, clearly~$U=\bigcup_{1\leq i\leq s}(x_i-T)$ has
  fewer than~$n/k$ elements.  Thus the average cardinality of the intersection
  of~$U$ with~$x-T$, for~$x\in\Zset/n\Zset$, is strictly smaller than one,
  whence there is~$x_{s+1}\in\Zset/n\Zset$ such that~$x_{s+1}-T$ is disjoint
  from~$U$.  Our claim thus follows by induction.  (See also
  Section~\ref{sec:packings}.)\qed
\end{pf}

Let us now proceed with the proof of our proposition.  For any fixed
set~$T=\{t_1,\dots,t_k\}$, the probability that $x-T\subset A^c$ for some
$x\in\Zset/n\Zset$ is at least the probability that $x_j-T\subset A^c$ for
some $j\in[r]:=\{1,\dots,r\}$, where the~$x_j$ ($1\leq j\leq r$) are fixed and
are as given by our claim.  This latter probability is $1-\tp(n,a,k,r)$, where
$\tp(n,a,k,r)$ is the probability that $x_j-T\not\subset A^c$ for each
$j\in[r]$.  To estimate $\tp(n,a,k,r)$, we consider random subsets
$\tA\subset\Zset/n\Zset$ constructed as follows: let~$y\in\tA$ with
probability $a/n$, independently for all~$y\in\Zset/n\Zset$.  The probability
that $\tA$ has~$m$ elements is $\binom nm(a/n)^m(1-a/n)^{n-m}$, which is
maximal for $m=a$, so the probability that $|\tA|=a$ is at least~$1/(n+1)$.
With this probability distribution, the events $B_j=x_j-T\not\subset\tA^c$
($j\in[r]$) are independent (because the sets~$B_j$ are pairwise disjoint),
and the probability of each of these events is $1-(1-a/n)^k$.  Hence the
probability that $B_j\not\subset\tA^c$ for all~$j\in[r]$ is $(1-(1-a/n)^k)^r$.
So we have
\begin{multline*}
  \tp(n,a,k,r)=\PP\(\forall j\in[r]
  \text{ we have }x_j-T\not\subset\tA^c\;\Big|\;|\tA|=a\) \\
  \le(n+1)\PP(\forall j\in[r]\text{ we have }x_j-T\not\subset\tA^c)
  =(n+1)\(1-\(1-\frac an\)^k\)^r,
\end{multline*}
and hence~$p(n,a,k)$ is at most
\begin{equation}
  \label{eq:bla}
  \binom nk\tp(n,a,k,r)\le\binom nk(n+1)\(1-\(1-\frac an\)^k\)^r \le
  n^{k+1}\(1-\(1-\frac an\)^k\)^r.
\end{equation}
Let $k=-\beta\ln a/\ln(1-a/n)\le\beta(n/a)\ln n$, where $\beta\le1$. 
We have that the right-hand side of~\eqref{eq:bla}
is~$n^{k+1}\(1-a^{-\beta}\)^r$, which is less than
\begin{equation*}
  n^{1+\beta\ln^4n}\exp\(-\frac{a^{-\beta}n}{k^2}\)
  <\exp\(-\frac{a^{2-\beta}}{\beta^2n\ln^2n}+\ln n\(1+\ln^4n\)\).
\end{equation*}
One may check that if $\beta\le(1-12(\ln\ln a)/\ln a)$, then
$a^{2-\beta}/\beta^2n\ln^2n\geq\ln^6n$ for large~$n$.
% \begin{equation*}
%   \frac{(n/\ln^3n)a^{1-\beta}}{n\ln^2n}
%   \ge\frac{a^{(12\ln\ln a)/\ln a}}{\ln^5a}=\frac{\ln^{12}a}{\ln^5n}
%   \ge\frac{(\ln n-3\ln\ln n)^{12}}{\ln^5n}
%   >\ln^6n.
% \end{equation*}

Since~$\ln^6n\gg\ln n(1+\ln^4 n)$, we have $p(n,a,k)\ll1$.  Therefore there is
$A\subset \Zset/n\Zset$ with $|A|=a$ such that $(A+t_1)\cup\dots\cup
(A+t_k)\ne\Zset/n\Zset$ for any $t_1,\dots,t_k\in\Zset/n\Zset$.  This implies
that, for some $A\subset\Zset/n\Zset$ with $|A|=a$, we have
$\alpha(F,\cC)>k_0$, where $k_0$ is as in~\eqref{eq:prop1.2}.  This completes
the proof of Proposition~\ref{prop:prop1.2} in the case in which~$a\geq
n/(\log n)^3$.

\subsubsection{Small~$a$}
\label{sec:small_a}
We now deal with the case in which~$a$ is `small', that is, $a<n/(\ln n)^3$.
Let
\begin{equation}
  \label{eq:defs}
  b=\lceil a(\ln a+1)\rceil,\quad
  r=\lceil\ln a\rceil,\quad
  \epsilon={1\over r},\quad
  \delta={10\ln\ln a\over\ln a},
\end{equation}
and
\begin{equation}
  \label{eq:defs2}
  k=\llceil{1-\delta\over1+\epsilon}r(\ln a)^2\rrceil. 
\end{equation}
We shall make use of the following claim, to be proved later
(see~\S\ref{sec:paragraph}).

\begin{claim}
  \label{claim:claim}
  There exist~$0\leq y_i<b$ $(1\leq i\leq a)$ so that if we let
  $A_0=\{\overline y_1,\dots,\overline
  y_a\}\subset\{\overline0,\overline1,\dots,\overline{b-1}\}\subset\ZZ/rb\ZZ$, 
  then
  $$
  (A_0+t_1)\cup\dots\cup(A_0+t_k)\ne \ZZ/rb\ZZ
  $$
  for all~$t_1,\dots,t_k\in\ZZ/rb\ZZ$.
\end{claim}

We now prove Proposition~\ref{prop:prop1.2} for~$a<n/(\ln n)^3$ assuming
Claim~\ref{claim:claim}.  Let $\ell=\lfloor n/(r+1)b\rfloor$, and let~$y_i$
($1\leq i\leq a$) be as in Claim~\ref{claim:claim} above.
Put~$A_0=\{\overline y_1,\dots,\overline y_a\}\subset\ZZ/rb\ZZ$, and let
$A=\{y_1\bmod n,\dots,y_a\bmod n\}\subset\ZZ/n\ZZ$.  We claim that
\begin{equation}
  \label{eq:m_cover}
  (A+s_1)\cup\dots\cup(A+s_m)=\ZZ/n\ZZ
\end{equation}
implies that~$m>\ell(k+1)$.  To prove this claim, suppose~\eqref{eq:m_cover}
holds for some $s_1,\dots,s_m\in\ZZ/n\ZZ$.  For $0\le j<\ell$, let
$$
B_j=\{jb(r+1)+q\mid0\le q<rb\}
\text{ and }
I_j=\{i\le m\mid(A+s_i)\cap B_j\ne\emptyset\}.
$$
The sets $I_j$ are pairwise disjoint, since the diameter of $A+s_i$ is at
most $b$, and the distance between $B_j$ and $B_{j+1}$ is $b+1$.  Moreover,
each $I_j$ must have at least $k+1$ elements, since
$$
\bigcup_{i\in I_j}(A+s_i)\supset B_j
$$
implies that
$$
\bigcup_{i\in I_j}(A_0+\overline s_i)=\ZZ/rb\ZZ, 
$$
which, by the choice of~$A_0=\{\overline y_1,\dots,\overline
y_a\}$, implies that~$|I_j|>k$.

To finish the proof we just notice that
\begin{multline*}
  \ell(k+1)=\llfloor\frac n{(r+1)b}\rrfloor
  \(\llceil{1-\delta\over1+\epsilon}r(\ln a)^2\rrceil+1\)\\
  >\(\frac n{(r+1)b}-1\){1-\delta\over1+\epsilon}(\ln a)^3
  >{n\over b(r+1)}(\ln a)^3\(1-{11\ln\ln a\over\ln a}\)\\
  >{n\over a}(\ln a)\(1-{12\ln\ln a\over\ln a}\)
  \geq\(1-\frac{12\ln\ln a}{\ln a}\)\frac{\ln
  a}{\ln{\displaystyle{\frac1{1-a/n}}}},
\end{multline*}
for large enough~$a$. \qed

\paragraph{Proof of Claim~\ref{claim:claim}.}
\label{sec:paragraph}
In order to prove Claim~\ref{claim:claim}, we consider a random subset~$A_0$
of $\{\overline 0,\overline 1,\dots,\overline{b-1}\}$, with each element
present in~$A_0$ independently with probability~$a/b$.  The probability
that~$A_0$ has~$m$ elements is ${b\choose m}(a/b)^m(1-a/b)^{b-m}$, which is
maximal for $m=a$.  Therefore, the probability that such a set~$A_0$ has~$a$
elements is at least~$1/(b+1)$.  As before, we shall condition on the
event~$|A_0|=a$ later in the proof.
  
Let us fix~$t_1,\dots,t_k$ and let us estimate from above the probability that
\begin{equation}
  \label{eq:cover}
  (A_0+t_1)\cup\dots\cup(A_0+t_k)=\ZZ/rb\ZZ.
\end{equation}
Put~$T=\{t_1,\dots,t_k\}$, and observe that~\eqref{eq:cover} occurs if and
only if for all~$x\in\ZZ/rb\ZZ$, the set~$x-T=\{x-t_1,\dots,x-t_k\}$
meets~$A_0$.  Let
\begin{equation}
  \label{eq:s_s_0_def}
  s=\llceil{\epsilon\over1+\epsilon}rb\rrceil
  \quad\text{and}\quad
  s_0=\llceil{s\over k^2}\rrceil.
\end{equation}
We now prove the following two facts (cf.~Claim~\ref{claim:disjoint}):
\begin{enumerate}
\item[(*)] There are $x_1,\dots,x_s$ such that, for each~$i$, we have 
  $$
  |(x_i-T)\cap\{\overline 0,\overline 1,\dots,\overline{b-1}\}|
  \leq(1+\epsilon){k\over r}.
  $$.
\item[(**)] There are~$\tx_1,\dots,\tx_{s_0}\in\{x_1,\dots,x_s\}$ such that
  the sets $\tx_j-T$ ($1\leq j\leq s_0$) are pairwise disjoint.
\end{enumerate}
To prove~(*), it suffices to observe that the average number of elements in
$(x-T)\cap\{\overline 0,\overline 1,\dots,\overline{b-1}\}$ ($x\in\ZZ/rb\ZZ$)
is~$k/r$.  The proof of~(**) is similar to the proof of
Claim~\ref{claim:disjoint}: suppose we
have~$\tx_1,\dots,\tx_{s_1}\in\{x_1,\dots,x_s\}$ such that the sets~$\tx_j-T$
($1\leq j\leq s_1$) are pairwise disjoint, but~$s_1<s/k^2$.  Then
\begin{equation}
  \label{eq:union_small}
  \Big|\bigcup_{1\leq j\leq s_1}(\tx_j-T)\Big|=s_1k<{s\over k}.
\end{equation}
If we select~$x_i\in\{x_1,\dots,x_s\}$ uniformly at random, then the
probability that a fixed element~$z$ in~$\ZZ/rb\ZZ$ belongs to~$x_i-T$ is at
most~$k/s$, because~$k=|T|$ translates of~$T$ contain~$z$.  Because
of~\eqref{eq:union_small}, the expected cardinality of
$$
(x_i-T)\cap\bigcup_{1\leq j\leq s_1}(\tx_j-T)
$$
is strictly smaller than~$1$.  Therefore the
sequence~$\tx_1,\dots,\tx_{s_1}$ may be extended with a new
element~$x_i\in\{x_1,\dots,x_s\}$.  This completes the proof of~(**).

For the remainder of the proof, we concentrate our attention on the~$\tx_j$
in~(**).  One may easily check that the probability that $(\tx_j-T)\cap
A_0\neq\emptyset$ occurs for all $1\leq j\le s_0$ is at most
$$
\(1-\(1-\frac ab\)^{(1+\epsilon)k/r}\)^{s_0}.
$$
Therefore the probability that, for
some~$T=\{t_1,\dots,t_k\}\subset\ZZ/rb\ZZ$, we have $(\tx_j-T)\cap
A_0\neq\emptyset$ for all~$1\leq j\leq s_0$, conditioned on the
event~$|A_0|=a$, is at most
\begin{equation}
  \label{eq:final_prob}
  (b+1)(rb)^k\(1-\(1-\frac ab\)^{(1+\epsilon)k/r}\)^{s_0}.
\end{equation}
We now estimate~\eqref{eq:final_prob} in parts.  In the calculations below, we
tacitly assume that~$a$ is larger than a suitable constant.
Since~$1-a/b\geq1-1/(\log a+1)$, we have
\begin{equation}
  \label{eq:bd1}
  \(1-{a\over b}\)^{(1+\epsilon)k/r}\geq\exp\(-(1+\epsilon){k\over r(\log
  a)}\). 
\end{equation}
We have
\begin{equation}
  \label{eq:bd2}
  (1+\epsilon){k\over r(\log a)}\geq(1-\delta)\log a.
\end{equation}
Putting together~\eqref{eq:bd1} and~\eqref{eq:bd2}, we have 
\begin{equation}
  \label{eq:bd3}
  \(1-\(1-{a\over b}\)^{(1+\epsilon)k/r}\)^{s_0}
  \leq\(1-a^{-1+\delta}\)^{s_0}
  \leq\exp\(-a^{-1+\delta}{\epsilon rb\over(1+\epsilon)k^2}\). 
\end{equation}
Very generously, we have~$rb/k^2\geq a/3(\log a)^4$.  Therefore, again
generously, we have
\begin{equation}
  \label{eq:bd4}
  a^{-1+\delta}{\epsilon rb\over(1+\epsilon)k^2}
  \geq{a^\delta\over7(\log a)^5}.
\end{equation}
On the other hand, a crude estimate gives
\begin{equation}
  \label{eq:bd5}
  (b+1)(rb)^k\leq\exp\(4(\log a)^4\).
\end{equation}
Putting together~\eqref{eq:bd3}, \eqref{eq:bd4}, and~\eqref{eq:bd5}, we see
that the quantity in~\eqref{eq:final_prob} is bounded from above by
\begin{equation}
  \label{eq:bd6}
  \exp\(-{a^\delta\over7(\log a)^5}+4(\log a)^4\).
\end{equation}
Because of our choice of~$\delta$ (see~\eqref{eq:defs}), we have
that~$a^\delta=(\log a)^{10}\gg(\log a)^9$ as~$a\to\infty$, and hence the quantity
in~\eqref{eq:bd6} is~$<1$ for any large enough~$a$.  We conclude that the
probability that~$A_0$ will do in Claim~\ref{claim:claim} is positive, and
hence the claim is proved.\qed

\subsection{Constructive lower bounds}
\label{sec:constructive}

Recall that we prove the existence of systems~$\cC$ with large~$\alpha(F,\cC)$
by taking~$F=\ZZ/n\ZZ$ and considering translates~$A+t$ ($t\in\ZZ/n\ZZ$) for
suitable random sets~$A\subset\ZZ$.  As already observed by
Alon~\cite{Alon90}, if we take~$n$ to be a prime power~$q$ and let~$A\subset
F=\GF(q)$ be the set of squares in~$\GF(q)$, then 
$$
\cC=\{A+t\mid t\in\GF(q)\}
$$
is an $(a,a)$-regular system for~$a=(q-1)/2$ and
\begin{equation}
  \label{eq:alon_ex}
  \alpha(F,\cC)\geq\({1\over2}-o(1)\)\lg q,
\end{equation}
where we write~$\lg$ for the logarithm to the base~$2$.  The bound
in~\eqref{eq:alon_ex} follows from the following result, which we quote
from~\cite{BBf} (see Lemma~9, Chapter~13) without proof.  Let~$\chi$ be the
quadratic character on~$\GF(q)$, so that~$\chi(x)=x^{(q-1)/2}$ $(x\in\GF(q))$.
We have~$\chi(x)\in\{\pm1,0\}$, with~$\chi(x)=0$ if~$x=0$ and~$\chi(x)=1$ if
and only if~$x$ is a square in~$\GF(q)\setminus\{0\}$.

\begin{lem}
  \label{lem:BB}
    If~$T\subset\GF(q)$ and~$k=|T|$,
  then
  \begin{equation}
    \label{eq:BB}
    \Big|q-\sum_{x\notin T}\prod_{t\in T}\(1-\chi(x-t)\)\Big|
    \leq\((k-2)2^{k-1}+1\)q^{1/2}+k2^{k-1}.
  \end{equation}
\end{lem}

Lemma~\ref{lem:BB} is in fact a consequence of a well known estimate of Weil
for character sums (see~\cite{BBf}).  To deduce~\eqref{eq:alon_ex} from
Lemma~\ref{lem:BB}, let~$T\subset\GF(q)$ be an arbitrary set
with~$k=|T|=\lfloor(1/2)\lg q-\lg\lg q\rfloor$.  The element~$x\in\GF(q)$ will
not be covered by the translates~$A+t$ ($t\in T$) if and only if~$x-T$ fails
to meet~$A$, that is, $x-t$~is not a square for any~$t\in T$.  Now, the number
of such~$x$ is
$$
2^{-k}\sum_{x\notin T}\prod_{t\in T}\(1-\chi(x-t)\).
$$
Since by the choice of~$k$ we have
$$
2^{-k}q>{1\over2}(k-2)q^{1/2}+2^{-k}q^{1/2}+{k\over2},
$$
the existence of such an~$x$ follows from~\eqref{eq:BB}.  

Finally, let us observe that our lower bound~$k_0$ in
Proposition~\ref{prop:prop1.2} for the case in which~$a=n/2$ (suppose~$n$ even
for simplicity) is
$$
k_0=\(1-{12\log\log n\over\log n}\)\lg n.
$$
Furthermore, the upper bound for~$\alpha(F,\cC)$ in
Corollary~\ref{prop:prop1.1} for this case is~$\lg n+1$.  Therefore Alon's
construction is off only by a factor of~$2$.  
%\ykcomm{Fazer para
%  $a=n/3,n/4,\dots$ considerando cubos, quartas potencias, etc?}

\section{Packings}
\label{sec:packings}

We briefly consider the problem of finding large packings in regular families.
Suppose~$\cC$ is a family of subsets of a set~$F$.  Let~$\beta(F,\cC)$ be the
maximal integer~$r$ for which there exist pairwise disjoint
sets~$C_1,\dots,C_r\in\cC$.

We prove the following proposition.

\begin{prop}
  \label{prop:pack}
  Suppose~$\cC$ is an $(a,b)$-regular family on an $n$-element set~$F$.  Then 
  \begin{equation}
    \label{eq:pack}
    {n\over a^2}\leq\beta(F,\cC)\leq{n\over a}.
  \end{equation}
\end{prop}

Proposition~\ref{prop:pack} follows from the following lemma.

\begin{lem}
  \label{lem:pack_lemma}
  Let~$\cC$ be an $(a,b)$-regular family of sets on a set~$F$.  Given a
  subset~$\tcC\subset\cC$ with~$r$ elements, it is possible to find a
  subset~$\cB\subset\tcC$ of disjoint sets with at least~$r/ab$ elements. 
\end{lem}

To prove Proposition~\ref{prop:pack}, observe that if~$\cC$ is as in the
statement of that result, then we may take~$\tcC=\cC$.  Note that
then~$r=|\tcC|=|\cC|=bn/a$, and hence~$r/ab=n/a^2$, and the lower bound
in~\eqref{eq:pack} follows.  The upper bound in~\eqref{eq:pack} is obvious. 

We now prove Lemma~\ref{lem:pack_lemma}.

\begin{pf} (Proof of Lemma~\ref{lem:pack_lemma})
  Let~$s$ be the maximal number of pairwise disjoint members in~$\tcC$.
  Suppose for a contradiction that~$s<r/ab$, and let $C_1,\dots,C_s\in\tcC$ be
  such a maximal collection.  Let~$A=\bigcup_{1\leq j\leq s}C_j$.  We
  have~$|A|=as$, so the number of members of~$\tcC$ that intersect~$A$ is at
  most~$abs<r=|\tcC|$.  Therefore there is~$C_{s+1}\in\tcC$ that is disjoint
  from all the~$C_j$ ($1\leq j\leq s$), which contradicts the maximality
  of~$C_1,\dots,C_s$. 
  \qed
\end{pf}

\subsection{An example}
\label{sec:example}
We now observe that the bounds in Proposition~\ref{prop:pack} cannot be
substantially improved without further hypotheses.  Indeed, given a prime
power~$q$ we may take~$F$ to be the projective plane over the finite field
$\GF(q)$, and~$\cC$ to be the collection of lines of~$F$.  Then $|F|=q^2+q+1$,
the system~$\cC$ is $(q+1,q+1)$-regular, and $\beta(F,\cC)=1$.  Notice that
the lower bound in~\eqref{eq:pack} tells us that
$\beta(F,\cC)\ge(q^2+q+1)/(q+1)^2\to1$ as $q\to\infty$.

More generally, given a positive integer~$r$ we may take
$F_r=F\times\{1,2,\dots,r\}$ and $\cC_r=\{L\times\{j\}\mid L\in\cC,\; 1\le
j\le r\}$ (i.e., $F_r$~is the union of $r$~disjoint copies of the projective
plane over~$\GF(q)$ and $\cC_r$ is the collection of lines in these copies).
We have~$|F_r|=r(q^2+q+1)$, the system~$\cC_r$ is $(q+1,q+1)$-regular, and
$\beta(F,\cC)=r$, which is close to the lower bound $r(q^2+q+1)/(q+1)^2$ given
by~\eqref{eq:pack} provided~$q$ is large.  We can use these examples in order
to show that, given sequences of integers~$(a_k)$ and~$(n_k)$, with
$a_k\to\infty$ and $n_k/a_k^2\to\infty$ as $k\to\infty$, there exist
sequences~$(\ta_k)$ and~$(\tn_k)$ such that $\ta_k/a_k$ and $\tn_k/n_k$ tend
to~$1$ as $k\to\infty$ and for which there exist~$F^{(k)}$ and $\cC^{(k)}$
such that $\cC^{(k)}$ is an $(\ta_k,\ta_k)$-regular family of sets on
$F^{(k)}$, where~$|F^{(k)}|=\tn_k$, and
$$
\lim_{k\to\infty}\beta(F^{(k)},\cC^{(k)})\(\frac{\tn_k}{\ta_k^2}\)^{-1}=1
$$
(here we use the fact that there is always a prime between $x$ and
$(1+o(1))x$, which follows from the prime number theorem).

\section{Concluding remarks}
\label{sec:conclude}

If~$a$ is a positive integer, let
\begin{equation*}
%  \label{eq:alpha_n}
  \alpha(a,n)=\max\alpha(F,\cC),
\end{equation*}
where the maximum is taken over all $(a,b)$-regular families of sets~$\cC$ on
an $n$-element set~$F$, and~$b\geq1$ is arbitrary.  Put
$$
f(a)=\limsup_{n\to\infty}{a\over n}\alpha(a,n).
$$
Our results imply that, for any fixed~$a$, we have
\begin{equation}
  \label{eq:us}
  \log a-10\log\log a
  \leq f(a)
  \leq\sum_{1\leq k\leq a}{1\over k}
  =\log a+\gamma+O\(1\over a\).
\end{equation}

Consider the case in which~$a=2$, that is, the case of regular graphs.  It is
not difficult to show that~$(2/n)\alpha(2,n)=4/3+o(1)$ as~$n\to\infty$, so
that~$f(2)=4/3$.  Indeed, for the lower bound, just take for~$\cC$ a
collection of, say, $k$~vertex disjoint triangles on an $3k$-element set~$F$.
Then~$\alpha(F,\cC)=2k$ and we conclude that~$f(2)\geq4/3$.

To prove the upper bound, we show that any $b$-regular graph~$G$ ($b>0$) must
contain a matching that covers at least~$2/3$ of its vertices.  Let~$M$ be a
maximum matching in~$G$, and suppose~$U$ is the set of vertices that are
covered by~$M$.  Suppose for a contradiction that~$|U|<(2/3)n$,
where~$n=|V(G)|$.  Let~$W=U^c=V(G)\setminus U$.  Let the number of neighbours
in~$W$ of a vertex~$u$ in~$U$ be the \textit{$W$-degree~$d_W(u)$ of~$u$}.  The
average $W$-degree of a vertex in~$U$ is~$|W|b/|U|$.  Thus there is an
edge~$e\in M$ whose endpoints~$x$ and~$y$ are such that
\begin{equation}
  \label{eq:augpath}
  d_W(x)+d_W(y)\geq2|W|b/|U|>b.
\end{equation}
Note that~$d_W(x)$, $d_W(y)<b$ (because of the edge~$e=\{x,y\}\subset U$).
Therefore~\eqref{eq:augpath} implies that~$d_W(x)$, $d_W(y)\geq2$.  But then
there exist distinct vertices~$x'$, $y'\in W$, with~$x'$ adjacent to~$x$
and~$y'$ adjacent to~$y'$.  Now observe that~$M\setminus\{e\}\cup\{xx',yy'\}$
is a larger matching than~$M$, which contradicts the maximality of~$|M|$.
This contradiction shows that~$M$ does indeed cover~$(2/3)n$ vertices of~$G$,
and hence~$\alpha(F,\cC)\leq2n/3$.  This implies~$f(2)\leq4/3$.

\begin{prob}
  \label{prob:1}
  Determine~$f(a)$ for all~$a\geq3$.
\end{prob}

Finally, we believe that it would be very interesting to improve on the
constructive lower bounds (see Section~\ref{sec:constructive}). 

\begin{thebibliography}{99}

\bibitem{Alon90} N. Alon: Transversal numbers of uniform hypergraphs,
  \emph{Graphs Combin.} \textbf{6} (1990), 1--4.

\bibitem{BBf} B. Bollob\'as: Random Graphs, \emph{Academic Press}, London,
  1985. 

\bibitem{Cohe97} G. Cohen, I. Honkala, S. Litsyn and A. Lobstein: Covering
  Codes, {\em North-Holland}, Amsterdam, 1997.

\bibitem{Furedi88} Z. F\"uredi: Matchings and covers in hypergraphs,
  \emph{Graphs Combin.} \textbf{4} (1988), 115--206.
  
\bibitem{Furedi96} Z. F\"uredi, G.J. Sz\'ekely and Z. Zubor: On the
  lottery problem, \emph{J. Combin. Des.} \textbf{4} (1996), 5--10.
  
\bibitem{Hama95} H. H\"am\"al\"ainen, I. Honkala, S. Litsyn and P.
  \"Osterg\aa rd: Football pools$\,$---$\,$a game for mathematicians, {\em
  Amer. Math. Monthly} {\bf 102} (1995), 579--588.  
  
\bibitem{John74} D.S. Johnson: Approximation algorithms for combinatorial
  problems, {\em J. Comput. System Sciences} {\bf 9} (1974), 256--298.
  
\bibitem{Lova75} L. Lov\'asz: On the ratio of optimal integral and fractional
  covers, {\em Discrete Math.} {\bf 13} (1975), 383--390.  

\bibitem{Rodl85} V. R\"odl: On a packing and covering problem,
  \emph{Europ. J. Combin.} \textbf{6} (1985), 69--78.
  
\bibitem{Stei74} S.K. Stein: Two combinatorial covering problems, {\em J.
    Comb. Th.}, Ser. A {\bf 16} (1974), 391--397.

\end{thebibliography}
\end{document}