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

The full text of this article is unavailable through your IP address: 3.135.205.164

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