MR_t(s,k) bound for Ks-free graphs
Conjecture on $MR_t(s,k)$ for $s \geq 4$ · arXiv:1907.12999
Status open medium confidence
The conjecture that $MR_t(s,k) \leq t^{1-\varepsilon}k$ for $s \geq 4$ and sufficiently large $t$ (with tightness at $\varepsilon = 1/s$) remains open. The source paper (arXiv:1907.12999) establishes the $s=3$ case (triangle-free) and appeared in Proceedings of the AMS in 2025, but no follow-up resolving or substantially advancing the $s \geq 4$ case was found in the indexed literature. The internal candidate reference (arXiv:2206.13635) addresses hypergraph coloring with excluded minors and does not engage with $MR_t(s,k)$ or independence numbers in $K_s$-free graphs.
Reviewer notes. No follow-up resolving the $s \geq 4$ case was found after 5+ web queries. The paper was published in Proc. Amer. Math. Soc. (2025) — an AMS proceedings URL was found but returned HTTP 403. Confidence is medium rather than high because the conjecture dates to 2019 (nearly 7 years old), making the absence of a follow-up in this search less conclusive than for a very recent conjecture. The Semantic Scholar API indicated ~4 citing papers but their titles/content could not be fully retrieved within the call budget.
Context
The paper's main result (Theorem 1) establishes $MR_t(3,k) \leq t^{1-\varepsilon}k$ for any $0 < \varepsilon < 1/26$ and all sufficiently large $t$; Erdős's construction (Theorem 2) shows $\varepsilon \leq 1/3$ is essentially tight for $s=3$. The authors conjecture in Section 4 that an analogous upper bound holds for $K_s$-free graphs with $s \geq 4$, with tightness at $\varepsilon = 1/s$.
Notes. Section 4 is not included in the provided text; this conjecture is described only by a forward reference in the introduction. The exact formal statement may differ from what is reconstructed here.
Source paper
Independence number in triangle-free graphs avoiding a minor
Zdeněk Dvořák, Liana Yepremyan · 2019-07-30
https://arxiv.org/abs/1907.12999
PDF source