6.3 Applications to Extremal Set Theory

The Erdős-Ko-Rado theorem is a key result in extremal set theory. It sets an upper bound on the size of intersecting families of sets, providing a powerful tool for solving problems involving set intersections.

This theorem has far-reaching implications in combinatorics and beyond. It's sparked numerous generalizations, inspired new proof techniques, and found applications in coding theory and graph theory, shaping the landscape of modern discrete mathematics.

The Erdős-Ko-Rado Theorem and Its Significance

Applications of Erdős-Ko-Rado theorem

• States for a family $\mathcal{F}$ of $k$-element subsets of an $n$-element set, if any two sets in $\mathcal{F}$ intersect, then $|\mathcal{F}| \leq \binom{n-1}{k-1}$ when $n \geq 2k$
  • Bound is tight, achieved by the family of all $k$-element subsets containing a fixed element
• Applying the EKR theorem involves identifying the values of $n$ and $k$ in the problem
  • Check if the condition $n \geq 2k$ is satisfied
  • If met, the maximum size of the family $\mathcal{F}$ is $\binom{n-1}{k-1}$
• Solves various problems involving intersecting families of sets
  • Finding the maximum number of committees formed from a group of people, such that each pair of committees has at least one member in common
  • Determining the maximum number of subsets of a given size that can be selected from a set, ensuring each pair of subsets has a non-empty intersection

Connections in extremal combinatorics

• Closely related to the Kruskal-Katona theorem, which gives a lower bound on the size of the shadow of a family of sets
  • Shadow of a family $\mathcal{F}$ of $k$-element sets is the family of all $(k-1)$-element sets contained in at least one set in $\mathcal{F}$
  • Kruskal-Katona theorem states if $|\mathcal{F}| = \binom{x}{k}$ for some real number $x$, then the size of the shadow of $\mathcal{F}$ is at least $\binom{x}{k-1}$
• Proves the Hilton-Milner theorem, giving the maximum size of an intersecting family that does not contain a fixed element
  • Hilton-Milner theorem states for $n > 2k$, the maximum size of such a family is $\binom{n-1}{k-1} - \binom{n-k-1}{k-1} + 1$
• Connections to the complete intersection theorem, dealing with the maximum size of a family of sets with a given number of pairwise intersections
  • Complete intersection theorem provides bounds on the size of families with specific intersection properties
  • EKR theorem serves as a foundation for studying more complex intersection structures

Significance and Open Problems

Impact on extremal set theory

• Foundational result in extremal set theory, studying the maximum or minimum size of a family of sets satisfying certain properties
• Inspired numerous generalizations and variations
  • Ahlswede-Khachatrian theorem considers families of sets with a fixed number of pairwise intersections
  • Frankl-Wilson theorem deals with families of sets with restricted intersection sizes
• Proof techniques used in the EKR theorem widely applied in extremal combinatorics
  • Shifting technique rearranges the elements of sets to create a more structured family
  • Compression technique transforms a family into a simpler one while preserving key properties
• Found applications in other areas of mathematics
  • Coding theory (designing error-correcting codes with specific properties)
  • Graph theory (studying the maximum size of independent sets in graphs)

Open problems and conjectures

• Erdős matching conjecture states for any family $\mathcal{F}$ of $k$-element subsets of an $n$-element set, if $|\mathcal{F}| > \max\left\{\binom{2k-1}{k}, \binom{n}{k} - \binom{n-k+1}{k}\right\}$, then $\mathcal{F}$ contains a matching of size $k + 1$
  • Proven for $k = 3$ and for sufficiently large $n$ in terms of $k$
  • Remains open for general values of $k$ and $n$
• Erdős-Rothschild problem asks for the maximum size of a family $\mathcal{F}$ of $k$-element subsets of an $n$-element set, such that no three sets in $\mathcal{F}$ have empty intersection
  • Solved for $k = 2$ and $k = 3$, but remains open for larger values of $k$
  • Generalizations to larger intersection sizes and different combinatorial structures are actively studied
• Generalizing the EKR theorem to other combinatorial structures
  • Permutations (Deza-Frankl conjecture proposes an analogue of the EKR theorem)
  • Vectors (studying the maximum size of a family of vectors with specific inner product properties)
  • Graphs (investigating the maximum size of a family of subgraphs with certain intersection properties)