Originators: H. Hanani (presented by D. West - REGS 2009)
Definitions: The covering number C(n,s,t) is the minimum number of s-sets in [n] needed to cover every t-set in [n]; that is, each t-set must be contained in some s-set in the family. A k-uniform hypergraph is a hypergraph in which every edge consists of k vertices. The transversal number τ(H) of a hypergraph H is the minimum size of a set of vertices of H that intersects every edge of H.
Background: Covering numbers have been studied and determined when s and t are both quite small (see [AABBG] for references and a recent result in this direction). Erdős--Hanani [EH] conjectured and Rödl [R] proved that the trivial lower bound (the number of t-sets divided by the number of t-sets that each s-set covers) is asymptotically optimal when s,t are fixed and n is large. The proof is probabilistic, via the famous "Rödl nibble".
When n is large compared to n-s and t, progress can be made by translating the covering problem into a transversal problem for uniform hypergraphs. Let r=n-s. A family S of s-sets covers all the t-sets if and only if every t-set is disjoint from the complement of some member of S. Thus C(n,n-r,t) is the minimum size of an r-uniform hypergraph with vertex set [n] such that no t-set intersects all edges; that is, an r-uniform hypergraph with transversal number at least t+1.
Chvátal and McDiarmid [CM] proved that if H is an r-uniform hypergraph with n vertices and m edges, then τ(H)≤ (⌊r/2⌋m+n)/⌊3r/2⌋. To relate the Chvátal-McDiarmid Theorem to covering numbers, set τ(H)=t+1 and solve for m; this yields a lower bound on the number of r-sets needed to have every t-set avoided by some such r-set: C(n,n-r,t)≥ t+1+(r(t+1)-n)/⌊r/2⌋.
When n≥ r(t+1), it is easy to see that C(n,n-r,t)=t+1, achieved using t+1 disjoint r-sets. The bound from the Chvátal-McDiarmid Theorem shows that the covering number grows by at least 1 for every multiple of ⌊r/2⌋ by which n decreases below r(t+1).
When n < r(t+1), there is not enough room in [n] for t+1 disjoint r-sets. A triangle configuration is a set of three r-subsets of a ⌈3r/2⌉-set such that each point appears in exactly two of the sets (except one appearing in only one set when r is odd). Two points are needed to hit all three sets. If n≥ r(t+1)-k⌊r/2⌋ and k≤ ⌈t/2⌉, then t+1-2k disjoint r-sets and k triangle configurations form an r-uniform family of size t+1+k with transversal number t+1. In particular, note that replacing two disjoint r-sets with one triangle configuration does not change the transversal number, but it decreases the number of points by r/2 and increases the number of r-sets by 1.
When n < ¾(rt)+r, there is not enough room in n to make a family of r-sets with transversal number t+1 by using triangle configurations and disjoint r-sets. An (a,b)-configuration Ta,b is a family of r-sets on ar/b points formed by grouping the points into a groups of size r/b and letting each union of b groups form a set in the family. When b does not divide r, one can use groups of size ⌊r/b⌋ plus extra points to make the r-sets. The transversal number of Ta,b is a-b+1. Constructions using repeated configurations of the form Ta,⌈a/2⌉ (say with two consecutive values of a) provide upper bounds on C(n,n-r,t) as n decreases further.
Problem 1: Prove better lower bounds on C(n,n-r,t), perhaps showing that configurations like those described above are optimal for some ranges of n below rt.
Comments: The first unknown range is for n between about (2/3)r(t+1) and (3/4)r(t+1), with upper bounds using copies of T3,2 and T4,2 (when r is even). At n=(2/3)r(t+1), the upper bound would be about 2(t+1). At n=(3/4)r(t+1), it is about (3/2)(t+1). Roughly speaking, using Ta,⌈a/2⌉ when n is about r(t+1)a/⌊(a+1)²/4⌋ yields an upper bound on C(n,n-r,t) of about {a\choose⌈a/2⌉}(t+1)/(⌊a/2⌋+1) (when r is divisible by ⌈a/2⌉).
Recall that the value of C(n,n-r,t) is the minimum number of edges in an r-uniform n-vertex hypergraph with transversal number t+1. Proving lower bounds in these ranges is equivalent to improving the upper bound on tranversal numbers in the Chvátal-McDiarmid Theorem when n is smaller relative to r(t+1). For even r, the constructions show that the C-M Theorem is optimal when n exceeds about (3/4)r(t+1). To obtain optimality in the next range of covering numbers (that is, C(n,n-r,t) ≥ (3/2)(t+1)+3[¾r(t+1)-n]/(r/2) when n<¾r(t+1)), it would suffice to show that the transveral number of an r-uniform hypergraph with n vertices and m edges is at most [(r/2)m+3n]/(3r) when n<¾r(t+1).
The Chvátal-McDiarmid Theorem can be proved by induction using Shannon's bound on the edge-chromatic number of multigraphs. Improving the bound for larger numbers of edges might require generalization of Shannon's Theorem to edge-coloring of multigraphs.
References:
[AABBG]
Abel, R. Julian R.; Assaf, Ahmed; Bennett, Frank E.; Bluskov, Iliya; Greig,
Malcolm Pair covering designs with block size 5. Discrete Math. 307 (2007),
no. 14, 1776--1791.
[CM]
Chvátal, V.; McDiarmid, C.
Small transversals in hypergraphs.
Combinatorica 12 (1992), no. 1, 19--26.
[EH]
Erdős P.; Hanani, H. On a limit theorem in combinatorial analysis.
Publ. Math. Debrecen 10 1963 10--13.
[R]
Rödl, V
On a packing and covering problem. European J. Combin. 6
(1985), no. 1, 69--78.