Which graphs are extremal graphs?

Опубликовано 6 сентября 2016, 16:35

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