Hilton-Milner tells us about an intersecting family of $k$-size subsets $\mathcal{F}$ from $\binom{[n]}{k}$: If $|\mathcal{F}| > \binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1$, then all elements of $\mathcal{F}$ share at least 1 element of [n].

The theorem classifies the non-trivial $\mathcal{F}$ if equality occurs i.e. $|\mathcal{F}| = \binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1$.

I was wondering if there are known results/literature to see on classifications with $|\mathcal{F}| < \binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1$, particularly values very close to equality?

I am currently looking at the case of $n=7$, and $k=3$ to get an idea of this (i.e. what can be said about an intersecting family of size 12 < $\binom{6}{2}-\binom{3}{2}+1?)$.

  • $\begingroup$ Does the question refer somehow to the Hilton-Milnor theorem (named after Peter Hilton and John Milnor) on homotopy groups of wedges of spheres? $\endgroup$ – Alex Suciu Apr 18 '12 at 22:30
  • $\begingroup$ No, this is a set theory result with Anthony Hilton and Eric Milner. $\endgroup$ – Mike Apr 19 '12 at 17:28
  • $\begingroup$ The set-theory tag seems misplaced here, since the topic is really finite combinatorics. $\endgroup$ – Joel David Hamkins Apr 17 '13 at 2:56

There are at least three types of results that spring to mind. One is the Ahlswede-Khachatrian theorem ("the complete intersection theorem"), which for each $n$ and $k < n/2$ will give you tight upper bounds for $t$-intersecting families (families in which every two sets intersect in at least $t$ points). For example, if $k \leq n/3 + 1$ then a $2$-intersecting family has size at most $\binom{n-2}{k-2}$, and so if $|\mathcal{F}| > \binom{n-2}{k-2}$ then there are two sets $S,T \in \mathcal{F}$ such that $|S \cap T| = 1$. They also have a matching Hilton-Milner type result, in which the family is required to have empty intersection ("the complete non-trivial intersection theorem").

A second one is stability results. Such results show that if $|\mathcal{F}| = (1-\epsilon)\binom{n-1}{k-1}$ then there is an element belonging to a $1-O(\epsilon)$ fraction of the sets. One such result is due to Friedgut ("on the measure of intersecting families, uniqueness and stability"), another is due to Keevash ("shadows and intersections: stability and new proofs").

A third one is due to Dinur and Friedgut ("intersecting families are essentially contained in juntas"). For $k = cn$, they show that any intersecting family essentially depends on $O(1)$ points, where the constant depends on $c$. For $k = o(n)$, they can show that any intersecting family has an element common to all but $C \binom{n-2}{k-2}$ of the sets.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.