Absolutely avoidable order-size pairs in hypergraphs

For a fixed integer $r \geq 2$, we call a pair $(m,f)$ of integers, $m \geq 1$, $0\leq f \leq \binom{m}{r}$, absolutely avoidable if there is $n_{0}$, such that for any pair of integers $(n,e)$ with $n \gt n_{0}$ and $0\leq e \leq \binom{n}{r}$ there is an $r$-uniform hypergraph on $n$ vertices and $e$ edges that contains no induced sub-hypergraph on $m$ vertices and $f$ edges. Some pairs are clearly not absolutely avoidable, for example $(m,0)$ is not absolutely avoidable since any sufficiently sparse hypergraph on at least $m$ vertices contains independent sets on $m$ vertices. Here we show that for any $r \geq 3$ and $m \geq m_{0}$, either the pair $(m, \left \lfloor{\binom mr/2}\right \rfloor )$ or the pair $(m, \left \lfloor{\binom{m}{r}/2}\right \rfloor -m-1)$ is absolutely avoidable.

Next, following the definition of Erdős, Füredi, Rothschild and Sós, we define the density of a pair $(m,f)$ as\[\sigma _{r}(m,f) = \limsup _{n \to \infty} \frac{|\{e : (n,e) \to (m,f)\}|}{\binom mr} \quad \textrm{,}\]where $(n,e) \to (m,f)$ if any $n$-vertex $r$-graph with $e$ edges contains an induced $m$-vertex subgraph with $f$ edges. We show that for $ r \geq 3$ most pairs $(m,f)$ satisfy $\sigma_{r}(m,f)=0$, and that for $m \gt r$, there exists no pair $(m,f)$ of density $1$.

Full Text (PDF format)

The author’s research was partially supported by the DFG grant FKZ AX 93/2-1.

Received 1 August 2022

Accepted 13 March 2023

Published 23 January 2024