Search

The feasible region Ω ind (F) of a graph F is the collection of points (x , y) in the unit square such that there exists a sequence of graphs whose edge densities approach x and whose induced F -densities approach y. A complete description of Ω ind (F) is not known for any F with at least four vertices that is not a clique or an independent set. The feasible region provides a lot of combinatorial information about F. For example, the supremum of y over all (x , y) ∈ Ω ind (F) is the inducibility of F and Ω ind (K r) yields the Kruskal-Katona and clique density theorems. We begin a systematic study of Ω ind (F) by proving some general statements about the shape of Ω ind (F) and giving results for some specific graphs F. Many of our theorems apply to the more general setting of quantum graphs. For example, we prove a bound for quantum graphs that generalizes an old result of Bollobás for the number of cliques in a graph with given edge density. We also consider the problems of determining Ω ind (F) when F = K r − , F is a star, or F is a complete bipartite graph. In the case of K r − our results sharpen those predicted by the edge-statistics conjecture of Alon et al. while also extending a theorem of Hirst for K 4 − that was proved using computer aided techniques and flag algebras. The case of the 4-cycle seems particularly interesting and we conjecture that Ω ind (C 4) is determined by the solution to the triangle density problem, which has been solved by Razborov. [ABSTRACT FROM AUTHOR]