Skip to content
Preprint

Integral saturation of adjacency-degree lattices

Nov 2026 · 0 citations
Mathematics Computer Science

Abstract

Let $A$ be the adjacency matrix of $G\sim G(n,1/2)$, let $D=\operatorname{diag}(A\mathbf{1})$, and let $\Lambda_G=\mathbb{Z}\langle A,D\rangle\mathbf{1}$. We prove $\Pr[\Lambda_G\ne\mathbb{Z}^n]\le n^{-3/20+o(1)}$. Thus two dependent graph operators generate the entire vertex lattice from the constant vector, simultaneously over every prime field. Adjacency alone has a modulo-two rank obstruction for every simple graph of order greater than one, even though its rational word span is typically full. The proof first constructs words containing at most two adjacency operations whose integer span contains $\Delta_G^3\mathbb{Z}^n$, where $\Delta_G$ is the product of the pairwise differences between distinct degree values. This confines all possible arithmetic obstructions to a finite prime range on a single event. We then remove the remaining obstructions using conditional alternating forms, symmetric random-matrix code estimates, and uniform counts of degree-graded invariant subspaces. We connect the integer lattice to graph reconstruction through pointed moments. Saturation forces every pointed orthogonal AD intertwiner to be a vertex permutation. The short-word construction also shows that a fixed polynomial-size family of ordinary caterpillars, of diameter at most seven and order $O(\sqrt{n\log n})$, identifies almost every graph among all finite simple graphs. For nonsaturated full-rank lattices, we give an exact description of the moment fibre by admissible unimodular overlattices; at index two, the only possible ambiguity is a specified four-vertex Godsil--McKay switch.

View source

Similar papers

Preprint Oct 2026

Rank and Invertibility of Dense Signed Random Regular Matrices

Let $A$ be the (non-symmetric) adjacency matrix of a uniformly random $d$-regular directed graph on $n$ vertices, and let $\Xi$ be independent of $A$ with i.i.d. Rademacher entries. Suppose that $\min(d,n-d)\ge\lambda n$ for some fixed $\lambda\in(0,1/2]$. We show that there exists $c>0$, depending only on $\lambda$, s...

Huai-Jin Liang, Yu-Xiao Shi, Ke-Xin Yu et al. · 1 citation
Preprint Oct 2026

Strongly log-concave measures and lattices

Let $\Lambda \subseteq \mathbb{R}^n$ be a full rank lattice with the property that $\det \Gamma \ge 1$ for all sublattices $\Gamma \subseteq \Lambda^*$. We prove that there exists a symmetric random vector $X \in \mathbb{R}^n$ with a smooth, strictly positive density $f : \mathbb{R}^n \to (0, \infty)$ satisfying that (...

Brayden Letwin, Victor Reis, T. Rothvoss · 0 citations
Preprint Oct 2026

Transposition Cayley Spectra and Subgraph Counts

Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(G)$ be the Cayley graph of the symmetric group $S_n$ generated by the transpositions corresponding to the edges of $G$. We study the inverse spectral problem for the assignment $G\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{...

Boris Shapiro · 0 citations
Preprint Nov 2026

Non-log-concave $\tau$-polynomials of regular graphs

For any simple graph $G$ on $n$ vertices, write its chromatic polynomial in the rising factorial basis as $P(G,x)=\sum_{j=0}^{n}(-1)^{n-j}c_j x^{\langle j\rangle}$, where $x^{\langle j\rangle}=\prod_{i=0}^{j-1}(x+i)$ for any $j\ge 1$ and $x^{\langle0\rangle}=1$. Brenti (1992) introduced the $\tau$-polynomial and its au...

Mei-Qiao Zhang, Feng-Ming Dong · 0 citations
Preprint Oct 2026

Triangle-free Rank--Ramsey graphs from ordered incidence lifts

For a graph $G$ with adjacency matrix $A_G$ and a coefficient field $\mathbb K$, put $\rho_{\mathbb K}(G)=\operatorname{rank}_{\mathbb K}(A_G+I)$. We answer the triangle-free Rank--Ramsey existence question of Beniamini, Linial and Shraibman. For every order $n$, we construct a triangle-free graph $H_n$ such that, simu...

Yong Lu, Qi Wu, Qian-Nan Zhou · 0 citations
Preprint Oct 2026

Large corank of dense random regular digraphs

Let $1\le k\le n$ and let $A$ be the adjacency matrix of a uniformly random $d$-regular directed graph on $n$ vertices. Suppose that $\lambda n\le d \le (1-\lambda)n$ for a fixed $0<\lambda\le 1/2$. We show that there exists $c_{\lambda}>0$ depending only on $\lambda$ such that $$ \mathbb{P}[\operatorname{rank}(A)\le n...

Huai-Jin Liang, Ke-Xin Yu, Ting-Zhou Yu · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.