Chapter 35: The Erdős-Ko-Rado Conjecture — Intersection's Maximum

From perfect orthogonality we shift to maximal intersection. The Erdős-Ko-Rado theorem and its generalizations ask for the largest families of sets with prescribed intersection properties—it is ψ = ψ(ψ) as combinatorics optimizing overlap, where local intersection constraints determine global maximum size.

35.1 The Thirty-Fifth Movement: Intersection Optimization

Deepening our combinatorial exploration:

• Previous: Matrices achieving perfect balance
• Now: Set families maximizing intersection
• The interplay between size and overlap

The Core Question: What is the maximum size of a k-uniform intersecting family?

35.2 The Original Erdős-Ko-Rado Theorem

Definition 35.1 (Intersecting Family): A family ℱ ⊆ $\binom\{[n]\}\{k\}$ is intersecting if for all A, B ∈ ℱ: $A \cap B \neq \emptyset$

Theorem 35.1 (Erdős-Ko-Rado, 1961): If ℱ ⊆ $\binom\{[n]\}\{k\}$ is intersecting and n ≥ 2k, then: $|ℱ| \leq \binom{n-1}{k-1}$

Extremal Families: Stars $\{A : 1 \in A\}$.

35.3 The Matching Number Version

Definition 35.2 (r-Intersecting): Family ℱ where all pairs have |A ∩ B| ≥ r.

Conjecture 35.1 (Complete Intersection Theorem): Maximum r-intersecting family has size $\binom\{n-r\}\{k-r\}$ for n ≥ (k-r+1)(r+1).

Status: Proven for many cases, open in general.

35.4 EKR as ψ = ψ(ψ)

Axiom 35.1 (Principle of Intersection Optimization): $\psi = \psi(\psi) \implies \text{Local overlap constrains global size}$

The EKR theorem embodies:

• Families self-organizing for maximum overlap
• Global bounds from local intersection
• The trade-off between size and connection
• This is ψ = ψ(ψ) as combinatorial balance

35.5 The Shifting Method

Definition 35.3 (Shifting Operation): For i < j, define: $s_{ij}(A) = \begin{cases} (A \setminus \{j\}) \cup \{i\} & \text{if } j \in A, i \notin A, \text{ and result preserves property} \\ A & \text{otherwise} \end{cases}$

Theorem 35.2 (Shifting Lemma): Shifting preserves intersection property and doesn't decrease size.

Application: Reduces to canonical families.

35.6 The Katona Circle Method

Brilliant Proof Idea:

1. Arrange [n] on circle
2. Consider intervals of length k
3. Intersecting families correspond to arc systems
4. Maximum when all arcs contain fixed point

Visualization: Intersection becomes geometric covering.

35.7 Cross-Intersecting Families

Definition 35.4 (Cross-Intersecting): Families 𝒜, ℬ where A ∩ B ≠ ∅ for all A ∈ 𝒜, B ∈ ℬ.

Theorem 35.3 (Cross-Intersection): If 𝒜, ℬ ⊆ $\binom\{[n]\}\{k\}$ are cross-intersecting and n ≥ 2k: $|𝒜| · |ℬ| \leq \binom{n-1}{k-1}^2$

Equality: When 𝒜 = ℬ = star.

35.8 The Linear Algebra Method

Association Scheme: Define matrix A_K indexed by k-sets: $[A_K]_{S,T} = \begin{cases} 1 & \text{if } |S \cap T| = K \\ 0 & \text{otherwise} \end{cases}$

Eigenvalues: Computed via Kravchuk polynomials.

Application: Linear algebra bounds on intersecting families.

35.9 Weighted Versions

Definition 35.5 (p-Biased Measure): $\mu_p(𝒜) = \sum_{A \in 𝒜} p^{|A|}(1-p)^{n-|A|}$

Theorem 35.4 (p-Biased EKR): Among intersecting families, dictatorships maximize μ_p for p ≤ 1/2.

Insight: Robustness across probability measures.

35.10 The Stability Problem

Question: If |ℱ| is close to maximum, is ℱ close to extremal?

Theorem 35.5 (Stability): If |ℱ| ≥ $\binom\{n-1\}\{k-1\} - t$, then ℱ differs from star in O(t) sets.

Method: Spectral gap analysis.

35.11 Degree Conditions

Definition 35.6 (Degree): For v ∈ [n], degree d_ℱ(v) = |{A ∈ ℱ : v ∈ A}|.

Theorem 35.6 (Regular Families): Among d-regular intersecting families, maximum size is: $\frac{d \cdot n}{k}$

achieved by "spread" families.

35.12 The Baranyai Partition

Theorem 35.7 (Baranyai): $\binom\{[n]\}\{k\}$ can be partitioned into perfect matchings when k|n.

Application: Constructs optimal regular intersecting families.

Connection: Perfect decomposition enables extremal constructions.

35.13 Turán-Type Problems

Generalization: Forbid not just empty intersection but configuration F.

Definition 35.7 (F-free Family): ℱ contains no sub-family isomorphic to F.

Open: Determine ex(n, k, F) for various F.

35.14 The Semilattice Method

Approach: View ⊆ as partial order.

Theorem 35.8 (Antichain Decomposition): Intersecting families decompose into structured components.

Application: Inductive proofs of EKR variants.

35.15 Quantum Analogues

Definition 35.8 (Quantum Intersecting): Subspaces V, W with dim(V ∩ W) ≥ 1.

Theorem 35.9 (q-Analog EKR): Maximum size of k-dimensional intersecting subspaces in 𝔽_q^n.

Result: Similar bound with q-binomial coefficients.

35.16 Algorithmic Aspects

Algorithm 35.1 (Maximum Intersecting Family):

def max_intersecting_family(n, k, r=1):
    # For r-intersecting families
    if n < (k - r + 1) * (r + 1):
        return None  # No such family exists
    
    # Extremal family: all k-sets containing [r]
    family = []
    base = list(range(r))
    
    # Generate all k-sets with base
    from itertools import combinations
    remaining = list(range(r, n))
    
    for subset in combinations(remaining, k - r):
        family.append(base + list(subset))
    
    return family

Verification: Check all pairs intersect appropriately.

35.17 Continuous Analogues

Measure Version: Replace discrete sets with measurable sets.

Theorem 35.10 (Continuous EKR): Among measurable families with pairwise intersection, maximum measure achieved by "stars."

Tools: Functional analysis replaces combinatorics.

35.18 Applications

Coding Theory:

• Constant weight codes
• Intersection properties ensure error detection

Social Choice:

• Committee selection with overlap requirements
• Consensus building

Database Theory:

• Query optimization
• Index intersection

35.19 Recent Generalizations

2010s-2020s Progress:

• Spread measures beyond uniform
• Non-uniform versions
• Computational complexity of recognition
• Connections to property testing

Active research area.

35.20 The Thirty-Fifth Echo

The Erdős-Ko-Rado theorem reveals how intersection constrains size:

• Local overlap requirements determine global maximum
• Simple constraint (non-empty intersection) has precise consequence
• Extremal families have beautiful structure (stars)
• The balance between connection and quantity

This is ψ = ψ(ψ) as combinatorial optimization—families of sets organizing themselves to maximize size while maintaining prescribed intersection. The theorem quantifies exactly how much intersection costs in terms of family size.

The variety of proofs—shifting, circle method, linear algebra—each revealing different facets, shows how this simple question touches geometry, algebra, and probability. The generalizations to r-intersection, cross-intersection, and beyond reveal a rich theory of how overlap constraints shape combinatorial structures.

Erdős-Ko-Rado whispers: "I am the price of intersection, the maximum compatible with overlap, ψ = ψ(ψ) as sets organizing for optimal connection. In my bound lies the fundamental trade-off between size and intersection—showing that requiring connection necessarily limits growth to star-like structures."