1 Core concepts and definitions

Extremal graph theory investigates extremal questions about graphs subject to restrictions. A restriction is typically expressed by forbidding a particular configuration—most often a fixed subgraph—or by constraining the graph’s density, degrees, or structure. The central theme is to determine or estimate the largest number of edges (or other quantities) compatible with not containing the forbidden object.

1.1 Graph properties and constraints

A graph property can be “global” (e.g., being sparse, having bounded degree, or having no large cliques) or “local” (e.g., forbidding a particular adjacency pattern). In extremal problems, the property is encoded by the absence of one or more subgraphs. Constraints may also be parametric: the graphs are of size \(n\) (number of vertices) and one seeks asymptotic behavior as \(n\to\infty\), or exact values for small \(n\).

1.2 Extremal quantities in graphs

A standard extremal quantity is the Turán-type function. For a fixed graph \(H\), the notation \[ \mathrm{ex}(n,H) \] denotes the maximum number of edges in an \(n\)-vertex graph that contains no (nontrivial) subgraph isomorphic to \(H\). Variants replace “subgraph” with “induced subgraph,” or consider related counts such as the maximum number of copies of one graph while avoiding another.

1.3 Forbidden subgraphs and “for-free” conditions

Most extremal questions specify a forbidden subgraph \(H\) and ask for the largest edge count under the “for-free” condition of being \(H\)-free. Here “for-free” means no explicit cost is paid for avoiding \(H\); rather, the graph is restricted to graphs that never realize the forbidden structure. The challenge is that the same local restriction can force global constraints on density and degree patterns.

1.4 Graph density and asymptotic viewpoints

Many results separate finite-\(n\) behavior from the limiting density. One frequently studies limits of the form \[ \limsup_{n\to\infty} \frac{\mathrm{ex}(n,H)}{\binom{n}{2}}, \] which measures how dense an \(H\)-free graph can be at scale. For certain families, the extremal density stabilizes and can be characterized by the chromatic properties of \(H\), leading to asymptotic theorems that focus on ratios rather than exact edge counts.

2 Fundamental results and theorems

Foundational theorems provide explicit extremal formulas for key forbidden configurations and guide intuition for more complex settings. Several of these results reveal that extremal constructions often come from complete multipartite graphs or close variants.

2.1 Turán’s theorem

Turán’s theorem determines \(\mathrm{ex}(n,K_r)\), the maximum number of edges in an \(n\)-vertex graph containing no \(K_r\). It shows that the extremal graphs are complete \((r-1)\)-partite graphs with parts as equal in size as possible, and it gives a closed formula for the edge count.

2.1.1 Balanced complete multipartite extremal examples

A complete multipartite graph has vertices partitioned into parts, with edges between every two vertices in different parts and none inside parts. When the parts are balanced, such graphs spread connections evenly while preventing large cliques: any clique can use at most one vertex from each part, so it has size at most the number of parts. For \(K_r\)-avoidance, using \(r-1\) parts prevents cliques of size \(r\).

2.1.1.1 Computing the Turán number ex(n, K_r)

If \(n\) is split into \(r-1\) parts of sizes as equal as possible, the Turán number equals the number of cross-part edges: \[

\mathrm{ex}(n,K_r)=\max\{e(G):V(G)=n,\ K_r\not\subseteq G\} = \sum_{1\le i<j\le r-1}V_iV_j.

\] Equivalently, it can be expressed as \[ \mathrm{ex}(n,K_r)=\left(1-\frac{1}{r-1}\right)\frac{n^2}{2} \pm O(n), \] where the lower-order term reflects the unevenness that occurs when \(n\) is not divisible by \(r-1\).

2.2 Mantel’s theorem as a special case

Mantel’s theorem is the case \(r=3\) of Turán’s theorem: it gives \(\mathrm{ex}(n,K_3)\), the maximum number of edges in a triangle-free graph. The extremal construction is the complete bipartite graph with two parts as equal as possible, which maximizes edges while preventing any three vertices from being mutually adjacent.

2.3 Erdős–Stone–Simonovits theorem (asymptotic density)

The Erdős–Stone–Simonovits theorem extends Turán-type thinking to arbitrary forbidden graphs \(H\), describing the asymptotic edge density of \(H\)-free graphs. At a high level, it states that unless \(H\) is bipartite, the extremal density is determined by the chromatic number of \(H\): graphs that avoid \(H\) cannot be too dense, and the maximal density behaves like that of an appropriate Turán graph.

2.4 Zarankiewicz-type extremal formulations

Zarankiewicz-type problems focus on avoiding complete bipartite subgraphs \(K_{s,t}\) rather than cliques. They ask for the largest number of edges in a bipartite graph on given vertex sizes that does not contain \(K_{s,t}\). Such formulations connect extremal graph theory with incidence geometry and with combinatorial bounds that translate between algebraic or geometric structure and forbidden adjacency patterns.

2.5 Kövári–Sós–Turán bounds

The Kövári–Sós–Turán theorem provides an upper bound on \(\mathrm{ex}(n,K_{s,t})\) (in appropriate bipartite formulations). The key phenomenon is that forbidding \(K_{s,t}\) forces subquadratic growth in the number of edges when \(s\) and \(t\) are fixed and \(n\) grows. These bounds are often not tight in every regime, but they establish the correct order of magnitude for many parameter ranges.

3 Ramsey-theoretic connections

Ramsey theory studies the inevitability of monochromatic or structured subgraphs under enough “size” or “density.” Extremal graph theory often converts these inevitability principles into quantitative bounds on how dense a graph can be without forcing the forbidden configuration.

3.1 Ramsey numbers and extremal graph constructions

Ramsey numbers \(R(s,t)\) bound the size \(N\) beyond which any graph on \(N\) vertices contains either a \(K_s\) or an independent set of size \(t\). Extremal graph constructions for avoiding one structure can therefore be used to produce lower bounds for Ramsey numbers, while upper bounds on extremal quantities can imply upper bounds for Ramsey-type thresholds.

3.2 From forbidden structures to Ramsey thresholds

A common bridge is to interpret extremal statements as “thresholds”: if a graph is dense enough, it must contain some unavoidable configuration. Ramsey theory refines this by controlling how large a structure must be before forcing a clique or independent set. Although the contexts differ, both fields identify the point where avoidance becomes impossible.

3.3 Turán-type bounds derived from Ramsey ideas

Turán-type theorems can be viewed through the same lens: forbidding a clique size imposes a density ceiling. Ramsey perspectives reinforce why complete multipartite graphs often become extremal: they “spread” adjacency to delay the emergence of the forbidden clique or related patterns.

4 Induced vs. non-induced extremal problems

Extremal problems can forbid induced subgraphs or merely forbid them as (not necessarily induced) subgraphs. The distinction matters substantially: an induced copy requires exactly the edges present in the pattern, while a non-induced copy permits extra edges between the chosen vertices.

4.1 Induced subgraph avoidance

In induced extremal theory, one typically studies \(\mathrm{ex}^{\mathrm{ind}}(n,H)\): the maximum number of edges in an \(n\)-vertex graph that contains no induced copy of \(H\). Because induced containment is stricter, the extremal edge bounds and typical constructions can differ from those in the non-induced setting.

4.2 Non-induced (subgraph) avoidance

Non-induced avoidance corresponds to the classic notion \(\mathrm{ex}(n,H)\): the forbidden configuration can appear with any additional edges among the chosen vertices, as long as there is a subgraph isomorphic to \(H\). These problems frequently align with Turán-type structures and are often more tractable for cliques and other highly structured graphs.

4.3 Complementary formulations and density dualities

Taking graph complements swaps cliques and independent sets and can convert some induced/non-induced constraints into related ones. Complement-based dualities frequently relate an extremal problem to another where forbiddance conditions are easier to describe or where known bounds apply, especially when the forbidden graph has a simple complement structure.

5 Techniques and proof methods

Proof strategies in extremal graph theory range from counting arguments to sophisticated structural tools. The methods are chosen to match the nature of the forbidden configuration and the extremal quantity under study.

5.1 Double counting and averaging arguments

A basic approach counts the same set of objects in two ways, often combining combinatorial identities with inequalities. Averaging arguments then translate global counts into the existence of vertices or neighborhoods with particular properties. This method is especially effective when the forbidden subgraph imposes a clear local restriction, such as limiting the number of common neighbors.

5.2 Dependent random choice

Dependent random choice is a probabilistic technique tailored to extremal problems where one wants to show the existence of large subsets with strong neighborhood expansion. Rather than picking vertices independently, the method introduces dependence to concentrate structure and derive useful lower bounds on common neighborhoods or induced density.

5.3 Probabilistic method and first-moment heuristics

The probabilistic method constructs or analyzes random graphs to prove existence statements. A common first-moment heuristic estimates how likely it is that a random graph contains the forbidden configuration by computing the expected number of copies; if that expectation is below one, there must exist a graph with no forbidden copies. Refinements may incorporate variance or higher-moment arguments.

5.4 Spectral methods (eigenvalues and expansion)

Spectral techniques use eigenvalues of adjacency matrices or related operators to bound the number of walks of certain lengths, which in turn controls counts of subgraphs. When a graph has a particular eigenvalue profile, it tends to behave like a pseudorandom object, enabling one to rule out forbidden configurations or to show that extremal graphs must have specific expansion characteristics.

5.5 Regularity lemma and its role in extremal problems

Szemerédi’s regularity lemma decomposes large graphs into structured “regular” pieces plus an error term. This permits the reduction of extremal questions to a finite, typically more manageable problem on a smaller “reduced” graph. Although proofs based on regularity can be technically heavy, they provide a framework for deriving asymptotic results and for proving stability statements.

5.6 Stability method and near-extremal structure

Stability results strengthen extremal theorems by describing what graphs look like when they are close to extremality. Rather than only identifying the maximum edge count, stability shows that any nearly optimal \(H\)-free graph must be structurally close to a known extremal construction (often a Turán graph or a related multipartite model). This method is useful for turning “almost maximal” into “almost forced structure.”

6 Exact extremal numbers and small-parameter cases

While asymptotic results describe the behavior for large \(n\), exact values for specific forbidden graphs often require tailored arguments. Small-parameter cases also serve as testbeds for conjectures and as sources of sharp bounds in regimes where general theorems are not precise.

6.1 Determining ex(n, H) for specific graphs H

When \(H\) is fixed and relatively small, \(\mathrm{ex}(n,H)\) can sometimes be computed exactly by combining explicit constructions with upper bounds obtained via specialized counting or structural arguments. These computations may reveal piecewise formulas depending on congruence classes of \(n\).

6.2 Paths, cycles, and bipartite forbidden subgraphs

Forbidding paths or cycles leads to problems where extremal graphs have constrained degrees or limited expansion. In bipartite settings, forbidding even cycles or complete bipartite subgraphs often connects with incidence structures and yields bounds involving fractional exponents, reflecting how constraints propagate through common-neighborhood counts.

6.3 Degree-sequence constraints and realizability

Some extremal questions can be approached through degree sequences: if a graph avoids a forbidden configuration, then degrees and codegrees must satisfy inequalities. Conversely, one may ask whether a candidate extremal degree sequence can actually be realized by a simple graph. Such constraints tie extremal graph theory to realization theorems and to combinatorial design considerations.

6.4 Computational and experimental approaches

Exact computations for moderate \(n\) can be aided by enumeration, integer programming, and heuristic search. These experiments help identify likely extremal constructions, suggest conjectures for exact values, and verify stability behavior for particular forbidden graphs before a full theoretical proof is developed.

7 Extremal graph theory in bipartite settings

Bipartite extremal problems often admit sharper or more geometric interpretations because edges run only between two vertex classes. This context also aligns well with incidence geometry, where vertices represent objects of one type and edges represent relations with another type.

7.1 Bipartite Turán-type problems

Bipartite Turán-type problems ask for the maximum edges in a bipartite graph with forbidden subgraphs, commonly \(K_{s,t}\). The extremal constructions frequently resemble structured “grid-like” patterns or nearly regular bipartite graphs that control the number of shared neighbors.

Even cycles \(C_{2k}\) are natural forbidden subgraphs in bipartite graphs because all cycles in bipartite graphs have even length. Avoiding \(C_{2k}\) restricts the number of short alternating walks between the two parts and thus constrains codegree distributions. As a result, upper bounds often reflect how many edges can be placed without creating too many length-\(2k\) connections.

7.3 Incidence graphs and geometry-inspired constructions

Many constructions for bipartite extremal problems arise from finite geometries: points and lines generate bipartite incidence graphs where edges encode incidence. Such models can be used both to produce lower bounds (by showing many edges can be added while maintaining a controlled girth) and to motivate conjectured tightness of bounds.

8 Multipartite and multipartite-complete extremal structures

Multipartite extremal graphs play a central role because they offer a systematic way to avoid large cliques and manage neighborhood intersections. Many classic theorems point to complete multipartite graphs as optimal or near-optimal models.

8.1 Complete multipartite graphs as extremal models

A complete multipartite graph automatically avoids certain clique sizes: any clique can take at most one vertex from each part. This yields immediate \(K_r\)-free constructions for \((r-1)\)-partite graphs and makes them natural candidates for extremal edge maximization under clique avoidance.

8.2 K_r-free graphs and edge-maximization

Forbidding \(K_r\) guides the edge-maximization problem toward \((r-1)\)-partite structures. The extremal graphs maximize the number of cross-part edges while ensuring that any \(r\)-tuple cannot select one vertex from each of \(r\) different parts to form a full clique. This logic is the backbone behind Turán-type extremal results.

8.3 Multipartite stability and rigidity

Stability methods often show that graphs close to extremality must resemble a complete multipartite graph with nearly balanced parts. “Rigidity” here refers to the idea that the forbidden structure constraint not only limits edge count but strongly determines global organization: small deviations from the multipartite profile typically reduce the edge count by more than the allowed margin.

9 Modern directions and open problems (overview)

Modern research extends classical themes into broader settings, including more complex forbidden families, higher-dimensional analogues, and refined threshold phenomena. Many open problems focus on exact values, sharp constants, or the precise nature of extremal configurations.

9.1 Hypergraph extensions (brief perspective)

Extremal hypergraph theory generalizes forbidden substructures from graphs to higher-uniformity hypergraphs. While complete analogues of classical results are often elusive, many concepts—density, forbidden configurations, and multipartite constructions—carry over in modified form, and new phenomena emerge due to the richer structure of hyperedges.

9.2 Extremal problems under additional constraints

Researchers study extremal questions when graphs are required to satisfy extra conditions beyond mere avoidance—for example, constraints on degree distribution, regularity, bipartiteness, or expansion-like properties. These variants aim to understand how robust the extremal structure is when the search space is narrowed.

9.3 Threshold phenomena and almost-sure extremality

Another direction concerns thresholds: the edge probability in random graphs at which the forbidden configuration appears with high probability. Extremal graph theory interacts here with random graph models, helping to identify when the extremal constructions become typical or “almost surely” optimal within a probabilistic environment.

9.4 Key conjectures and problem families (high-level)

Open problems commonly cluster into families: determining exact extremal numbers for specific forbidden graphs, proving or disproving sharper bounds for \(K_{s,t}\)-free and cycle-free bipartite graphs, and establishing stability with optimal error terms. Across these families, the recurring goal is to pinpoint the exact extremal behavior and understand the structure of all near-extremal examples.