The feasible region $Omega_{{rm 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 des
cription of $Omega_{{rm 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)in Omega_{{rm ind}}(F)$ is the inducibility of $F$ and $Omega_{{rm ind}}(K_r)$ yields the Kruskal-Katona and clique density theorems. We begin a systematic study of $Omega_{{rm ind}}(F)$ by proving some general statements about the shape of $Omega_{{rm 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 Bollobas for the number of cliques in a graph with given edge density. We also consider the problems of determining $Omega_{{rm 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 $Omega_{{rm ind}}(C_4)$ is determined by the solution to the triangle density problem, which has been solved by Razborov.
We present a method which provides a unified framework for most stability theorems that have been proved in graph and hypergraph theory. Our main result reduces stability for a large class of hypergraph problems to the simpler question of checking th
at a hypergraph $mathcal H$ with large minimum degree that omits the forbidden structures is vertex-extendable. This means that if $v$ is a vertex of $mathcal H$ and ${mathcal H} -v$ is a subgraph of the extremal configuration(s), then $mathcal H$ is also a subgraph of the extremal configuration(s). In many cases vertex-extendability is quite easy to verify. We illustrate our approach by giving new short proofs of hypergraph stability results of Pikhurko, Hefetz-Keevash, Brandt-Irwin-Jiang, Bene Watts-Norin-Yepremyan and others. Since our method always yields minimum degree stability, which is the strongest form of stability, in some of these cases our stability results are stronger than what was known earlier. Along the way, we clarify the different notions of stability that have been previously studied.
Combining two classical notions in extremal combinatorics, the study of Ramsey-Turan theory seeks to determine, for integers $mle n$ and $p leq q$, the number $mathsf{RT}_p(n,K_q,m)$, which is the maximum size of an $n$-vertex $K_q$-free graph in whi
ch every set of at least $m$ vertices contains a $K_p$. Two major open problems in this area from the 80s ask: (1) whether the asymptotic extremal structure for the general case exhibits certain periodic behaviour, resembling that of the special case when $p=2$; (2) constructing analogues of Bollobas-ErdH{o}s graphs with densities other than $1/2$. We refute the first conjecture by witnessing asymptotic extremal structures that are drastically different from the $p=2$ case, and address the second problem by constructing Bollobas-ErdH{o}s-type graphs using high dimensional complex spheres with all rational densities. Some matching upper bounds are also provided.
By a finite type-graph we mean a graph whose set of vertices is the set of all $k$-subsets of $[n]={1,2,ldots, n}$ for some integers $nge kge 1$, and in which two such sets are adjacent if and only if they realise a certain order type specified in ad
vance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz {L}uczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture.
