Maximum $\mathcal{H}$-free subgraphs

Abstract

Given a family of hypergraphs $\mathcal{H}$, let $f(m,\mathcal{H})$ denote the largest size of an $\mathcal{H}$-free subgraph that one is guaranteed to find in every hypergraph with $m$ edges. This function was first introduced by Erdős and Komlós in 1969 in the context of union-free families, and various other special cases have been extensively studied since then. In an attempt to develop a general theory for these questions, we consider the following basic issue: which sequences of hypergraph families $\{{\mathcal{H}}_m\}$ have bounded $f(m,{\mathcal{H}}_m)$ as $m\to \infty$? A variety of bounds for $f(m,{\mathcal{H}}_m)$ are obtained which answer this question in some cases. Obtaining a complete description of sequences $\{{\mathcal{H}}_m\}$ for which $f(m,{\mathcal{H}}_m)$ is bounded seems hopeless.

References in corpus (2)

• Large subgraphs without short cycles
• Large subgraphs without complete bipartite graphs