Tight Staircase Bounds for Cyclic Subsets below Dirac's Threshold

Abstract

Let $\mathrm{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 $\hat{I}\text{c◯}(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=\hat{I}\text{c◯}(n)$ and $d<n/2$, then $$\mathrm{Cyc}(G)\ge (q-o(1))2^{n/q},\text{where }q=\lfloor \frac{n}{d+1}\rfloor \ge 2.$$ This bound is asymptotically best possible, including the leading coefficient $q$, as witnessed at the staircase levels by the disjoint union of $q$ equal cliques. Consequently, the optimal exponential rate changes by discrete jumps as $d$ crosses the thresholds $n/k$, rather than varying smoothly with $d$. We also prove the optimal exponential rate at the Dirac boundary: every $n$-vertex $n/2$-regular graph satisfies $\mathrm{Cyc}(G)\ge 2^{(1-o(1))n},$ which is sharp up to a subexponential factor by $K_{n/2,n/2}$.