Tight Staircase Bounds for Cyclic Subsets below Dirac's Threshold

Hong Liu, Mengyuan Niu, Lanchao Wang, Zhifei Yan

arXivarxiv/2607.06551Jul 7, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

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