The cofinite regularity spectrum of $F$-irregular graphs

Public text index for scholarly discovery. It mirrors theorem, lemma, proposition and related statements from this immutable version and does not imply human verification.

1. Theorem 1.1: Cofinite regularity spectrum
   PF:2026.000018/v1/THM-1.1

   Let $F$ be a finite, simple, connected graph with at least three vertices. If $F$ is a star, then $\Spec(F)=\varnothing$. Otherwise there exists an integer $r_F$ such that for \emph{every} integer $r\ge r_F$ there is a finite simple connected $r$-regular $F$-irregular graph $G_r$ of diameter exactly two. Moreover, the hosts can be chosen so that $|V(G_r)|/r\to1$ as $r\to\infty$.

2. Corollary 1.2: Existence classification
   PF:2026.000018/v1/COR-1.2

   A finite connected graph $F$ of order at least three admits a connected regular $F$-irregular host if and only if $F$ is not a star. In the non-star case there are infinitely many such hosts of odd regularity and infinitely many of even regularity, each of diameter two.

3. Lemma 2.1: Seed certificates
   PF:2026.000018/v1/LEM-2.1

   There exist graphs satisfying the following properties. \item Two complementary $125$-vertex $62$-regular graphs $A,B$ whose combined $250$ rooted triangle counts are pairwise distinct, with total span $932$. \item The $31250$-vertex $7812$-regular graph H_0=A[A]\ \dot\cup\ B[B] has $31250$ pairwise distinct rooted triangle counts, with total span at most $14\,563\,432$. \item Two $1250$-vertex $310$-regular bipartite graphs $U,V$ with disjoint edge sets under a common vertex labeling. Their $2500$ rooted four-cycle counts are pairwise distinct and have total span $834\,684$.

4. Lemma 4.1: Triangle invariance
   PF:2026.000018/v1/LEM-4.1

   With $R$ as in (equation reference), all new terms in $\diag(A_R^3-A_{R_0}^3)$ are constant across the vertices. In particular, \Delta\tau_R=\Delta\tau_{R_0} for every two roots.

5. Lemma 4.2: Four-cycle separation under layered connections
   PF:2026.000018/v1/LEM-4.2

   Take $k$ positions from the two $1250$-vertex seeds $U,V$ of Lemma 2.1, with $\ell\le k$, using color $e_i$ at position $i<\ell$ and fixed color $0$ thereafter. Use any collection of distinct connection generators with a fixed bounded count at each proper level. Then $\tau_R$ is constant, and for every pair of roots \Delta c_4^R=\Delta c_4^{R_0},\qquad |\Delta c_4^R|\ge\left(1-\frac{834\,684}{1250^3-1}\right)u^3.

6. Lemma 5.1: Common block average after root alignment
   PF:2026.000018/v1/LEM-5.1

   Let $R$ be an auxiliary graph constructed in \hyperref[sec:wiring]{Section reference}. Fix roots $v=(e,x)$ and $w=(f,y)$, and let $\istar$ be their highest unequal absolute coordinate. Partition $V(R)$ by the word-block label and the letters strictly above $\istar$; every block has size $L_*=q_{\istar+1}$. There is a vertex permutation $\varphi$ with $\varphi(v)=w$ such that the relabeled adjacency matrix \[ A'_R(z,z')=A_R(\varphi(z),\varphi(z')) \] has the same blockwise average $\mathcal U$ as $A_R$. Write $K=A_R-\mathcal U$ and $K'=A'_R-\mathcal U$, and put \[ \omega_*=D_{\istar+1}+\sum_{s:a_s\le\istar}q_{a_s}. \] Then every block of $K$ and $K'$ has zero row and column sums, \[ 0\le\mathcal U(z,z')\le1,\…

7. Theorem 5.2: Rooted localization
   PF:2026.000018/v1/THM-5.2

   Fix regular seed alphabets with orders $2\le n_i\le n_{\max}$ and degrees independent of color at each position. Suppose each proper connection level $a<P$ carries at most $M_*$ generators; the number at level $P$ is unrestricted. Let $v,w$ be roots of an auxiliary graph $R$ from \hyperref[sec:wiring]{Section reference}, with highest unequal coordinate $\istar$, and set $u=q_{\istar}$. For any fixed connected rooted graph $(H,a)$ of order $h_H$: \item if $H$ is a tree, $\Hom_v(H,a;R)=\Hom_w(H,a;R)$; \item if $H$ contains a cycle, then |\Delta\Hom(H,a;R)| \le C_{H,M_*}\omega^{h_H-g(H)}u^{g(H)-1}. The constant may depend on the fixed alphabets, $H$ and $M_*$, but not on $P,\ell$, the selected generators or the…

8. Lemma 6.1: Rooted complement identity
   PF:2026.000018/v1/LEM-6.1

   If $G=\overline R$ has order $N\ge2h$, where $h=|V(F)|$, then for any two roots in $G$, a_F\Delta d_F^G =\sum_{\varnothing\ne E'\subseteq E(F)}(-1)^{|E'|} (N-s-1)_{h-s}\,\Delta I_J, where $(x)_m=x(x-1)\cdots(x-m+1)$ for $m\ge1$ and $(x)_0=1$.

9. Lemma 6.2: Quotient-order bound
   PF:2026.000018/v1/LEM-6.2

   Fix $F$ and two roots at suffix scale $u$. Let a quotient of an edge support $J$ have $m$ vertices, $c$ nontrivial connected components and identification defect $d=s-m$. Let $H$ be the quotient component containing the distinguished root. If $H$ has a cycle, choose an integer $q$ with $3\le q\le g(H)$. The contribution of this rooted quotient to (equation reference) is bounded by C_FN^{h-q-d}\left(\frac\omega N\right)^{m-c-q+1}u^{q-1}, \qquad m-c-q+1\ge0. A quotient with the root in a tree component makes no contribution to the root difference.

10. Lemma 6.3: Leading types
    PF:2026.000018/v1/LEM-6.3

    Let $F$ be connected and $h=|V(F)|$. \item If $F$ contains a triangle, the only root-dependent zero-loss type at scale $N^{h-3}u^2$ is an uncontracted triangle support. Summing over these supports gives coefficient $-6c_3(F)$ multiplying $\Delta\tau_R$. \item If $F$ is triangle-free and contains a $P_4$, the only root-dependent zero-loss type among non-discrete quotients at scale $N^{h-4}u^2$ identifies the endpoints of a $P_4$. Its summed coefficient is $8p_4(F)$ multiplying $\Delta\tau_R$. \item If $F$ has finite girth $g\ge5$, the only zero-loss type among discrete cyclic quotients at scale $N^{h-g}u^{g-1}$ is a single $C_g$ support. Their sum has coefficient $(-1)^ggc_g(F)$ multiplying $\Delta z_g$. In (…

11. Lemma 6.4: Four-cycle principal term
    PF:2026.000018/v1/LEM-6.4

    Let $F$ be a connected triangle-free graph of order $h$ containing a four-cycle. Let $R$ be an $\omega$-regular auxiliary graph constructed as in \hyperref[sec:wiring]{Section reference}, with positive seed degrees and with bounded proper-level generator counts as in Theorem 5.2. Suppose $\tau_R$ is constant. For distinct roots $v,w$, put $u=q_{\istar}$ and $\eps=\omega/N$. Then a_F\Delta d_F^{\overline R} =8c_4(F)N^{h-4}\Delta c_4^R +O_F\bigl((\eps+N^{-1})N^{h-4}u^3\bigr).

12. Theorem 7.1: Spectral digit decomposition
    PF:2026.000018/v1/THM-7.1

    Let $R$ be an auxiliary graph constructed in \hyperref[sec:wiring]{Section reference}, and let $D_i$ be the suffix degree in Eq. (equation reference). Define the matrix $\mathcal B_i$ on $\Gamma\times[n_i]$ by \mathcal B_i=D_iI+q_i\diag_{e\in\Gamma}(A_{S_{i,\chi_i(e)}}) +\sum_{s:a_s\le i}q_{a_s}(T_s\otimes I_{n_i}). For every positive integer $t$ and every two roots $(e,x),(f,y)$ of $R$, \Delta z_t^R =\sum_{i=0}^{P-1}\frac1{q_i} \bigl[(\mathcal B_i^t)_{(e,x_i),(e,x_i)}-(\mathcal B_i^t)_{(f,y_i),(f,y_i)}\bigr]. In particular, top-level generators do not affect these differences.

13. Lemma 7.2: Dependence on the local color
    PF:2026.000018/v1/LEM-7.2

    For each absolute position $i$ and each $t\ge0$, the value $(\mathcal B_i^t)_{(e,x_i),(e,x_i)}$ depends on $e$ only through $\chi_i(e)$. Consequently, all positions above the highest unequal letter cancel exactly in Eq. (equation reference).

14. Lemma 7.3: Disjoint binary subspaces
    PF:2026.000018/v1/LEM-7.3

    Fix $h_0\ge1$ and let $M=2^{h_0}-1$. For $k\ge1$, put $d=h_0\lceil\log_2(k+1)/h_0\rceil$. Whenever $p\ge2d+1$, there are $k$ different $h_0$-dimensional binary subspaces of $\FF_2^p$, all contained in the bit-$0$ zero hyperplane, and any two meeting only in zero.

15. Lemma 7.4: Uniform high-digit separation
    PF:2026.000018/v1/LEM-7.4

    Fix an integer $g\ge5$. For the mixed-radix construction and generator allocation specified above, there exist constants $M=2^{h_0}-1$, $p_0$, $\lambda_g^->0$ and $\lambda_g^+<\infty$, independent of $r,p,k,\ell$, such that, whenever $p\ge p_0$ and $\istar=p+j$ with $j\ge p$, setting $u=q_{\istar}$ and $\sigma=\operatorname{sgn}(\delta_{\istar})$ gives \lambda_g^-|\delta_{\istar}| \le \sigma\frac{\Delta z_g^R}{u^{g-1}} \le\lambda_g^+|\delta_{\istar}|. The constants can be chosen so that 4\frac{1+\eta}{1-\eta}\frac{\lambda_g^+}{\lambda_g^-} <125^{g-3}.

16. Lemma 8.1: A uniform mesh for irrational rotations
    PF:2026.000018/v1/LEM-8.1

    Let $\alpha\notin\mathbb Q$ and $\theta>0$. There is an integer $T_0(\alpha,\theta)$ such that, for every $T\ge T_0$, every integer $a$, and every phase $\beta$, the set \[ \{\,\beta+(a+t)\alpha\pmod1:0\le t<T\,\} \] has maximum circular gap $d_T<\theta$. Thus $d_T\to0$ uniformly over $a$ and $\beta$; also $d_T\ge1/T$.

17. Lemma 8.2: Exact-degree and phase selection
    PF:2026.000018/v1/LEM-8.2

    Fix $n=125$, $b=31250$, integers $g\ge5$ and $h_0\ge1$, $M=2^{h_0}-1$, a constant $\gamma>0$, and a nonempty open arc $I$ on the circle $\RR/((g-3)\log n)\mathbb Z$. For every sufficiently large integer $r$ there are integers $p,k,\ell\ge1$ and a family of distinct generators in (equation reference) such that \item $N=2^\ell b^pn^k$ and $r=N-1-\omega$ hold exactly; \item $p<\ell<k$, $\omega/N\to0$, and for $Q=b^pn^k$ the residual wiring degree $t=\omega-D$ satisfies $t/Q\to\infty$, uniformly in the admissible $p$ window; \item every amplified upper level uses the $M$ nonzero vectors from its designated complete subspace, with disjoint sets across levels, and at most $124$ additional digit generators. All pro…

18. Lemma 8.3: Exact degree for a fixed alphabet
    PF:2026.000018/v1/LEM-8.3

    Fix a regular seed alphabet of order $m\ge3$ and degree $d$, where $m$ is not a power of two and $1\le d<m$. For every sufficiently large integer $r$, the layered construction admits parameters $k>\ell\ge1$ and distinct proper- and top-level generators such that \[ Q=m^k,\qquad D=d\frac{Q-1}{m-1},\qquad N=2^\ell Q,\qquad r=N-1-D-t, \] where $t\ge0$, $t/Q\to\infty$ and $t/N\to0$ as $r\to\infty$. At each proper level at most $m-1$ generators are used.

19. Lemma 14.1: Block fourth-moment identity
    PF:2026.000018/v1/LEM-14.1

    Let $A,B$ be adjacency matrices of complementary $d$-regular graphs on $n=2d+1$ vertices, and let $Z$ be any $q\times q$ zero--one matrix. Put $E=A-B$ and \[ \mathsf M=J_q\otimes B+Z\otimes E,\qquad P_0=qJ_q,\quad P_1=ZJ_q+J_qZ^T,\quad P_2=ZZ^T. \] For $j=0,\ldots,4$, let $a_j(i)$ be the $i$th diagonal entry of the corresponding matrix in \[ P_0^2,\quad P_0P_1+P_1P_0,\quad P_1^2+P_0P_2+P_2P_0,\\ P_1P_2+P_2P_1,\quad P_2^2. \] In the bipartite graph with incidence matrix $\mathsf M$, the rooted four-cycle count at the left vertex $(i,x)$ is c_4(i,x)=\frac12\left(\sum_{j=0}^4 a_j(i)(B^{4-j}E^j)_{xx} -2(qd)^2+qd\right). Right-vertex counts are obtained by replacing $Z$ with $Z^T$. For the complementary block sub…