A short proof of the Hilton-Milner Theorem

Denys Bulavka and Russ Woodroofe · 2024

Read A short proof of the Hilton-Milner Theorem by Denys Bulavka and Russ Woodroofe (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-02513.txt.

Description

Abstract . We give a short and relatively elementary proof of the Hilton-Milner Theorem. The Hilton-Milner Theorem gives the maximum size of a uniform pairwise-intersecting family of sets that do not share a common element. Theorem 1 (Hilton and Milner 1967 [ 9 ] ) . Let k\leq n/2 .

Catalog record

CREATORDenys Bulavka and Russ Woodroofe
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-02513

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A short proof of the Hilton-Milner Theorem Thanks: Work of the first author is partially supported by the Israel Science Foundation grant ISF-2480/20. Work of the second author is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects J1-9108, J1-2451, J1-3003, and J1-50000). Denys Bulavka and Russ Woodroofe Abstract . We give a short and relatively elementary proof of the Hilton-Milner Theorem. The Hilton-Milner Theorem gives the maximum size of a uniform pairwise-intersecting family of sets that do not share a common element. Theorem 1 (Hilton and Milner 1967 [ 9 ] ) . Let k\leq n/2 . If \mathcal{F} is a family of pairwise-intersecting k -element subsets of [n] , where \bigcap_{F\in\mathcal{F}}F=\emptyset , then \left|\mathcal{F}\right|\leq{n-1\choose k-1}-{n-1-k\choose k-1}+1 . In the current article, we will show Theorem 1 to follow quickly from the following theorem, which we believe to be of some independent interest. Two set systems \mathcal{A} and \mathcal{B} are cross-intersecting if for every A\in\mathcal{A},B\in\mathcal{B} , the intersection A\cap B is nonempty. The shadow \partial B of a k -element set B consists of all the (k-1) -element subsets of B ; the shadow of a uniform set family is the union of the shadows of its constituent sets. Theorem 2 . Let 2k-1\leq n , let \mathcal{A} be a family of (k-1) -element subsets of [n] , and let \mathcal{B} be a family of k -element subsets of [n] . If \mathcal{A},\mathcal{B} are cross-intersecting, \mathcal{B} is nonempty, and \partial\mathcal{B}\subseteq\mathcal{A} , then \left|\mathcal{A}\right|+\left|\mathcal{B}\right|\leq{n\choose k-1}-{n-k\choose k-1}+1. Note that the bound of Theorem 1 is attained with a single k -element set B that does not contain 1 , together with all the k -element sets that contain 1 and intersect B ; the bound of Theorem 2 is attained with a single k -element set and all (k-1) -element sets that intersect it. Our proof of Theorem 1 may be viewed as injective. Other recent proofs of Theorem 1 were given in [ 4 , 10 ] , but instead of relying on a simple cross-intersecting type theorem, both of these proofs rely on a certain “partial complement” operation. In somewhat older work [ 6 ] (see also [ 3 ] ), Frankl and Tokushige gave a proof of Hilton-Milner from a different cross-intersection theorem, but the proof is less elementary than that of Theorem 2 , requiring the Schützenberger-Kruskal-Katona Theorem. A recent preprint of Wu, Li, Feng, Liu and Yu [ 12 ] gives a proof based on still another cross-intersecting theorem, but the existing proofs of this underlying result also seem to be somewhat more difficult than our approach. Shifting We recall that a system \mathcal{F} of subsets of [n] is shifted if for each i<j , whenever F\in\mathcal{F} , j\in F and i\notin F , then also \left(F\setminus j\right)\cup i\in\mathcal{F} . Here, we abuse notation to identify i,j with the singleton subsets \{i\},\{j\} where it causes no confusion. The (combinatorial) shifting operation \operatorname{Shift}_{i\leftarrow j} is defined as \displaystyle\operatorname{Shift}_{i\leftarrow j}\mathcal{F}= \displaystyle\left\{F\in\mathcal{F}:j\notin F\text{ or }i\in F\text{ or }\left(F\setminus j\right)\cup i\in\mathcal{F}\right\} \displaystyle\cup\left\{\left(F\setminus j\right)\cup i:F\in\mathcal{F}\text{ is such that }j\in F,i\notin F\right\}. It is well-known that repeated applications of \operatorname{Shift}_{i\leftarrow j} over i<j will eventually reduce an arbitrary set system to a shifted set system, that the operation preserves the cross-intersecting property, and that \partial\operatorname{Shift}_{i\leftarrow j}\mathcal{F}\subseteq\operatorname{Shift}_{i\leftarrow j}\partial\mathcal{F} [ 2 , 1 , 7 , 8 ] . Proof of Theorem 2 We carry out a straightforward induction on n . . If n=2k-1 , then the upper bound is {n\choose k-1} , and the result follows by noticing that if a (k-1) -element set is in \mathcal{A} , then its complement cannot be in \mathcal{B} (and vice-versa). For the inductive step, we may assume that \mathcal{A} and \mathcal{B} are shifted; otherwise, shift. Let \mathcal{A}(\neg n),\mathcal{B}(\neg n) consist of the subsets in \mathcal{A},\mathcal{B} (respectively) that do not contain n . It is immediate that \mathcal{A}(\neg n),\mathcal{B}(\neg n) are shifted, cross-intersecting, and satisfy the shadow condition. Let \mathcal{A}(n),\mathcal{B}(n) be obtained by taking the families consisting of the subsets in \mathcal{A},\mathcal{B} that contain n , then deleting n from each subset. It follows quickly from definitions that \mathcal{A}(n),\mathcal{B}(n) are shifted, cross-intersecting, and satisfy the shadow condition. As \mathcal{A} and \mathcal{B} are shifted, so \mathcal{A}(\neg n) and \mathcal{B}(\neg n) are nonempty, and hence by induction (1) \left|\mathcal{A}(\neg n)\right|+\left|\mathcal{B}(\neg n)\right|\leq{n-1\choose k-1}-{n-1-k\choose k-1}+1. For \mathcal{A}(n),\mathcal{B}(n) , there are a few easy cases: If \mathcal{A}(n) is empty, then (by the shadow condition) also \mathcal{B}(n) is empty. If \mathcal{B}(n) is empty, then since \mathcal{B} is nonempty and shifted, we have \{1,\dots,k\}\in\mathcal{B} . Since every set in \mathcal{A}(n) intersects with \{1,\dots,k\} , we get \left|\mathcal{A}(n)\right|+\left|\mathcal{B}(n)\right|=\left|\mathcal{A}(n)\right|\leq{n-1\choose k-2}-{n-1-k\choose k-2} . If \mathcal{B}(n) is nonempty, then by induction it holds that \displaystyle\left|\mathcal{A}(n)\right|+\left|\mathcal{B}(n)\right| \displaystyle\leq{n-1\choose k-2}-{n-1-(k-1)\choose k-2}+1 (2) \displaystyle\leq{n-1\choose k-2}-{n-1-k\choose k-2}. The result now follows from ( 1 ), the bound on \left|\mathcal{A}(n)\right|+\left|\mathcal{B}(n)\right| , and the Pascal’s Triangle identity. ∎ Proof of Theorem 1 We will use the following lemma of Frankl and Füredi: Lemma 3 (essentially Frankl and Füredi [ 5 ] ) . If \mathcal{F} is a pairwise-intersecting family of k -element subsets of [n] with \bigcap_{F\in\mathcal{F}}F=\emptyset , then there is a shifted family \mathcal{F}^{\prime} satisfying the same properties and with \left|\mathcal{F}^{\prime}\right|\geq\left|\mathcal{F}\right| . . Given the lemma, the proof of Theorem 1 is nearly immediate. Let \mathcal{F} be a shifted family satisfying the conditions of the theorem. Define \displaystyle\mathcal{A}= \displaystyle\,\{F\setminus 1\,\, \displaystyle:F\in\mathcal{F}\text{ with }1\in\mathcal{F}\} \displaystyle\mathcal{B}= \displaystyle\,\{F \displaystyle:F\in\mathcal{F}\text{ with }1\notin\mathcal{F}\} . Since \mathcal{F} is shifted, if F\in\mathcal{F} does not have 1 , then \left(F\setminus i\right)\cup 1\in\mathcal{F} for each i\in\mathcal{F} . It follows that \partial\mathcal{B}\subseteq\mathcal{A} . Since \mathcal{F} is intersecting, also \mathcal{A},\mathcal{B} are cross-intersecting systems of subsets of \{2,\dots,n\} . Since \mathcal{F} has empty intersection, both of \mathcal{A},\mathcal{B} are nonempty. The desired bound is now immediate from Theorem 2 . ∎ Remark 4 . This proof requires only the special case of Theorem 2 where the set systems are shifted. Proof of Lemma 3 For completeness, we also prove the lemma. . Given \mathcal{F} as in Theorem 1 , apply shifting operations \operatorname{Shift}_{i\leftarrow j} . Each such operation preserves the pairwise-intersecting property and cardinality, but may or may not result in a system with a common element of intersection. If a sequence of shifting operations ends in a shifted system with empty intersection, then we are certainly done. Otherwise, some \operatorname{Shift}_{i_{0}\leftarrow j_{0}} results in a system where every set contains i_{0} . Thus, before this step, we have a system \mathcal{F} where every set contains either i_{0} or j_{0} . Relabel i_{0} to 1 and j_{0} to 2 , and continue applying \operatorname{Shift}_{i\leftarrow j} operations over all 3\leq i<j . Thus, after these additional shift operations, we have \left\{1,3,\dots,k+1\right\} and \left\{2,3,\dots,k+1\right\} in the system. Without loss of generality, we also have all k -element subsets containing \left\{1,2\right\} ; otherwise, add them. Thus, we have \partial\left\{1,\dots,k+1\right\} contained in our system. As \partial\left\{1,\dots,k+1\right\} has empty intersection and is preserved under all further shift operations (over 1\leq i<j ), the result follows. ∎ Discussion In addition to being short and direct, our proof is relatively elementary, using only shifting theory. Indeed, we recover a completely elementary proof of the restriction of the Hilton-Milner Theorem to shifted systems. A main difficulty in proofs of Hilton-Milner

Read the complete text