Extremal Hypergraph Problems

This thesis studies extremal problems in hypergraph theory, set theory, and graph theory. Results in this thesis can be divided into seven parts. In the first part, we study the feasible region $\Omega(\mathcal{F})$ of a hypergraph family $\mathcal{F}$, which is the set of points $(x,y)$ so that there exists a sequence of $\mathcal{F}$-free $r$-graphs whose shadow densities approach $x$ and whose edge densities approach $y$. We prove some general results about the shape of $\Omega(\mathcal{F})$, and study $\Omega(\mathcal{F})$ for some specific examples such as the cancellative hypergraphs and the expansion of cliques. In the second part, we present a unified framework for proving stability theorems in graph and hypergraph theory. Our main result reduces stability for a large class of hypergraph Tur\'{a}n problems to the simpler question of checking that a hypergraph $\mathcal H$ with large minimum degree that omits the forbidden structures is vertex-extendable. We illustrate our method by giving new short proofs to many stability theorems. In the third part, we provide a construction of finite hypergraph families that have arbitrarily (but finite) many extremal configurations. This is the first such construction. Before our work, every family of hypergraphs whose Tur\'{a}n density is known has a unique extremal configuration. In the fourth part, we study problems that are generalizations of the celebrated Erd\H{o}s--Ko--Rado theorem. We give the correct bounds for the size of a family that does not contain a $d$-cluster but contains at least two disjoint edges. This resolves a conjecture of Mammoliti and Britz. We also extend a structural theorem due to Frankl about conditionally intersecting $3$-graphs to the general case, and use it to give new proofs to some theorems in Extremal set theory. Extending the celebrated Katona intersecting shadow theorem, we give tight bounds for the size of the shadow of $t$-intersecting families and families with a bounded matching number. Finally, resolving a conjecture of Mubayi and Verstra\"{e}te, we determine the maximum size of a family that does not contain nontrivial intersecting subgraphs. In the fifth part, we study some extensions of the Tur\'{a}n theorem in Graph theory. We determine the minimum number of copies of a color-critical graph $F$ in a graph with fixed number of edges and fixed $F$-covering number. We also consider the local density problem in $K_4$-free graphs and prove a conjecture of Chung and Graham, and independently, Erd\H{o}s, Faudree, Rousseau, and Schelp for all almost-regular $K_4$-free graphs. In the sixth part, we study the independence number of hypergraps that omit just one intersection. This is related to R\"{o}dl and \v{S}i\v{n}ajov\'{a}'s result on the independence number of $(n,k,\ell)$-systems. We also show some explicit constructions of $(n,k,\ell)$-systems with small independence number. Such constructions are usually very useful in theoretical computer science. In the last part, we study the feasible region $\Omega_{\mathrm{ind}}(F)$ of induced graphs $F$, which is the set of points $(x,y)$ so that there exists a sequence of graphs whose edge density approaches $x$ and whose induced $F$-density approaches $y$. We prove some general results about the shape of $\Omega_{\mathrm{ind}}(F)$, and study $\Omega_{\mathrm{ind}}(F)$ for some specific examples such as complete bipartite graphs and complete graphs minus one edge $K_{r}^{-}$. Our results on $K_{r}^{-}$ sharpen those predicted by the edge-statistics conjecture of Alon et.\ al.\