OPENHARDgraph theoryextremal graph theory
The cycle set of a graph $G$ on $n$ vertices is $A\subseteq \{3,\ldots,n\}$ such that $G$ has a cycle of length $\ell$ iff $\ell \in A$. Let $f(n)$ count possible cycle sets. Prove $f(n)=o(2^n)$ and $f(n)/2^{n/2}\to \infty$.
Notes: Verstraete proved f(n) << 2^{n - n^{1/10}}. Nenadov improved to f(n) << 2^{n - n^{1/2-o(1)}}. The limit of f(n)^{1/n} remains unknown.
AI Status: NONE · 0 total attempts