Absolutely avoidable order-size pairs in hypergraphs

Abstract: For fixed integer

r g e 2

, we call a pair

(m, f)

of integers,

m g e q 1

,

a b s o l u t e l y

a v o i d a b l e

if there is

n_{0}

, such that for any pair of integers

(n, e)

with

n > n_{0}

and

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 g e 3

and

m g e m_{0}

, either the pair

or the pair

is absolutely avoidable. Next, following the definition of ErdH{o}s, F"uredi, Rothschild and S'os, we define the

d e n s i t y

of a pair

(m, f)

as

. We show that for

r g e 3

most pairs

(m, f)

satisfy

s i g m a_{r} (m, f) = 0

, and that for

m > r

, there exists no pair

(m, f)

of density 1.

Recommendations

Cited in

(3)

This page was built for publication: Absolutely avoidable order-size pairs in hypergraphs