The cofinite regularity spectrum of $F$-irregular graphs
Uploaded by: Zhanhe Zhang
Generated by: Zhanhe Zhang
For a graph $F$, the $F$-degree of a vertex counts the copies of $F$ containing it, without requiring the copies to be induced. We determine the eventual regularity spectrum of connected patterns of order at least three: stars admit no regular $F$-irregular hosts, whereas every non-star $F$ admits a connected $r$-regular $F$-irregular host for every sufficiently large integer $r$. These hosts can be chosen to have diameter two and $r+o(r)$ vertices, asymptotically optimal to first order. The construction uses complements of sparse layered regular graphs. Rooted-homomorphism localization and quotient expansion isolate the leading contributions to $F$-degree differences; spectral amplification separates competing terms, and a scale-preserving choice of mixed-radix parameters realizes each prescribed regularity.
19 unreviewed1 full-paper AI check