\documentclass{elsart}
%\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd,amsbsy}
\usepackage{amsmath,amsfonts}

\def\cC{{\mathcal{C}}}
\def\NN{{\mathbb{N}}}
\def\tp{\tilde p}
\def\tA{\tilde A}
\def\ykcomm#1{\marginpar{\tiny #1}}
\def\({\left(}
\def\){\right)}  

\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
  and~300334/93--1), 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}

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 note, 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.

If~$\cC$ is a hypergraph on~$F$, 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$.
%\begin{equation*}
%  \label{eq:alpha_def}
%  \alpha(F,\cC)=\min\Big\{r\in\NN\;\big|\;\exists\, C_1,\dots,C_r\in\cC\text{
%  such that }\bigcup%\nolimits_{j=1}^rC_j=F\Big\}.
%                    \nolimits_{1\leq j\leq r}C_j=F\Big\}.
%                    %_jC_j=F\Big\}.
%\end{equation*}
In this note, we shall be concerned with estimating~$\alpha(F,\cC)$.  Our
first result is a slight improvement of classical results by Johnson, Stein,
and Lov\'asz~(see \cite{John74}, \cite{Lova75}, and~\cite{Stei74}).

\begin{prop}
  \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{1\over1-a/n}}}
      +\frac na\sum_{r=1}^\ell\frac1r 
    <{n\over a}\big(\ln(a+1)+\gamma\big)-{1\over2}\ln{a\over \ell}+{1\over2},
  \end{equation}
  where~$\gamma=0.5772156649\dots$ is Euler's constant.
\end{prop}

The proof of Proposition~\ref{prop:prop1.1} is based on the following remark:
given a subset $A\subset F$, there is always a set $C\in\cC$ such that $|A\cap
C|\ge (b/|\cC|){|A|}=(a/n)|A|$.  (This remark follows from an averaging
argument.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Indeed, for each $B\subset F$, we have 
% $$
% \sum\limits_{C\in\cC}|C\cap B|=\sum\limits_{C\in\cC} \sum\limits_{x\in B}
% \chi_C(x)=\sum\limits_{x\in B} \sum\limits_{C\in\mathcal
%   C}\chi_C(x)=\sum\limits_{x\in B}\big|\{C\in\cC \mid x\in C\}\big|
% =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.  The case
% $B=F$ implies $a|\cC|=bn$, and the case $B=A$ gives
% $\sum\limits_{C\in\cC}|C\cap A|=b|A|$, which implies that there is a set
% $C\in\cC$ for which $|C\cap A|\ge(b/|A|){|\cC|}=(a/n)|A|$, as claimed above.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We omit the details.
%proof of Proposition~\ref{prop:prop1.1}.

\begin{rem}
  \label{rem:rem1.1}
  If we just suppose that $|C|\le a$ for all~$C\in\cC$ and $\deg(x)\ge b$ for
  all~$x\in F$, then we can set $m=|\cC|$ and conclude that
  $n/a\le\alpha(F,\cC)\le f(a,b,m,n)$, where
  $$
  f(a,b,m,n)=
  \begin{cases}
    {\displaystyle\frac na+\frac mb\sum_{r=2}^a\frac1r\le\frac
    mb(\ln(a+1)+\gamma)} 
    &\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\ge m/\sqrt n$}.
  \end{cases}
  $$
\end{rem}

Our main result, given in the following proposition, shows that the estimates
of the previous proposition are asymptotically sharp for certain regular
families of subsets of finite sets.  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}\){\ln
      a\over\ln{\displaystyle{1\over1-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$.   

We now prove Proposition~\ref{prop:prop1.2}.  Because of space limitations, we
consider the case $a\ge n/\ln^3n$ only (the other case requires an 
additional idea).  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$.  We claim that, for $r=\lceil
n/k^2\rceil$, there are $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.
%We omit the proof of this claim.  
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 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 follows by induction.  Let us now proceed with the proof of our
proposition.
% 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.  Let $\overline B=B_1\cup\dots\cup B_s$.  Clearly, $\overline B $
% has $ks<n/k$ elements.  We want to show that there is
% $x=x_{s+1}\in\Zset/n\Zset$ such that $x-T\cap\overline B=\emptyset$. However,
% given $y\in\overline B$, the set $D_y=\{x\in\Zset/n\Zset \mid y\in x-T\}$ has
% $k$ elements, so $\bigcup_{y\in\overline B}D_y$ has at most $k^2s<n$ elements.
% Therefore, there is $x\in\Zset/n\Zset\setminus\bigcup_{y\in\overline B}D_y$.
% For this choice of $x$, we have $(x-T)\cap\overline B=\emptyset$.  Our claim
% follows by induction.

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
${n\choose m}(\frac an)^m(1-\frac an)^{n-m}$, which is maximum for $m=a$, so
the probability that $|\tA|=a$ is at least $1/n$.  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\PP(\forall j\in[r]
  \text{ we have }x_j-T\not\subset\tA^c)
  =n\(1-\(1-\frac an\)^k\)^r,
\end{multline*}
and hence~$p(n,a,k)$ is at most
\begin{equation}
  \label{eq:bla}
  {n\choose k}\tp(n,a,k,r)\le{n\choose k}n\(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}.  %\qed

\begin{thebibliography}{99}

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

\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}