Suppose G has n vertices and no induced copy of H

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

All graphs here are finite and simple. For a graph $G$, let $\alpha(G)$ be the maximum size of an independent vertex set and $\omega(G)$ the maximum size of a clique. An induced copy of $H$ in $G$ is an injective vertex map preserving both adjacency and nonadjacency; $G$ is $H$-free if no such copy exists. Its homogeneous number is $h(G)=\max\{\alpha(G),\omega(G)\}$.

Statement recorded in the supplied source.

For every fixed graph $H$, does there exist $\varepsilon(H)>0$ such that every $H$-free graph $G$ with $n\geq1$ vertices satisfies $h(G)\geq n^{\varepsilon(H)}$? The recorded example $H=C_5$ means the five-vertex cycle; that instance was subsequently proved in the cited 2021 paper. [S2]

Short English statement

For each forbidden induced graph, must every graph avoiding it have a clique or independent set of polynomial size? The five-cycle instance is established.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3100015 (AMR-030-0015). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Maria Chudnovsky, Alex Scott, Paul Seymour and Sophie Spirkl, Erdos--Hajnal for Graphs with No 5-hole (2021), abstract and section 1, Conjecture 1.1 and the five-cycle result. https://arxiv.org/abs/2102.04994.