🎲Extremal Combinatorics Unit 12 – Extremal Combinatorics: Problem-Solving

Key Concepts and Definitions

• Extremal combinatorics studies the maximum or minimum size of a collection of finite objects satisfying certain criteria
• Focuses on determining the largest or smallest possible size of a combinatorial structure with specific properties
• Investigates the existence and construction of extremal configurations that achieve the maximum or minimum size
• Ramsey theory, a subfield of extremal combinatorics, explores the conditions under which a combinatorial object must contain a particular substructure
  • Ramsey numbers $R(m,n)$ represent the smallest integer $N$ such that any red-blue coloring of the edges of the complete graph $K_N$ contains either a red $K_m$ or a blue $K_n$
• Turán's theorem establishes an upper bound on the number of edges in a graph that does not contain a complete subgraph of a given size
  • Turán graph $T(n,r)$ is the complete $r$-partite graph with $n$ vertices that has the maximum number of edges without containing a complete subgraph $K_{r+1}$
• Szemerédi's regularity lemma states that every large enough graph can be partitioned into a bounded number of parts, with most pairs of parts forming a pseudo-random bipartite graph
• Extremal set theory investigates the maximum or minimum size of a family of sets satisfying certain conditions (Sperner's theorem, Erdős–Ko–Rado theorem)

Fundamental Principles

• Pigeonhole principle asserts that if $n$ items are placed into $m$ containers and $n > m$, then at least one container must contain more than one item
  • Generalized pigeonhole principle states that if $n$ items are placed into $m$ containers, then at least one container must contain at least $\lceil \frac{n}{m} \rceil$ items
• Dirichlet's box principle, a multidimensional generalization of the pigeonhole principle, deals with the distribution of points in higher-dimensional spaces
• Double counting principle states that if a set of objects can be counted in two different ways, then the two counts must be equal
  • Useful for proving equalities and establishing bijections between sets
• Inclusion-exclusion principle expresses the size of the union of multiple sets in terms of the sizes of their intersections
  • Formula: $|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n|$
• Probabilistic method proves the existence of a combinatorial object with certain properties by showing that a randomly constructed object has a positive probability of possessing those properties
• Extremal graph theory investigates the maximum or minimum number of edges in a graph satisfying specific conditions (triangle-free graphs, bipartite graphs)

Problem-Solving Techniques

• Identify the extremal parameter to optimize (maximum or minimum size, number of edges, substructures)
• Determine the constraints and conditions that the combinatorial object must satisfy
• Utilize fundamental principles (pigeonhole principle, double counting, inclusion-exclusion) to establish bounds or equalities
• Apply known extremal results and theorems (Turán's theorem, Ramsey theory, Sperner's theorem) when applicable
  • Recognize the underlying structure of the problem and map it to a known extremal result
• Employ the probabilistic method to prove the existence of a combinatorial object with desired properties
  • Construct a random object and show that it has a positive probability of satisfying the required conditions
• Use the regularity lemma to partition a large graph into pseudo-random parts and analyze the structure
• Develop a custom extremal construction that achieves the maximum or minimum size while satisfying the given constraints
  • Iteratively refine the construction to improve the bounds or achieve the optimal value
• Prove the optimality of an extremal construction by establishing matching upper or lower bounds using combinatorial arguments or known inequalities

Common Extremal Problems

• Turán-type problems seek the maximum number of edges in a graph that does not contain a specific subgraph (triangle-free graphs, $K_r$-free graphs)
• Ramsey-type problems investigate the minimum size of a structure that guarantees the existence of a particular substructure (Ramsey numbers, van der Waerden numbers)
• Erdős–Stone-type problems determine the maximum number of edges in a graph with a forbidden subgraph of a given chromatic number
• Extremal set theory problems study the maximum size of a family of sets satisfying certain conditions (intersecting families, union-free families)
  • Sperner's theorem states that the maximum size of an antichain in the Boolean lattice $B_n$ is ${n \choose \lfloor n/2 \rfloor}$
  • Erdős–Ko–Rado theorem establishes the maximum size of an intersecting family of $k$-element subsets of an $n$-element set
• Hypergraph Turán problems extend Turán-type questions to hypergraphs, seeking the maximum number of edges in a hypergraph avoiding a specific subhypergraph
• Extremal problems in additive combinatorics investigate the maximum size of a subset of an abelian group satisfying certain additive properties (sum-free sets, Sidon sets)

Proof Strategies

• Induction is a powerful technique for proving statements that depend on a natural number parameter
  • Base case establishes the truth of the statement for the smallest value(s) of the parameter
  • Inductive step assumes the truth of the statement for a value $k$ and proves it for $k+1$
• Contradiction assumes the negation of the desired statement and derives a logical inconsistency
  • Useful for proving the non-existence of a combinatorial object with specific properties
• Pigeonhole principle can be applied to force the existence of a substructure or a repeated configuration
  • Assign elements to "pigeonholes" and argue that at least one "pigeonhole" must contain a certain number of elements
• Double counting establishes equalities by counting the same set of objects in two different ways
  • Useful for proving bijections or relating the sizes of different combinatorial structures
• Probabilistic method proves the existence of an object with desired properties by analyzing a random construction
  • Markov's inequality, Chebyshev's inequality, and Chernoff bounds are commonly used to bound probabilities
• Regularity lemma allows for the decomposition of a large graph into pseudo-random parts, enabling the application of density arguments and counting techniques
• Stability method proves that extremal constructions are essentially unique by showing that any construction close to the extremal size must resemble the known extremal construction
• Flag algebra method uses a semi-definite programming approach to establish asymptotic bounds on the density of substructures in large combinatorial objects

Applications and Examples

• Ramsey theory has applications in various areas, including graph coloring, communication networks, and social sciences
  • Friendship theorem (Ramsey's theorem for $K_3$) states that in any group of six people, there are either three mutual friends or three mutual strangers
• Turán's theorem has implications in extremal graph theory, computer science, and discrete geometry
  • Mantel's theorem (Turán's theorem for triangle-free graphs) asserts that a triangle-free graph on $n$ vertices has at most $\lfloor \frac{n^2}{4} \rfloor$ edges
• Szemerédi's regularity lemma is used in graph property testing, graph limits, and additive combinatorics
  • Roth's theorem on arithmetic progressions can be proved using the regularity lemma
• Extremal set theory results have connections to coding theory, cryptography, and combinatorial designs
  • Sperner's theorem is related to the maximum size of an error-correcting code with minimum distance 2
  • Erdős–Ko–Rado theorem has applications in the study of intersecting families of permutations and vector spaces
• Extremal problems in additive combinatorics have implications in number theory, harmonic analysis, and theoretical computer science
  • Roth's theorem on 3-term arithmetic progressions in dense subsets of integers is an important result in additive combinatorics

Advanced Topics

• Hypergraph Ramsey theory extends Ramsey-type problems to hypergraphs, investigating the existence of monochromatic subhypergraphs
• Szemerédi's theorem on arithmetic progressions states that any subset of the integers with positive upper density contains arbitrarily long arithmetic progressions
  • Furstenberg's ergodic-theoretic proof of Szemerédi's theorem uses techniques from ergodic theory and measure theory
• Extremal problems for sparse graphs, such as the Erdős–Rényi random graph model, investigate the threshold functions for the appearance of specific subgraphs
• Ramsey–Turán theory combines Ramsey theory and Turán-type problems, studying the maximum number of edges in a graph that does not contain a large monochromatic subgraph
• Hypergraph regularity lemmas extend the concept of regularity to hypergraphs, enabling the application of similar techniques as in the graph case
• Extremal problems in algebraic combinatorics explore the maximum or minimum size of combinatorial objects with algebraic structure (sets of permutations, matrices, polynomials)
• Extremal problems in combinatorial geometry investigate the maximum or minimum size of geometric configurations satisfying certain properties (points, lines, angles)
• Algorithmic aspects of extremal combinatorics involve the design and analysis of efficient algorithms for constructing extremal objects or determining their size

Practice Problems and Solutions

1. Prove that any graph with $n$ vertices and more than $\lfloor \frac{n^2}{4} \rfloor$ edges contains a triangle.

   • Solution: Apply Turán's theorem for triangle-free graphs (Mantel's theorem). If the graph has more than $\lfloor \frac{n^2}{4} \rfloor$ edges, it cannot be triangle-free, so it must contain a triangle.

2. Show that in any group of 10 people, there are either four mutual friends or three mutual strangers.

   • Solution: Use Ramsey's theorem for $K_4$ and $K_3$. The Ramsey number $R(4,3)$ is known to be 10. In any red-blue coloring of the edges of $K_{10}$, there exists either a red $K_4$ (four mutual friends) or a blue $K_3$ (three mutual strangers).

3. Prove that any subset $A$ of $\{1,2,\ldots,n\}$ with $|A| > \sqrt{n}$ contains a pair of distinct elements $x,y \in A$ such that $x$ divides $y$.

   • Solution: Apply the pigeonhole principle. Partition the elements of $\{1,2,\ldots,n\}$ into $\sqrt{n}$ "pigeonholes" based on their largest prime factor. If $|A| > \sqrt{n}$, then at least one "pigeonhole" contains two elements $x,y \in A$, and the element with the larger value is divisible by the other.

4. Determine the maximum number of edges in a bipartite graph with 10 vertices in each part that does not contain a complete bipartite subgraph $K_{3,3}$.

   • Solution: Use the Kővári–Sós–Turán theorem, which provides an upper bound on the number of edges in a $K_{s,t}$-free bipartite graph. For $K_{3,3}$-free bipartite graphs with 10 vertices in each part, the maximum number of edges is at most $10^{5/3} + 10 \approx 47$.

5. Prove that any set of 51 distinct positive integers contains a subset of three integers that form an arithmetic progression.

   • Solution: Apply van der Waerden's theorem on arithmetic progressions. The van der Waerden number $W(3,2)$ is known to be 9, meaning that any 2-coloring of the integers $\{1,2,\ldots,9\}$ contains a monochromatic arithmetic progression of length 3. Partition the 51 integers into six groups of size 9 (with one group possibly smaller). By the pigeonhole principle, at least one group contains three integers from the original set, forming an arithmetic progression.