Contents Online

# Journal of Combinatorics

## Volume 12 (2021)

### Number 2

### Maximum $\mathcal{H}$-free subgraphs

Pages: 185 – 214

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n2.a1

#### Authors

#### 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 $\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 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