2022/05/30 by Weber, Lea
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2205.15197
For fixed integer r≥ 2, we call a pair (m,f) of integers, m≥ 1, 0≤ f ≤ \binommr, absolutely avoidable if there is n0, such that for any pair of integers (n,e) with n>n0 and 0≤ e≤ \binomnr 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≥ 3 and m ≥ m0, either the pair (m, \lfloor\binom mr/2\rfloor) or the pair (m, \lfloor\binommr/2\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 σr(m,f) = \limsupn → ∞ \frac|\e : (n,e) → (m,f)\|\binom mr. We show that for r≥ 3 most pairs (m,f) satisfy σr(m,f)=0, and that for m > r, there exists no pair (m,f) of density 1.