Off-Diagonal Induced Ramsey Numbers

Source: arxiv.org/abs/2611.06886

Bruno Andrades, Marcelo Campos, Rafael Filipe, Anastasiia Kats

arXivarxiv/2611.06886Nov 4, 2026math.COscore 0

Given graphs $F$ and $H$, the induced Ramsey number $r_{\mathrm{ind}}(F,H)$ is the smallest integer $n$ for which there exists a graph $G$ on $n$ vertices such that every red-blue colouring of $E(G)$ contains either a blue induced copy of $F$ or a red induced copy of $H$. A conjecture of Kohayakawa, Prömel and Rödl asserts that, for every fixed graph $F$, this number is polynomial in $v(H)$. We prove this conjecture, showing that there is an absolute constant $C > 0$ such that $$r_{\mathrm{ind}}(F,H) \leq v(H)^{Cv(F)^2}$$ for all graphs $F$ and $H$. The proof combines a variant of a random…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.06886
curl -X POST /api/v1/records/arxiv/2611.06886/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06886/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'