The full text of this article is unavailable through your IP address: 185.93.229.3
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