Independence ratio of Mycielski graphs
Open problem on minimum independence ratio of Mycielski graphs · arXiv:1907.11429
Status open high confidence
The exact value of the minimum independence ratio mir(M_k) of Mycielski graphs remains unknown. Cropper, Gyárfás, and Lehel (Discrete Mathematics, 2006) established asymptotic bounds c_1·sqrt(log m)/m ≤ mir(M_s) ≤ c_2·log(m)/m (where s = R(3,m)−1), and small exact values (mir(M_2)=1/2, mir(M_3)=1/5) are known, but no general exact formula has been found. Multiple literature searches across 2020–2026 confirm no subsequent paper has resolved this open problem.
Reviewer notes. No follow-up resolving the exact formula was found. The Cropper–Gyárfás–Lehel paper (Discrete Math. 306, 2006, pp. 1988–1990) provides the best known asymptotic bounds. The problem is closely related to the Hall ratio of Mycielski graphs. The open problem arises in the source paper in the context of why a natural generalisation of Folkman's theorem (replacing constant 2 by a larger integer k) fails.
Context
While Cropper, Gyárfás and Lehel [CGL06] established asymptotic bounds $c_1 \cdot \frac{\sqrt{\log m}}{m} \leq \mathrm{mir}(M_s) \leq c_2 \cdot \frac{\log m}{m}$ for every integer $m > 3$ (where $s$ is one less than the Ramsey number $R(3,m)$), no exact formula for $\mathrm{mir}(M_k)$ is known. The authors flag this gap while discussing why replacing the constant $2$ by a larger integer $k$ fails to generalise Observation 1.1.
Notes. Stated informally in passing ('seems to be unknown'); no labelled environment. Question 1.2 is posed in the paper but immediately resolved negatively and so is not extracted as an open problem.
Source paper
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwenaël Joret, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor, Jean-Sébastien Sereni · 2020-03-23
https://arxiv.org/abs/1907.11429
PDF source