Which graphs are extremal graphs?

Consider a problem in extremal graph theory of the following type: find the maximum density of a subgraph F in a graph, where the density of one or more other subgraphs are fixed. More generally, we may want to maximize some linear combination of densities of various graphs. In almost all cases when the answer is known, the extremal graph has a finite structure, at least asymptotically: the nodes can be partitioned into subsets with given proportions, and the subgraphs between these classes are quasirandom with given densities. Is this always so?

To get a cleaner formulation of this, we formulate the question in terms of limits of growing graph sequences, which can be described by 2-variable measurable symmetric functions from [0,1]2 to [0,1]. The density of any finite simple graph in asuch a function can be defined in a natural way. Then the above problem leads to the following: which functions are “finitely forcible”, i.e., uniquely determined by a finite number of subgraph densities?

With Vera Sos we proved that every stepfunction is finitely forcible.
Somewhat surprisingly, the converse is not true, and one can find quite general classes of finitely forcible functions (each of which describes the asymptotic structure of an extremal graph). We offer some necessary and some sufficient conditions. A complete characterization seems difficult (but perhaps not hopeless).

This is joint work with Balazs Szegedy.

Date:
Speakers:
Laszlo Lovasz
Affiliation:
Renyi Institute
    • Portrait of Jeff Running

      Jeff Running