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.
An $(n,r,s)$-system is an $r$-uniform hypergraph on $n$ vertices such that every pair of edges has an intersection of size less than $s$. Using probabilistic arguments, R{o}dl and v{S}iv{n}ajov{a} showed that for all fixed integers $r> s ge 2$, there
exists an $(n,r,s)$-system with independence number $Oleft(n^{1-delta+o(1)}right)$ for some optimal constant $delta >0$ only related to $r$ and $s$. We show that for certain pairs $(r,s)$ with $sle r/2$ there exists an explicit construction of an $(n,r,s)$-system with independence number $Oleft(n^{1-epsilon}right)$, where $epsilon > 0$ is an absolute constant only related to $r$ and $s$. Previously this was known only for $s>r/2$ by results of Chattopadhyay and Goodman
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.
For every positive integer $t$ we construct a finite family of triple systems ${mathcal M}_t$, determine its Tur{a}n number, and show that there are $t$ extremal ${mathcal M}_t$-free configurations that are far from each other in edit-distance. We al
so prove a strong stability theorem: every ${mathcal M}_t$-free triple system whose size is close to the maximum size is a subgraph of one of these $t$ extremal configurations after removing a small proportion of vertices. This is the first stability theorem for a hypergraph problem with an arbitrary (finite) number of extremal configurations. Moreover, the extremal hypergraphs have very different shadow sizes (unlike the case of the famous Turan tetrahedron conjecture). Hence a corollary of our main result is that the boundary of the feasible region of ${mathcal M}_t$ has exactly $t$ global maxima.
A $k$-uniform hypergraph with $n$ vertices is an $(n,k,ell)$-omitting system if it does not contain two edges whose intersection has size exactly $ell$. If in addition it does not contain two edges whose intersection has size greater than $ell$, then
it is an $(n,k,ell)$-system. R{o}dl and v{S}iv{n}ajov{a} proved a lower bound for the independence number of $(n,k,ell)$-systems that is sharp in order of magnitude for fixed $2 le ell le k-1$. We consider the same question for the larger class of $(n,k,ell)$-omitting systems. For $kle 2ell+1$, we believe that the behavior is similar to the case of $(n,k,ell)$-systems and prove a nontrivial lower bound for the first open case $ell=k-2$. For $k>2ell+1$ we give new lower and upper bounds which show that the minimum independence number of $(n,k,ell)$-omitting systems has a very different behavior than for $(n,k,ell)$-systems. Our lower bound for $ell=k-2$ uses some adaptations of the random greedy independent set algorithm, and our upper bounds (constructions) for $k> 2ell+1$ are obtained from some pseudorandom graphs. We also prove some related results where we forbid more than two edges with a prescribed common intersection size and this leads to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number $r_{k}(F^{k},t)$, where $F^{k}$ is the $k$-uniform Fan. Here the behavior is quite different than the case $k=2$ which reduces to the classical graph Ramsey number $r(3,t)$.
A conjecture of Chung and Graham states that every $K_4$-free graph on $n$ vertices contains a vertex set of size $lfloor n/2 rfloor$ that spans at most $n^2/18$ edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.
A hypergraph $mathcal{F}$ is non-trivial intersecting if every two edges in it have a nonempty intersection but no vertex is contained in all edges of $mathcal{F}$. Mubayi and Verstra{e}te showed that for every $k ge d+1 ge 3$ and $n ge (d+1)n/d$ eve
ry $k$-graph $mathcal{H}$ on $n$ vertices without a non-trivial intersecting subgraph of size $d+1$ contains at most $binom{n-1}{k-1}$ edges. They conjectured that the same conclusion holds for all $d ge k ge 4$ and sufficiently large $n$. We confirm their conjecture by proving a stronger statement. They also conjectured that for $m ge 4$ and sufficiently large $n$ the maximum size of a $3$-graph on $n$ vertices without a non-trivial intersecting subgraph of size $3m+1$ is achieved by certain Steiner systems. We give a construction with more edges showing that their conjecture is not true in general.
The classical Kruskal-Katona theorem gives a tight upper bound for the size of an $r$-uniform hypergraph $mathcal{H}$ as a function of the size of its shadow. Its stability version was obtained by Keevash who proved that if the size of $mathcal{H}$ i
s close to the maximum, then $mathcal{H}$ is structurally close to a complete $r$-uniform hypergraph. We prove similar stability results for two classes of hypergraphs whose extremal properties have been investigated by many researchers: the cancellative hypergraphs and hypergraphs without expansion of cliques.
The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers $s,t$ and an $n$-vertex graph $G$ with $lfloor n^2/4 rfloor +t$ edges and triangle covering number $s$, we determine (for large
$n$) sharp bounds on the minimum number of triangles in $G$ and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, ErdH os, and Lovasz-Simonovits whose results apply only to $s le t$. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture.
A fundamental result in extremal set theory is Katonas shadow intersection theorem, which extends the Kruskal-Katona theorem by giving a lower bound on the size of the shadow of an intersecting family of $k$-sets in terms of its size. We improve this
classical result and a related result of Ahlswede, Aydinian, and Khachatrian by proving tight bounds for families that can be quite small. For example, when $k=3$ our result is sharp for all families with $n$ points and at least $3n-7$ triples. Katonas theorem was extended by Frankl to families with matching number $s$. We improve Frankls result by giving tight bounds for large $n$.
