Absolutely avoidable order-size pairs for induced subgraphs

Publication date 15 November 2023

Abstract: We call a pair

(m, f)

of integers,

m g e q 1

,

, emph{absolutely avoidable} if there is

n_{0}

such that for any pair of integers

(n, e)

with

n > n_{0}

and

there is a graph on

n

vertices and

e

edges that contains no induced subgraph 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 graph on at least

m

vertices contains independent sets on

m

vertices. Here we show that there are infinitely many absolutely avoidable pairs. We give a specific infinite set

M

such that for any

m i n M

, the pair

is absolutely avoidable. In addition, among other results, we show that for any monotone integer function

q (m)

,

| q (m) | = O (m)

, there are infinitely many values of

m

such that the pair

is absolutely avoidable.

Recommendations

Cited in

(5)

This page was built for publication: Absolutely avoidable order-size pairs for induced subgraphs