Maximum $\mathcal{H}$-free subgraphs

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 $\lbrace \mathcal{H}_m \rbrace$ 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 $\lbrace \mathcal{H}_m \rbrace$ for which $f(m,\mathcal{H}_m)$ is bounded seems hopeless.

Keywords

extremal set theory, family of hypergraphs, hypergraphs

2010 Mathematics Subject Classification

05C35, 05C65, 05D05

Full Text (PDF format)

The research of Dhruv Mubayi was partially supported by NSF grants DMS-1300138 and 1763317.

Received 21 May 2019

Accepted 6 May 2020

Published 16 July 2021