{"id":"arxiv/2607.06551","url":"https://arxiv.org/abs/2607.06551","tags":["math.CO"],"score":0,"title":"Tight Staircase Bounds for Cyclic Subsets below Dirac's Threshold","domain":"math.CO","source":"arxiv","authors":["Hong Liu","Mengyuan Niu","Lanchao Wang","Zhifei Yan"],"reviews":0,"subject":"math.CO","summary":"Let $\\operatorname{Cyc}(G)$ denote the number of cyclic subsets in a graph $G$, which are subsets that induce a Hamiltonian subgraph. Draganić, Keevash and Müyesser recently proved that every regular Dirac graph has $Ω(2^n)$ cyclic subsets, resolving a problem of Erdős and Faudree. We determine the sharp asymptotic lower bound throughout the linear range below Dirac's threshold. Let $G$ be an $n$-vertex $d$-regular graph with $d=Ω(n)$ and $d<n/2$, then $$ \\operatorname{Cyc}(G)\\ge (q-o(1))2^{n/q}, \\quad \\text{where } \\quad q=\\left\\lfloor \\frac{n}{d+1}\\right\\rfloor \\ge 2. $$ This bound is…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-07","reactions":{}}