Supersaturation problem for color-critical graphs

Abstract: The emph{Tur'an function}

e x (n, F)

of a graph

F

is the maximum number of edges in an

F

-free graph with

n

vertices. The classical results of Tur'an and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine

h_{F} (n, q)

, the minimum number of copies of

F

that a graph with

n

vertices and

e x (n, F) + q

edges can have. We determine

h_{F} (n, q)

asymptotically when

F

is emph{color-critical} (that is,

F

contains an edge whose deletion reduces its chromatic number) and

q = o (n^{2})

. Determining the exact value of

h_{F} (n, q)

seems rather difficult. For example, let

c_{1}

be the limit superior of

q / n

for which the extremal structures are obtained by adding some

q

edges to a maximum

F

-free graph. The problem of determining

c_{1}

for cliques was a well-known question of ErdH os that was solved only decades later by Lov'asz and Simonovits. Here we prove that

c_{1} > 0

for every {color-critical}~

F

. Our approach also allows us to determine

c_{1}

for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.

Recommendations

Cites Work

Cited In (11)

This page was built for publication: Supersaturation problem for color-critical graphs