TOPICS
Search

Extremal Graph Theory

Extremal graph theory studies how the intrinsic structure of graphs ensures certain types of properties (e.g., clique-formation and graph colorings) under appropriate conditions.

A basic quantity is the extremal number ex(n,H), the largest number of edges in an n-vertex simple graph containing no copy of a specified graph H. Conlon et al. (2026) proved the rational exponents conjecture, showing that every rational number r in [1,2] is realized by ex(n,H)=Theta(n^r) for a single forbidden graph H, where Theta is big-Theta notation. The proof originated in an AI-assisted research program, as described by the authors.

See also

Erdős Degeneracy Conjecture, Erdős-Simonovits Compactness Conjecture, Erdős-Stone Theorem, Extremal Graph, Extremal Number, Ramsey Theory, Rational Exponents Conjecture, Simonovits Product Conjecture, Structural Ramsey Theory, Szemerédi's Regularity Lemma, Turán Graph, Turán's Theorem

Explore with Wolfram|Alpha

References

Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bollobás, B. Extremal Graph Theory with Emphasis on Probabilistic Methods. Providence, RI: Amer. Math. Soc., 1986.Conlon, D.; Janzer, O.; Jiang, T.; Kim, J.; Lee, J.; Liu, H.; Longbrake, S.; and Yepremyan, L. "A Proof of the Rational Exponents Conjecture." 13 Oct 2026. https://arxiv.org/abs/2610.18713.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 143, 1990.

Referenced on Wolfram|Alpha

Extremal Graph Theory

Cite this as:

Weisstein, Eric W. "Extremal Graph Theory." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ExtremalGraphTheory.html

Subject classifications