Supersaturation strengthens an extremal existence theorem by forcing many copies of a forbidden graph when the edge count exceeds its extremal threshold by a fixed density. For a fixed clique, the Erdős-Stone theorem and averaging over bounded-size random vertex subsets give a positive multiple of copies.
Choose a fixed sample size for which the normalized Turan theorem bound lies below the given density by a positive margin. The expected edge count in a random -vertex subset then forces a positive proportion of subsets to contain a forbidden-size clique. Each clique belongs to a known number of subsets, so double counting gives a positive constant times cliques.
The extremal number is the largest number of edges in an -vertex graph containing no subgraph isomorphic to .
For fixed positive integers and sufficiently large , the unique extremal graph forbidding vertex-disjoint copies of the complete graph is the join of graphs , up to isomorphic graphs. Each forbidden clique would require a distinct vertex of .
For every fixed graph , the sequenceis nonincreasing once . Indeed, choose a uniformly random -vertex induced subgraph of an extremal -free graph on vertices. It remains -free and has expected edge countwhich cannot exceed .
Every graph on vertices with at least edges contains at least triangles. An induction deletes the endpoints of an edge lying in no triangle; if every edge lies in a triangle, the edge-triangle incidence bound is already sufficient.
Among -vertex graphs containing no , the maximum number of edges is attained by the complete -partite graph whose part sizes differ by at most one, denoted .
A clique-free graph near the Turan theorem edge bound is close to a complete multipartite graph. Choose a maximum-degree vertex, split its neighbourhood from the remaining vertices, and apply induction inside the neighbourhood. The degree bound implies that missing cross edges are at least twice the number of edges inside the remaining class. This inequality controls all three types of edits and gives the constant three.
Fix an odd cycle length. If the graph has edge density at least and sufficiently few copies of that cycle, odd-cycle copies from positive triangle density forces few triangles in a graph. The triangle removal lemma deletes at most edges, after which the clique-free edit bound applies with two parts. Absorbing its linear rounding error into the density margin gives the displayed bound for large order.
The Turan graph is the complete multipartite graph on vertices with parts whose sizes differ by at most one.
For , put , , and . Every graph on vertices satisfiesThus an edge count forces at least triangles in a graph. This is an exact finite bound, with the rounding in the Turan graph retained. To prove it, use edge-triangle symmetrization. The inequality allows merging the two smallest classes when there are at least four classes. With three classes, fixing the middle class makes the objective affine in the product of the other two sizes; either merge them or balance them. Only and need remain.
Zykov symmetrization replaces one of two nonadjacent vertices by a clone of the other. Cloning the vertex of larger degree does not decrease the edge count and does not create a larger clique. Iteration reduces the extremal problem for clique-free graphs to complete multipartite graphs.
For each real , some maximizer of among graphs on vertices is complete multipartite graph. Among maximizers maximize . Cloning either of two nonadjacent vertices preserves the objective, since maximality forces their local contributions to agree. If their vertex neighbourhoods differ, the sum of the two changes in the squared-degree of a vertex objective is twice the size of their symmetric difference, a contradiction. Nonadjacency therefore partitions the vertices into classes with identical vertex neighbourhoods.
A graph-theoretic rhombus is two triangles sharing an edge. Every rhombus-free graph on vertices has at mostedges. If the graph is triangle-free this is Turán's theorem. Otherwise remove a triangle: every remaining vertex has at most one neighbor in it, and induction bounds the edge count by
.
.
The triangular prism has six vertices and nine edges. Each edge lies in at most one triangle, so it has no rhombus; its two triangles show that it is not .
An edge density exceeding the Turan theorem threshold for by a fixed positive amount forces a balanced subgraph with logarithmic part size. Combine clique supersaturation by sampling with the dense clique family blow-up lemma. Dense binomial random graphs show that the logarithmic order is optimal for a uniform density guarantee.
In a binomial random graph with fixed edge probability below one, the displayed first-moment bound tends to zero for and sufficiently large fixed . At the same time the edge density concentrates near . Thus a positive fixed density cannot force balanced complete multipartite subgraphs whose part size grows faster than logarithmically.
For fixed positive integers , a graph on vertices with and no balanced complete multipartite blow-up contains an -partite subgraph with vertices, balanced classes of size , and minimum degree of a graph .
One proof first removes a vanishing fraction of vertices of low degree of a vertex, finds a slowly growing by the Erdős-Stone theorem, and assigns almost every remaining vertex to a root class in which it has fewer than neighbours of a vertex. After discarding a further vanishing fraction, a inside an assigned class would extend to using the root classes. Thus internal edges and missing cross-class edges both number . Removing the vertices with unusually many missing cross-class edges gives the stated minimum degree of a graph.
If a fixed graph has chromatic number , every extremal -free graph on vertices has minimum degree of a graph . Use a high-minimum-degree multipartite stability subgraph : replacing any vertex by one adjacent to all but one class of preserves -freeness. Any supposed new copy of can replace the new vertex by an unused common neighbour in the omitted class. Extremality therefore gives the lower bound on every degree of a vertex; the Erdős-Stone theorem gives the upper bound on the average degree of a vertex.
For each fixed positive integer ,The standard proof counts -element subsets of graph neighbourhoods in a bipartite subgraph. If one side has degrees , the absence of givesconvexity then bounds the number of edges.
Articles by others on the same topic
Extremal graph theory is a branch of combinatorial mathematics that studies the extremal properties of graphs. Specifically, it focuses on questions related to the maximal or minimal number of edges in a graph that satisfies certain properties or conditions. The primary goal is often to determine the extremal (that is, maximum or minimum) values for specific parameters of graphs (like the number of edges, number of vertices, etc.) that meet certain constraints, such as containing a particular subgraph or avoiding certain configurations.