Journal of Combinatorics

Volume 15 (2024)

Number 1

Absolutely avoidable order-size pairs for induced subgraphs

Pages: 41 – 57

DOI: https://dx.doi.org/10.4310/JOC.2024.v15.n1.a2

Authors

Maria Axenovich (Karlsruhe Institute of Technology, Karlsruhe, Germany)

Lea Weber (Karlsruhe Institute of Technology, Karlsruhe, Germany)

Abstract

We call a pair $(m, f)$ of integers, $m \geq 1, 0 \leq f \leq \binom{m}{2}$, 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}{2}$ 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 \in M$, the pair $(m, \binom{m}{2} / 2)$ is absolutely avoidable. In addition, among other results, we show that for any integer function $q(m)$ for which the limit $\lim\limits _{m \to \infty} \frac{q(m)}{m}$ exists, there are infinitely many values of $m$ such that the pair $(m, \binom{m}{2}/2 +q(m))$ is absolutely avoidable.

Keywords

order, size, induced subgraphs, number of edges

2010 Mathematics Subject Classification

Primary 05C35. Secondary 05C75.

The full text of this article is unavailable through your IP address: 3.235.172.123

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

Received 4 August 2021

Accepted 5 September 2022

Published 7 November 2023