2025-11-26T13:16:17.903747

Hilton-Milner Theorem for the $r$-independent sets in a union of cliques

Gunderson, Meagher, Morris et al.
We give a Hilton-Milner Theorem for the $r$-independent sets in the graph that is the union of copies of $K_k$. That is, we determine the maximum intersecting families of $r$-independent sets in this graph, subject to the condition that the sets in a family do not all share a common element. As a by-product, we also find a tight upper bound for the sum of sizes of a pair of cross intersecting families made up of the same objects. We apply our theorem to find the largest intersecting family of $r$-independent sets in a family of graphs called ``depth-two claws". This confirms the Holroyd--Talbot conjecture for depth-two claws, extending previous results on these graphs (which covered cases where $r$ was relatively small compared to the number of vertices) to all possible values of $r$.
academic

Hilton-Milner Theorem for the rr-independent sets in a union of cliques

Basic Information

  • Paper ID: 2511.18785
  • Title: Hilton-Milner Theorem for the rr-independent sets in a union of cliques
  • Authors: Karen Gunderson (University of Manitoba), Karen Meagher (University of Regina), Joy Morris (University of Lethbridge), Venkata Raghu Tej Pantangi
  • Classification: math.CO (Combinatorics)
  • Submission Date: November 24, 2025 (arXiv submission)
  • Paper Link: https://arxiv.org/abs/2511.18785

Abstract

This paper establishes a generalization of the Hilton-Milner theorem for rr-independent sets in the union of complete graphs Γn,k=∪i=1nKk\Gamma_{n,k} = \cup_{i=1}^n K_k. Specifically, the authors determine the size and structure of maximum intersecting families under the constraint that all sets share no common element. As a byproduct, the paper establishes tight upper bounds on the sum of sizes for cross-intersecting family pairs. The results are applied to "depth-two claws," proving that these graphs satisfy the Holroyd-Talbot conjecture for all possible values of rr, extending previous results that held only for smaller rr values.

Research Background and Motivation

Core Problem

This paper investigates a classical problem in extremal set theory: In the family of rr-independent sets of the graph Γn,k\Gamma_{n,k} (the disjoint union of nn copies of KkK_k), when requiring that all sets in the family share no common element (i.e., ∩F=∅\cap \mathcal{F} = \emptyset), what are the maximum size and structure of an intersecting family?

Problem Significance

  1. Natural generalization of classical theory: The Erdős-Ko-Rado (EKR) theorem and Hilton-Milner theorem are cornerstones of extremal combinatorics. Extending them to independent sets of graphs is an important research direction.
  2. Theoretical importance: The EKR property characterizes combinatorial properties of graph structures. The Holroyd-Talbot conjecture predicts that for any graph GG, if r<μ(G)/2r < \mu(G)/2 (where μ(G)\mu(G) is the size of the minimum maximal independent set), then GG is rr-EKR.
  3. Technical challenges: When r>n/2r > n/2, the classical Hilton-Milner theorem cannot be directly applied, requiring development of new techniques to handle "large" independent sets.

Limitations of Existing Methods

  • Deza-Frankl (1983): Proved that Γn,k\Gamma_{n,k} is rr-EKR for all r≤nr \leq n, but did not address the maximum value problem for non-regular intersecting families.
  • Feghali et al. (2018): For depth-two claws, proved the rr-EKR property only when 2r−1≤n2r-1 \leq n, leaving the case of large rr unresolved.
  • Technical gaps: Details of compression operations in previous literature are often omitted, leading to gaps in some proofs.

Research Motivation

This paper aims to:

  1. Establish a complete Hilton-Milner-type theorem for rr-independent sets in Γn,k\Gamma_{n,k}
  2. Develop a rigorous framework for compression and projection techniques
  3. Apply the new results to resolve the Holroyd-Talbot conjecture for depth-two claws (for all values of rr)

Core Contributions

  1. Main Theorem (Theorem 3.1): Determines the maximum size of non-regular intersecting families in Γn,k\Gamma_{n,k}
    • When 3≤r<n3 \leq r < n: ∣F∣≤∣Hn,kr∣|\mathcal{F}| \leq |\mathcal{H}^r_{n,k}|, and for r≥4r \geq 4, equality holds if and only if F≅Hn,kr\mathcal{F} \cong \mathcal{H}^r_{n,k}
    • When r=nr = n: Provides explicit upper bounds and extremal structures
  2. Cross-Intersecting Theorem (Theorem 3.3): For cross-intersecting family pairs (A,B)(\mathcal{A}, \mathcal{B}), proves ∣A∣+∣B∣≤∣Hn,kr∣+∣Mn,kr∣|\mathcal{A}| + |\mathcal{B}| \leq |\mathcal{H}^r_{n,k}| + |\mathcal{M}^r_{n,k}| and completely characterizes when equality holds
  3. Application Result (Theorem 9.3): Proves that the depth-two claw GnG_n is (strictly) rr-EKR for all 1≤r≤n−11 \leq r \leq n-1, completely resolving the Holroyd-Talbot conjecture for this graph class
  4. Methodological Contributions:
    • Rigorous formalization of the theoretical framework for compression and projection operations (Section 4)
    • Development of pairing techniques for handling r>n/2r > n/2 cases (Lemma 5.1-5.7)
    • Systematization of Hilton-Milner theory for bounded set families (Section 6)

Detailed Methodology

Task Definition

Basic Objects:

  • Graph Γn,k=Kk(1)∪⋯∪Kk(n)\Gamma_{n,k} = K_k^{(1)} \cup \cdots \cup K_k^{(n)}, with vertices labeled (i,j)(i,j), where i∈[n]i \in [n] denotes the clique index and j∈[k]j \in [k] denotes the vertex within the clique
  • In,kr\mathcal{I}^r_{n,k}: The set of all rr-independent sets, with ∣In,kr∣=(nr)kr|\mathcal{I}^r_{n,k}| = \binom{n}{r}k^r

Intersecting Families: A family F⊆In,kr\mathcal{F} \subseteq \mathcal{I}^r_{n,k} is called intersecting if for any F1,F2∈FF_1, F_2 \in \mathcal{F}, we have F1∩F2≠∅F_1 \cap F_2 \neq \emptyset

Objective: Determine the maximum size of intersecting families satisfying ∩F=∅\cap \mathcal{F} = \emptyset

Core Construction

Hilton-Milner Family (Definition 3.1): Hn,kr={F∈En,kr:F∩H≠∅}∪{H}\mathcal{H}^r_{n,k} = \{F \in \mathcal{E}^r_{n,k} : F \cap H \neq \emptyset\} \cup \{H\} where:

  • H=[2,r+1]×{1}H = [2, r+1] \times \{1\} (special set not containing (1,1)(1,1))
  • En,kr={F∈In,kr:(1,1)∈F}\mathcal{E}^r_{n,k} = \{F \in \mathcal{I}^r_{n,k} : (1,1) \in F\} (regular family)

Size Calculation (Equation 3.2): ∣Hn,kr∣=1+∑j=1r−1(rj)(n−r−1r−j−1)kr−j−1(kj−(k−1)j)|\mathcal{H}^r_{n,k}| = 1 + \sum_{j=1}^{r-1} \binom{r}{j}\binom{n-r-1}{r-j-1}k^{r-j-1}(k^j - (k-1)^j)

Technical Framework

1. Compression Operations (Section 4)

Definition: For i∈[n],s∈[2,k]i \in [n], s \in [2,k], define

X \setminus \{(i,s)\} \cup \{(i,1)\} & \text{if}\ (i,s) \in X \\ X & \text{otherwise} \end{cases}$$ Family compression: $$\pi_{i,s}(\mathcal{F}) = \{P_{i,s}(X) : X \in \mathcal{F}\} \cup \{X : X, P_{i,s}(X) \in \mathcal{F}\}$$ **Key Properties** (Lemma 4.1): - Preserves family size: $|\pi_{i,s}(\mathcal{F})| = |\mathcal{F}|$ - Preserves intersecting property: If $(\mathcal{A}, \mathcal{B})$ is cross-intersecting, then $(\pi_{i,s}(\mathcal{A}), \pi_{i,s}(\mathcal{B}))$ is also cross-intersecting **Stable Families**: $\mathcal{F}$ is called stable if $\pi_{i,s}(\mathcal{F}) = \mathcal{F}$ for all $i,s$ #### 2. Projection Operations **Definition**: $\phi : \mathcal{I}^r_{n,k} \to \binom{[n]}{\leq r}$ defined by $$\phi(X) = \{i : (i,1) \in X\}$$ **Key Lemma** (Lemma 4.2): For stable cross-intersecting pairs $(\mathcal{A}, \mathcal{B})$, for any $A \in \mathcal{A}, B \in \mathcal{B}$ there exists $i$ such that $(i,1) \in A \cap B$ **Preimage Counting** (Equation 4.1): For $\mathcal{X} \subseteq \binom{[n]}{\leq r}$, $$|\phi^{-1}(\mathcal{X})| = \sum_{\ell=0}^r \binom{n-\ell}{r-\ell}(k-1)^{r-\ell} \cdot |\mathcal{X}^{(\ell)}|$$ where $\mathcal{X}^{(\ell)}$ is the $\ell$-uniform part of $\mathcal{X}$ #### 3. Pairing Technique for $r > n/2$ (Section 5) **Core Lemma** (Lemma 5.1): For $n/2 \leq r \leq n$ and $r$-maximal cross-intersecting pairs $(\mathcal{S}, \mathcal{T})$, when $\ell, n-\ell \leq r$: $$|\mathcal{S}^{(n-\ell)}| + |\mathcal{T}^{(n-\ell)}| + |\mathcal{S}^{(\ell)}| + |\mathcal{T}^{(\ell)}| = 2\binom{n}{\ell}$$ **Proof Strategy**: Through complement correspondence $X \leftrightarrow X^c$, establish $$X \in \binom{[n]}{\ell} \setminus (\mathcal{S}^{(\ell)} \cup \mathcal{T}^{(\ell)}) \iff X^c \in \mathcal{S}^{(n-\ell)} \cap \mathcal{T}^{(n-\ell)}$$ **Optimization Lemma** (Lemma 5.7): Let $c_\ell = C^{n,k}_{r,\ell} = \binom{n-\ell}{r-\ell}(k-1)^{r-\ell}$. If $\ell < n/2$ then $c_\ell > c_{n-\ell}$ (Lemma 5.6). For $x,y$ satisfying $x + y = x_0 + y_0$ and $x \leq x_0$: $$xc_\ell + yc_{n-\ell} \leq x_0 c_\ell + y_0 c_{n-\ell}$$ with equality if and only if $x = x_0$ ### Proof Strategy **Proof of Theorem 3.3** (Section 7): 1. Reduce to stable pairs via compression operations 2. Project to $\binom{[n]}{\leq r}$, setting $x_\ell = |\mathcal{S}^{(\ell)}| + |\mathcal{T}^{(\ell)}|$ 3. Case analysis: - **$r \leq n/2$**: Directly obtain $x_\ell \leq y_\ell$ from Lemma 5.5 (where $y_\ell$ corresponds to extremal family pair values) - **$r > n/2$**: Partition $[r]$ into $M_1, M_2, M_3$, pair $M_2$ and $M_3$ via $\ell \leftrightarrow n-\ell$ using Lemma 5.1, apply Lemma 7.1 (optimization lemma) **Proof of Theorem 3.1** (Section 8): 1. If compression yields $\cap \mathcal{C} \neq \emptyset$: Find the family $\mathcal{F}$ before the last compression, decompose into $\mathcal{F}_1, \mathcal{F}_2$ (containing $(1,1)$ and $(1,2)$ respectively), apply Theorem 3.3 to $(\tilde{\mathcal{F}}_1, \tilde{\mathcal{F}}_2)$ 2. If $\cap \mathcal{C} = \emptyset$: Project to $r$-maximal intersecting family $\mathcal{S} \subseteq \binom{[n]}{\leq r}$, apply Hilton-Milner theory from Section 6 (Lemma 6.3), combined with optimization techniques ## Experimental Setup This is a pure theoretical mathematics paper with no experimental verification. All results are established through rigorous mathematical proofs. ### Verification Methods - **Small case verification**: For small parameters like $r=2,3$, verify theorems through direct calculation (Lemma 3.2) - **Boundary cases**: Detailed analysis of special cases $r=n$ and $r=n-1$ - **Extremal constructions**: Explicitly provide family structures achieving the upper bounds ## Experimental Results ### Main Theoretical Results **Theorem 3.1 (Main Theorem)**: - **Upper bound**: $|\mathcal{F}| \leq |\mathcal{H}^r_{n,k}|$ - **Uniqueness**: For $r \geq 4$, equality holds $\iff \mathcal{F} \cong \mathcal{H}^r_{n,k}$ - **Exception**: For $r=3$, non-isomorphic extremal families exist (Lemma 3.2) **Theorem 3.3 (Cross-Intersecting)**: - **Upper bound**: $|\mathcal{A}| + |\mathcal{B}| \leq |\mathcal{H}^r_{n,k}| + |\mathcal{M}^r_{n,k}|$ - **Characterization**: For $r \geq 3$, equality $\iff (\mathcal{A}, \mathcal{B}) \cong (\mathcal{H}^r_{n,k}, \mathcal{M}^r_{n,k})$ ### Application Results **Theorem 9.3 (Depth-Two Claws)**: Let $G_n$ be the depth-two claw with $n$ leaves. Then: 1. For all $1 \leq r \leq n-1$, $G_n$ is $r$-EKR 2. For $4 \leq r < n-1$, $G_n$ is strictly $r$-EKR **Proof Key Points**: - Decompose $G_n$ into root vertex $c$ and $\Gamma_{n,2}$ - Family decomposition: $\mathcal{A} = \mathcal{B} \cup \mathcal{C}$ (where $\mathcal{B}$ does not contain $c$, $\mathcal{C}$ contains $c$) - When $\cap \mathcal{B} = \emptyset$, apply Theorem 3.1 to obtain $$|\mathcal{B}| \leq |\mathcal{H}^r_{n,2}| = \binom{n-1}{r-1}2^{r-1} - \sum_{j=0}^{r-1}\binom{r}{j}\binom{n-r-1}{r-j-1}2^{r-j-1} + 1$$ - Combine with $|\mathcal{C}| \leq \binom{n}{r-1}$ and Lemma 9.2 (technical inequality) to prove $$|\mathcal{A}| < \binom{n-1}{r-1}2^{r-1} + \binom{n-1}{r-2}$$ (size of regular family) ### Technical Results **Lemma 6.3 (Bounded Set Hilton-Milner)**: For $r$-maximal intersecting family $\mathcal{B} \subseteq \binom{[n]}{\leq r}$ with $\cap \mathcal{B} = \emptyset$: $$|\mathcal{B}^{(\ell)}| \leq |\mathcal{V}_{n,r}^{(\ell)}|$$ for all $2 \leq \ell \leq \min\{r, \lfloor n/2 \rfloor\}$, and for $r \geq 4$, equality for all $\ell$ holds $\iff \mathcal{B} \cong \mathcal{V}_{n,r}$ ## Related Work ### Classical Theory 1. **Erdős-Ko-Rado Theorem (1961)**: - Original version: When $n \geq 2r$, maximum intersecting family in $\binom{[n]}{r}$ has size $\binom{n-1}{r-1}$ - Uniqueness: When $n > 2r$, the unique extremal family is the regular family 2. **Hilton-Milner Theorem (1967)**: - Non-regular intersecting families have maximum size $\binom{n-1}{r-1} - \binom{n-r-1}{r-1} + 1$ - Extremal family structure: $\mathcal{H}_{n,r}$ (Equation 2.2) 3. **Cross-Intersecting Theory**: - Hilton-Milner/Simpson: $|\mathcal{A}| + |\mathcal{B}| \leq 1 + \binom{n}{r} - \binom{n-r}{r}$ - Frankl-Tokushige: Generalization to sets of different sizes - Borg-Feghali: Generalization to bounded-size families ### EKR Property for Graphs 1. **Deza-Frankl (1983)**: - Proved $\Gamma_{n,k}$ is $r$-EKR for all $r \leq n$ - Strictly $r$-EKR except for $(k,r)=(2,n)$ 2. **Holroyd-Spencer-Talbot (2005)**: - Generalization to unions of cliques of different sizes - Development of compression techniques 3. **Holroyd-Talbot Conjecture (2005)**: - Conjecture: $r < \mu(G)/2 \Rightarrow G$ is $r$-EKR - This paper completely resolves it for depth-two claws ($\mu(G_n) = n$) 4. **Feghali-Johnson-Thomas (2018)**: - Depth-two claws: $r$-EKR when $2r-1 \leq n$ - This paper extends to all $r \leq n-1$ ### Advantages of This Paper 1. **Completeness**: First complete Hilton-Milner theorem for $\Gamma_{n,k}$ (for all $r$) 2. **Rigor**: Develops rigorous compression theory framework, filling gaps in literature 3. **Technical innovation**: Pairing technique for handling $r > n/2$ cases 4. **Breadth of application**: Resolves complete conjecture for depth-two claws ## Conclusions and Discussion ### Main Conclusions 1. **Theoretical Contributions**: - Completely determine extremal structures of non-regular intersecting families in $\Gamma_{n,k}$ - Establish tight bounds for cross-intersecting family pairs - Develop systematic theory for bounded set families 2. **Application Results**: - Prove depth-two claws satisfy Holroyd-Talbot conjecture for all $r \leq n-1$ - Determine when regular families are unique extremal families 3. **Methodology**: - Three-step framework: compression-projection-optimization - Pairing technique for handling large parameters ### Limitations 1. **Parameter Restrictions**: - Cannot characterize all extremal families when $r=3$ (Lemma 3.2) - Depth-two claws are not EKR when $r=n$ (Proposition 9.4) 2. **Graph Class Restrictions**: - Only handles disjoint unions of complete graphs - Depth-two claw results depend on special property of $k=2$ 3. **Technical Constraints**: - Compression operations may change set sizes, requiring handling of bounded families - Additional pairing techniques needed when $r > n/2$ ### Future Directions (Section 10) 1. **Unions of Cliques of Different Sizes**: - Question: Can Theorem 3.1 be generalized to $\Gamma = \cup_{i=1}^n K_{k_i}$ (where $k_i$ are not all equal)? - Challenge: Choice of regular family is not unique 2. **Rooted Unions of Cliques**: - Construction: $n$ copies of $K_k$ plus a root connected to one vertex in each clique - Question: For which $(n,k,r)$ is this graph $r$-EKR? - Partial results: - $k \leq \frac{n-2}{\ln(n/2)}$: Non-root vertices optimal - $k > n+1$: Root vertex optimal - Intermediate cases: Depend on $r$ 3. **Other Projection Objects**: - Apply compression-projection method to other combinatorial objects - Example: Multisets (preliminary work in [14]) 4. **Hilton-Milner Theorem for General Graphs**: - For graphs satisfying Holroyd-Talbot conjecture, does a unified Hilton-Milner-type result exist? ## In-Depth Evaluation ### Strengths 1. **Theoretical Rigor**: - Detailed treatment of compression and projection operations (Section 4) fills gaps commonly overlooked in literature - All lemmas have complete proofs; particularly, Lemma 6.3 re-proves results from [14] 2. **Technical Innovation**: - **Pairing Technique** (Lemma 5.1-5.7): Cleverly handles $r > n/2$ cases through $\ell \leftrightarrow n-\ell$ pairing - **Optimization Framework** (Lemma 7.1): Unifies treatment across different parameter ranges - **Preimage Counting** (Equation 4.1): Connects graph independent sets to abstract set families 3. **Result Completeness**: - Provides not just upper bounds but complete characterization of extremal structures - Handles all parameter ranges (including boundary case $r=n$) - Explicitly identifies exceptional cases (non-uniqueness for $r=3$) 4. **Application Value**: - Resolves complete conjecture for depth-two claws, extending from $2r-1 \leq n$ to all $r \leq n-1$ - Provides methodological template for studying other graph classes 5. **Clarity of Exposition**: - Well-structured: Background (§2) → Results (§3) → Techniques (§4-6) → Proofs (§7-8) → Applications (§9) - Clear motivation: Each technical lemma has explicit purpose statement ### Weaknesses 1. **Incompleteness for $r=3$**: - Lemma 3.2 provides counterexample but does not fully characterize extremal families - Missing complete description of all extremal families when $r=3$ 2. **Weak Results for $r=n$**: - Upper bound in Theorem 3.1(2) is not as tight as for $r < n$ - Depth-two claws are not EKR when $r=n$, limiting application scope 3. **Technical Complexity**: - Proof requires many auxiliary lemmas (7 lemmas in Sections 5-6) - Extensive case analysis ($r \leq n/2$, $n/2 < r < n$, $r=n$) 4. **Limited Generalizability**: - Proof for depth-two claws heavily relies on $k=2$ (bipartite structure) - Section 10 discussion of $k=3$ case shows method does not directly apply 5. **Computational Complexity**: - Formula for $|\mathcal{H}^r_{n,k}|$ (3.2) involves summation, less elegant than regular family formula - Lacks asymptotic analysis (e.g., behavior as $n \to \infty$) ### Impact Assessment 1. **Theoretical Contribution**: - **High**: Completely resolves Hilton-Milner problem for $\Gamma_{n,k}$, supplements Deza-Frankl work - Rigorous formalization of compression theory will influence subsequent related work 2. **Methodological Value**: - **Medium-High**: Pairing technique and optimization framework may apply to other extremal problems - Generalization to arbitrary graphs remains challenging 3. **Practical Utility**: - **Low**: Pure theoretical results with no direct applications - Provides tools for understanding combinatorial properties of graph structures 4. **Reproducibility**: - **High**: All proofs complete, no additional computational experiments needed - Key constructions ($\mathcal{H}^r_{n,k}$) explicitly defined ### Applicable Scenarios 1. **Direct Applications**: - Independent set problems for unions of complete graphs - Depth-two claws and similar tree structures - Independent sets in bipartite graphs (via $k=2$ case) 2. **Method Borrowing**: - EKR property research for other graph classes - Extremal set theory problems requiring compression techniques - Combinatorial optimization involving projection operations 3. **Theoretical Research**: - Further study of Holroyd-Talbot conjecture - Hilton-Milner-type theorems for general graphs - Extremal theory of cross-intersecting families ### Technical Evaluation **Highlights of Proof Techniques**: 1. **Criticality of Lemma 4.2**: Stable families' intersection must lie in $[n] \times \{1\}$, preserving intersecting property under projection 2. **Symmetry of Lemma 5.1**: Complement correspondence $X \leftrightarrow X^c$ establishes duality between $\ell$ and $n-\ell$ 3. **Weight Optimization in Lemma 5.7**: Uses $c_\ell > c_{n-\ell}$ (when $\ell < n/2$) for inequality manipulation **Potential Improvements**: 1. Does a unified method exist for all $r$ (avoiding case analysis)? 2. Can a more concise formula or asymptotic estimate be given for $|\mathcal{H}^r_{n,k}|$? 3. Is complete characterization for $r=3$ feasible? ## Key References 1. **[5] Erdős-Ko-Rado (1961)**: Foundational work, original EKR theorem 2. **[10] Hilton-Milner (1967)**: Extremal results for non-regular intersecting families 3. **[4] Deza-Frankl (1983)**: Proves EKR property for $\Gamma_{n,k}$ 4. **[12] Holroyd-Talbot (2005)**: Proposes conjecture on graph EKR properties 5. **[6] Feghali-Johnson-Thomas (2018)**: Partial results for depth-two claws 6. **[14] Liao et al. (2023)**: Hilton-Milner theorem for multisets (technical foundation for this paper) --- **Overall Assessment**: This paper represents important theoretical work in extremal combinatorics, completely resolving the Hilton-Milner problem for unions of complete graphs through rigorous mathematical proof and successfully applying results to depth-two claws. Technically, it develops pairing methods for handling large parameters; methodologically, it systematizes the compression-projection framework. Despite limitations such as incompleteness for $r=3$ and restricted generalizability, its theoretical contributions and methodological innovations make it an important reference in the field. The paper is rigorously written with complete proofs, serving as an excellent technical template for related research.