Absolutely avoidable order-size pairs in hypergraphs

Lea Weber

paper

Absolutely avoidable order-size pairs in hypergraphs

arXiv:2205.15197

Abstract

For fixed integer $r \geq 2$ , we call a pair $(m, f)$ of integers, $m \geq 1$ , $0 \leq f \leq (r m)$ , $ab so l u t e l y$ $a v o i d ab l e$ if there is $n_{0}$ , such that for any pair of integers $(n, e)$ with $n > n_{0}$ and $0 \leq e \leq (r n)$ 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, ⌊ (r m) /2 ⌋)$ or the pair $(m, ⌊ (r m) /2 ⌋ - m - 1)$ is absolutely avoidable. Next, following the definition of Erdős, Füredi, Rothschild and Sós, we define the $d e n s i t y$ of a pair $(m, f)$ as $σ_{r} (m, f) = lim sup_{n \to \infty} \frac{∣ { e : ( n , e ) \to ( m , f )} ∣}{( r m )}$ . We show that for $r \geq 3$ most pairs $(m, f)$ satisfy $σ_{r} (m, f) = 0$ , and that for $m > r$ , there exists no pair $(m, f)$ of density 1.