This question comes out of REU research from this past summer. Unfortunately weeks of thought led to only trivial observations and the conclusion that the problem is quite hard.

Fix $k,t$. Let $F$ be a set of $k$-subsets of $[n] := \{1,\ldots,n\}$ of minimal cardinality such that $F$ covers all $t$-subsets of $[n]$ (covers in the sense that any $t$-subset of $[n]$ is a subset of an element of $F$.) Let $\kappa_n := |F|$. The Erdős-Hanani conjecture states that

$\kappa_n = \binom{n}{t} / \binom{k}{t}(1 + o(1))$.

Of course $\binom{n}{t} / \binom{k}{t}$ is a lower bound on $\kappa_n$, so the EH conjecture is saying that the obvious necessary condition is asymptotically sufficient. Rödl proved the EH conjecture in 1985.

This question is about what happens when $k$ and $t$ are not fixed. Specifically, take $k = \lfloor n/2 \rfloor$ and $t = \lfloor n/2\rfloor - 1$. Define $F$ and $\kappa_n$ as above. Is it true that

$\kappa_n = \frac{1}{\lfloor n / 2 \rfloor} \binom{n}{\lfloor n/2 \rfloor}(1 + o(1))$?


The EH conjecture lead to the study of what is called "packing in a hypergraph." See http://en.wikipedia.org/wiki/Packing_in_a_hypergraph. Rödl's proof introduced what is now called the "Rödl nibble" and is pseudo-random in nature. Spencer gave a lovely proof using branching processes. There are a lot of results from the late 80s to 90s that say, as Kahn puts it in "Asymptotics of Hypergraph Matching, Covering and Coloring Problems", that hypergraphs are asymptotically well-behaved as long as their edge sizes are bounded! Unfortunately the $n/2$ version of EH involves hypergraphs of unbounded edge size and the existing methods appear useless.

Some ideas

A straightforward application of the method of alterations (or equivalently, some easy analysis of the greedy algorithm) gives that $\kappa_n \leq \log n \frac{1}{\lfloor n / 2 \rfloor} \binom{n}{\lfloor n/2 \rfloor} (1 + o(1))$, so the whole question is whether we can eliminate this log factor.

A set of $\lfloor n/2 \rfloor$-subsets has maximum coverage of $(\lfloor n/2 \rfloor - 1)$-subsets when all its elements have pairwise symmetric difference of at least 4. So really this is a coding theory problem. The paper "Lower bounds for constant weight codes" by Graham and Sloane shows that we can find a set $H$ of $\lfloor n /2\rfloor$-subsets of $[n]$ such that $|H| \geq \frac{1}{2}\binom{n}{\lfloor n/2 \rfloor}$ and the hamming distance between elements is at least 4. Let $G$ be the set of $(\lfloor n/2 \rfloor - 1)$-subsets covered by $H$. $G$ is half the size we want it to be, but we only used half as many elements are we are allowed. So we might be optimistic that by allowing some small overlap we can cover everything we want. If we take a permutation $\sigma \in S_n$ and look at $\sigma(H)$ (i.e. apply the permutation to the elements of the elements of $H$) it covers $\sigma(G)$. Of course $|\sigma(G)| = |G|$. We could hope that a good choice of $\sigma$ gives $|G \cup \sigma(G)| \approx 2|G|$ and we have found an appropriate set $F := H \cup \sigma(H)$. I asked the question of whether such a $\sigma$ must exist before: Size of union of a set of subsets and its permutations. That question is interesting in its own right, but this EH conjecture is really why I wanted an answer.

  • $\begingroup$ Have you checked out the La Jolla Covering Repository online? That might give a nice suggestion of what to expect. Gerhard "Ask Me About System Design" Paseman, 2013.02.15 $\endgroup$ – Gerhard Paseman Feb 16 '13 at 1:32
  • $\begingroup$ Does your description have $t$ and $l$ mixed up? If so, please edit. $\endgroup$ – Brendan McKay Feb 16 '13 at 1:36
  • $\begingroup$ @Brendan McKay: Yes, thank you. It is corrected. $\endgroup$ – Sam Hopkins Feb 16 '13 at 2:04
  • $\begingroup$ I should mention also that the Graham-Sloane construction means that the EH-conjecture for $k = \phi(n)$ and $t = k - 1$ has a positive answer when $\phi(n) = o(n)$, so $n/2$ is in fact the "hard case." $\endgroup$ – Sam Hopkins Feb 16 '13 at 2:15
  • $\begingroup$ Some structural results on this part of the boolean lattice can be found with the search phrases "middle levels" and "boolean" together. For example, see the references in arxiv.org/pdf/math.CO/0608485.pdf . $\endgroup$ – Brendan McKay Feb 16 '13 at 3:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.