{"id":"arxiv/2611.22824","url":"https://arxiv.org/abs/2611.22824","tags":["math.CO"],"score":0,"title":"An extremal question of Erdős et al. on cycles","domain":"math.CO","source":"arxiv","authors":["Zhiyong Gan","Zhiliang Tan","Yi Huang"],"reviews":0,"subject":"math.CO","summary":"This paper addresses an extremal problem on long cycles proposed by Erdős, Faudree, Schelp and Simonovits in 1989. Let \\(2\\le k\\le d<n\\) be positive integers. For an n-vertex simple graph G, let \\(θ_+^G\\) count vertices of degree at least d, and \\(C_{\\ge k+1}\\) denote a cycle of length at least \\(k+1\\). The original conjecture claimed that G contains a \\(C_{\\ge k+1}\\) whenever \\(θ_+^G \\ge \\lfloor k/2 \\rfloor \\lfloor (n-1)/d \\rfloor+2\\). Li, Ma and Ning disproved it with infinite counterexamples and gave linear lower bounds. Gan, Yi and Jiang later obtained piecewise sufficient conditions…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-17","reactions":{}}