Fiveable
Fiveable
Fiveable
Fiveable
Unlock Cram Mode

Extremal Combinatorics

2.1 Ramsey's Theorem for Graphs

3 min readLast Updated on July 22, 2024

Ramsey's Theorem for graphs reveals hidden patterns in large structures. It shows that in any big enough graph, you'll always find either a group of vertices all connected to each other or a group with no connections at all.

This theorem is a powerful tool in extremal combinatorics. It helps us understand the limits of what's possible in graph structures and has real-world applications in areas like social networks and communication systems.

Ramsey's Theorem for Graphs

Ramsey's Theorem for graphs

Top images from around the web for Ramsey's Theorem for graphs
Top images from around the web for Ramsey's Theorem for graphs
  • States for any positive integers mm and nn, there exists a minimum positive integer R(m,n)R(m, n) such that any graph with at least R(m,n)R(m, n) vertices must contain either a clique of size mm (a complete subgraph with mm vertices) or an independent set of size nn (a set of nn vertices with no edges between them)
  • Guarantees the existence of certain substructures in sufficiently large graphs (cliques or independent sets)
  • Establishes a fundamental relationship between the size of a graph and the existence of specific substructures (cliques or independent sets)
  • Provides a framework for studying the unavoidable patterns that emerge in large structures (social networks, communication networks)
  • Has applications in various areas of mathematics, including graph theory, number theory, and geometry (Euclidean Ramsey theory, van der Waerden's theorem)

Existence of Ramsey numbers

  • Can be proven using the probabilistic method or constructive proofs (explicit constructions)
  • Example: Prove that R(3,3)6R(3, 3) \leq 6
    • Consider a complete graph with 6 vertices, K6K_6
    • Color each edge of K6K_6 either red or blue
    • Count the number of monochromatic triangles (cliques of size 3) in each color
      • Let rr be the number of red triangles and bb be the number of blue triangles
      • r+b=(63)=20r + b = \binom{6}{3} = 20, as each triangle is either red or blue
    • If r10r \geq 10, then there is a red K3K_3; if b10b \geq 10, then there is a blue K3K_3
    • Therefore, R(3,3)6R(3, 3) \leq 6

Calculation of small Ramsey numbers

  • R(1,n)=1R(1, n) = 1 for all n1n \geq 1 contains a clique of size 1 and an independent set of size 1 in any graph with 1 vertex
  • R(2,n)=nR(2, n) = n for all n1n \geq 1 must contain either a clique of size 2 (an edge) or an independent set of size nn in any graph with nn vertices
  • R(3,3)=6R(3, 3) = 6, as proven in the previous objective
  • R(3,4)=9R(3, 4) = 9 can be proven using a similar counting argument as in the R(3,3)R(3, 3) case
  • R(3,5)=14R(3, 5) = 14 and R(4,4)=18R(4, 4) = 18 have more complex proofs (use of symmetry, case analysis)

Applications of Ramsey's Theorem

  • Party problem: At a party with at least R(m,n)R(m, n) people, there must be either a group of mm people who all know each other (a clique of size mm) or a group of nn people who are all strangers to each other (an independent set of size nn)
  • Friendship paradox: In any group of at least R(3,3)=6R(3, 3) = 6 people, there must be either a group of 3 mutual friends (a clique of size 3) or a group of 3 mutual strangers (an independent set of size 3)
  • Graph coloring: When coloring the edges of a complete graph with kk colors, Ramsey's Theorem guarantees the existence of monochromatic cliques of a certain size, depending on the number of vertices and the value of kk (Ramsey numbers for multicolored graphs)
  • Applies to the study of social networks, communication networks, and other large complex systems where patterns and structures inevitably emerge as the size of the system grows (cliques of friends, independent sets of non-communicating nodes)
© 2025 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.


© 2025 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.

© 2025 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.