Colour-critical vertex Created 2026-10-06 Updated 2026-10-14
A vertex is colour-critical if deleting it lowers the chromatic number by one. If and , an embedding of into a complete -partite graph inside one neighbourhood extends to an embedding of . This supplies maximum-degree obstructions in extremal graph theory.
David Conlon 2026-11-05
David Conlon studies extremal graph theory and Ramsey theory. His joint work with Jacob Fox, Choongbum Lee and Benny Sudakov shows that imposing a vertex order can make Ramsey problems substantially harder, even for matchings.[ref]
Ordered Ramsey numbers by David Conlon and others. Original byline and abstract
With Joonkyung Lee and Alexander Sidorenko, he also linked failures of a hypergraph analogue of the Sidorenko conjecture to improved extremal lower bounds. This turns a failed density inequality into information about constructions avoiding a specified hypergraph.[ref]
Extremal graph theory Created 2026-09-24 Updated 2026-11-05
Extremal graph theory asks how large or dense a graph can be while avoiding a prescribed configuration. For a fixed graph , its extremal number is the maximum number of edges in an -vertex simple graph containing no copy of as a subgraph.
For instance, Mantel theorem gives : a balanced complete bipartite graph has that many edges and no triangle. The Turan theorem generalizes this to forbidden cliques. Such bounds turn a numerical observation, having many edges, into a structural conclusion, the forced presence of a pattern.
Extremal hypergraph theory Created 2026-10-06 Updated 2026-11-05
Extremal hypergraph theory asks how many hyperedges a hypergraph can have under a forbidden-configuration condition. For a fixed -uniform hypergraph , its extremal number is the maximum number of hyperedges in an -vertex -uniform hypergraph containing no copy of .
For , this is ordinary extremal graph theory. For , pairwise adjacency no longer captures how vertices participate jointly, and even natural small forbidden configurations lead to difficult problems. The normalized limiting edge proportion is the Turán density. Thus hypergraph questions extend graph extremal problems while retaining genuinely higher-order incidence information.
Pál Turán Created 2026-10-14 Updated 2026-11-05
Pál Turán worked in number theory and combinatorics. His1934 proof of the typical size of the number of prime divisors became an important precursor of probabilistic number theory: averaging a counting function can reveal the behaviour of almost all integers without computing it separately for each integer.[ref]
https://mathshistory.st-andrews.ac.uk/Biographies/Turan/. University of St Andrews biography,1934 Hardy–Ramanujan proof and doctoral thesis
In extremal graph theory, the theorem carrying his name asks how many edges force a complete subgraph. The triangle case gives the sharp threshold, attained by a balanced complete bipartite graph.Portrait of Pál Turán
. Bundesarchiv, Bild 183-33149-0001 / CC-BY-SA 3.0; photographer unknown. CC BY-SA 3.0, via Wikimedia Commons. Source. Past exam of the mathematics course of the University of Cambridge 2005 ii Paper 4 17F Solution Created 2026-09-24 Updated 2026-10-14
Extremal graph theory asks how many edges a graph can have while avoiding a prescribed subgraph. Define as the maximum number of edges of an -vertex simple graph containing no copy of ; copies need not be induced. The extremal graph often reveals the structural reason a forbidden configuration must appear.
A complete proof of Mantel theorem illustrates this principle. In a triangle-free graph, the neighborhoods of the endpoints of any edge are disjoint, so . Summing over edges gives , where is the edge count. By Cauchy-Schwarz inequality,Thus when , and the zero-edge case is immediate. A balanced complete bipartite graph is triangle-free and has edges. ThereforeThe proof links a local forbidden triangle to a global degree inequality.
The general Turan theorem states that the balanced complete -partite graph maximizes the edge count among -free graphs. Its leading density is . A standard symmetrization explanation is to replace a lower-degree vertex by a twin of a nonadjacent higher-degree vertex: no is created and the edge count does not decrease. Iterating at the level of twin classes produces a complete multipartite graph with at most parts. Moving vertices between parts then balances the part sizes and maximizes the number of cross edges. This provides structural intuition beyond the preceding exact triangle proof.
For any fixed graph with chromatic number , the Erdős-Stone theorem isThe lower bound is the Turan construction: an -partite graph cannot contain . To describe the upper-bound proof, fix an edge-density excess above . Apply a regularity partition with an error parameter much smaller than that excess and a positive density threshold. Delete irregular and low-density pairs; the resulting reduced graph still has density above the Turan threshold, so it contains . The corresponding vertex classes form pairwise regular, positive-density pairs. The embedding argument successively chooses vertices with large neighborhoods in every remaining class; regularity discards only a small exceptional set at each choice. With the parameters sufficiently small and sufficiently large, this embeds a complete -partite graph with vertices in each part, and therefore a properly colored copy of . This explains why chromatic number, rather than the exact shape of , controls the leading quadratic term.
For example , so forbidding a five-cycle still allows asymptotically edges, and exceeding that density by any fixed positive fraction eventually forces a five-cycle. For the exact Turan theorem strengthens the asymptotic statement. For bipartite , the theorem gives only , leaving an important finer problem: for example -free graphs have upper bounds of order from counting common neighborhoods. Extremal results consequently range from exact finite bounds to asymptotic density thresholds and stability questions about near-extremal structure.
Robbert Fokkink Created 2026-10-14 Updated 2026-11-05
Robbert Fokkink studies game theory, dynamical systems, ergodic theory and topology. His research statement highlights search games, symbolic sequences and the topology of inverse limits and tiling spaces.[ref] A search-game model makes uncertainty strategic: the best search plan depends on where a target can be hidden and what information the searcher receives. His historical research on Willem Abraham Wythoff also connects the provenance of early extremal graph theory with the study of mathematical games.[ref]
https://www.nieuwarchief.nl/serie5/pdf/naw5-2016-17-4-275.pdf. Authored historical article,2016, pp275–280
Homepage: diamhomes.ewi.tudelft.nl/~rfokkink/
Willem Mantel Created 2026-10-14 Updated 2026-11-05
Willem Mantel posed the1907 question now associated with the triangle-free extremal bound: a triangle-free graph with vertices has at most edges. A balanced complete bipartite graph attains the bound. The historical record distinguishes the proposer from the published solver, Willem Abraham Wythoff. Mantel also taught calculus to prospective engineers in Delft.[ref]
https://www.nieuwarchief.nl/serie5/pdf/naw5-2016-17-4-275.pdf. Robbert Fokkink,2016, printed pp279–280, Mantel's1907 problem, published Wythoff proof and teaching role
The result is a model of extremal graph theory: forbidding a small configuration imposes a global limit on edge density.