Multicolour Erdős--Hajnal Conjecture

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.

For an integer $r\geq1$, $K_r$ denotes the complete graph on $r$ vertices. Fix $k\geq2$ and $m\geq2$, and a pattern $\chi:E(K_k)\to\{1,\ldots,m\}$. A colour-preserving copy in $c:E(K_n)\to\{1,\ldots,m\}$ is an injection $\phi:V(K_k)\to V(K_n)$ with $c(\phi(u)\phi(v))=\chi(uv)$ for every $uv\in E(K_k)$. A vertex subset omits a colour if its induced edges use at most $m-1$ colours.

Statement recorded in the supplied source.

For every fixed pattern $\chi$, is there an $\varepsilon>0$ such that, for every integer $n\geq1$, every $m$-colouring of $E(K_n)$ either contains a colour-preserving copy of $\chi$ or has a subset $S\subseteq V(K_n)$ with $|S|\geq n^\varepsilon$ whose induced edges omit a colour? [S2] [S3]

Short English statement

Must avoiding a fixed coloured clique force a polynomially large vertex set missing at least one of the available colours?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3289 (OPG-60042). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Multicolour Erdős--Hajnal Conjecture, node 60042, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/multicolour_erdos_hajnal_conjecture.
• S3 Maria Axenovich and Lea Weber, A note on multicolour Erdős--Hajnal conjecture (2023), Section 1, definitions of a copy and a homogeneous set. https://arxiv.org/pdf/2311.03249.