CS Paper Radar

Rank-Three Projections and Minimal Multiplicity Bipartitions of Path Complements

Jintao Fei, Jiangying Luo

cs.DM math.SP ·submitted 2026-08-27 15:11 UTC · v1
theory

Abstract

For a graph \(G\) admitting a real symmetric realization with exactly two distinct eigenvalues, \(MB(G)\) is the minimum, over all such realizations, of the smaller of the two eigenvalue multiplicities. Adm, Fallat, Meagher, Nasserasr, Plosker, and Yang asked for this parameter for the complement of a path on at least eight vertices. We answer their question completely by proving $$ MB(\overline{P_n})=3 \qquad (n\ge 6). $$ In particular, this resolves the previously unresolved orders \(n\ge 9\) divisible by three. The proof is exact and constructive. We exhibit six vectors in \(\mathbb{R}^3\) whose mutual inner products vanish exactly for consecutive indices, whose rank-one outer products form a basis of \(\mathbb{S}^3\), and which admit a strictly positive Parseval scaling. An elementary absorption lemma then permits any finite faithful orthogonal extension of this vector chain to be added with small positive weights while the six original weights are corrected to retain the Parseval identity. The resulting Gram matrix is a rank-three orthogonal projection in \(\mathcal{S}(\overline{P_n})\). A local two-dimensional orthogonality obstruction gives the matching lower bound. For completeness, we include self-contained proofs of the exceptional small orders: \(MB(\overline{P_3})=1\), whereas \(q(\overline{P_4})=4\) and \(q(\overline{P_5})=3\).

Comment
9 pages, 13 references; exact and constructive proof. The source package includes an exact-arithmetic verification script

Closest papers

Nearest neighbours by meaning across the whole index.

Integral saturation of adjacency-degree lattices

cs.DM math.CO ·2026-11-01 ·Zhipeng Lu
theory similarity 0.59
Abstract

Let $A$ be the adjacency matrix of $G\sim G(n,1/2)$, let $D=\operatorname{diag}(A\mathbf{1})$, and let $Λ_G=\mathbb{Z}\langle A,D\rangle\mathbf{1}$. We prove $\Pr[Λ_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 $Δ_G^3\mathbb{Z}^n$, where $Δ_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.

0.28

Determinant boundaries and gaps in determinantal complexity

cs.CC ·2026-11-02 ·Karthik Sheshadri
theory similarity 0.58
Abstract · 75 pages, in submission to FoCM

Landsberg, Manivel, and Ressayre constructed determinant-boundary components whose defining forms, for odd n >= 3, are limits of n x n determinants but cannot themselves be represented by determinants of that size. Their border determinantal complexity (DC) is therefore smaller than their exact DC. We prove that the difference can grow linearly with n. For every n >= 10, we construct an explicit homogeneous form of degree n, concise in n^2 variables, whose orbit closure is a boundary component, whose border DC is n, and whose exact DC is at least 2n - 1. Thus n rows suffice when limits are allowed, whereas every exact representation requires at least 2n - 1 rows. The same bound holds for the unpadded odd-skew forms at every odd n >= 3. We also prove that every concise degree-n boundary form in n^2 variables has exact DC at least n + 2. We construct three families of pairwise distinct boundary components. Together with the traceless determinant, they give at least floor((n-1)/2) + floor(n/3) components for every n >= 3, with an additional term counted explicitly in the paper. The main lower bound follows from a general degree lemma. If an affine matrix represents an irreducible homogeneous polynomial f of degree d and has globally free rank-one cokernel over the coordinate ring of f = 0, its size is at least 2d - 1. The adjugate factors into two nonzero kernel vectors, each requiring a coordinate of degree at least d - 1. Comparing their product with the degree of a cofactor proves the bound. The lemma is sharp for individual representations, as witnessed by algebraic branching programs. Whether the exact-versus-border gap can grow superlinearly remains open.

0.32

Completing the Boundary Case of the Mahmoodian-Mirzakhani Conjecture and 117 New Computational 5-Cycle Decompositions of Complete Tripartite Graphs

cs.DM math.CO ·2026-08-18 ·Roozbeh Pournader
theory similarity 0.57
Abstract · 15 pages; for associated data files, see https://doi.org/10.5281/zenodo.21882725

Let $K_{r,s,t}$, with $r\le s\le t$, denote the complete tripartite graph whose partite sets have sizes $r,s,t$. Mahmoodian and Mirzakhani gave three necessary conditions for $K_{r,s,t}$ to admit a decomposition into 5-cycles and conjectured that these conditions are sufficient. One of the conditions is $t\le 4rs/(r+s)$. We prove the conjecture for every odd triple on the extremal boundary $t = 4rs/(r+s)$. The proof is constructive. After reducing an arbitrary odd boundary triple to $(r,s,t)=(hga,hgb,hab)$, $a+b=4g$, we give an explicit cyclic decomposition of $K_{ga,gb,ab}$ and use the Mahmoodian and Mirzakhani scaling theorem to supply the common factor $h$. Together with the previously known all-even result, this settles the conjecture for every triple satisfying the boundary condition with equality. We also report explicit computer-generated $C_5$-decompositions for 117 odd triples satisfying the necessary conditions, 116 of which are strict-interior cases. To the best of our knowledge, all 117 cases were previously unresolved: no decomposition for any of them had been reported, and none of the 117 triples is covered by earlier existence results, constructions, or their recursive consequences. Moreover, these 117 certificates together with the boundary construction settle every previously unresolved triple satisfying the necessary conditions with fewer than $4400$ edges. Each computation is supplied as a machine-readable cycle-list certificate and can be checked independently by a short Python verifier. We also give a complete human-readable edge-label-matrix certificate for $K_{9,19,23}$.

0.31

Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs

cs.DM math.CO ·2026-10-10 ·Junran Yu, Gregory Gutin, Hong-Jian Lai, Xiaoyan Zhang
theory similarity 0.55
Abstract

Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

0.21

Explicit restricted isometries with $k=m^{2/3-o(1)}$

cs.IT math.FAmath.COmath.MG ·2026-11-10 ·Christian Kümmerle, Dustin G. Mixon
theory similarity 0.55
Abstract · 16 pages

We construct an explicit family of real $m\times n$ restricted isometries with $m\to\infty$, $m/n\to 0$, $δ_k\to 0$, and $k=m^{2/3-o(1)}$. We combine Gershgorin's circle theorem with a flat RIP estimate to reduce the problem to choosing a large vertex set in a strongly regular graph with the property that every small subset spans few edges. We select this vertex set using an incidence geometric result due to Zahl. The proof only uses the entrywise absolute value of the Gram matrix despite the conventional wisdom that such proof techniques exhibit a barrier of $m^{1/2}$. We prove that this barrier is actually $m^{2/3}$, and we show that our particular construction exhibits the same barrier.

0.23

$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrt{n})$

cs.DM math.CO ·2026-10-31 ·Jonathan Conroy, Hung Le, Jack Spalding-Jamieson
theory similarity 0.55
Abstract

We show that every $K_h$-minor-free graph with $n$ vertices has a balanced separator of size $O(h\sqrt{n})$ for any parameter $h \in \mathbb{N}$, resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given $k$ large (not necessarily disjoint) subsets of vertices, there is a walk of length $O(k/ψ(G))$ hitting every subset, where $ψ(G)$ is the vertex expansion. This technical result substantially improves on an analogous lemma by Alon, Seymour, and Thomas [AST90] in an important parameter setting, where the previous lower bound [Kot00] does not apply.

0.48

A 3-regular counterexample to the Bilu--Linial signing conjecture

cs.DM math.CO ·2026-09-14 ·Zhiqiang Xu
similarity 0.54
Abstract · 19 pages, 5 figures. The presentation has been improved

We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu--Linial signing conjecture for general regular graphs. The graph $F$ is not Ramanujan, and the conjecture restricted to Ramanujan base graphs remains open.

0.62

Spectral Methods for the Complexity of Planar Graph Homomorphisms

cs.CC ·2026-09-28 ·Ashwin Maran, Jin-Yi Cai, Zhuxiao Tang
theory similarity 0.53
Abstract · 35 pages, 2 figures

We explore the frontier beyond the recently discovered barrier represented by the \emph{quantum automorphism group} $qut(M)$ in the classification theory of planar graph homomorphisms $PlGH(M)$. We show that analyzing the spectral relations of $M$ can prove \#P-hardness when traditional vertex separation and domain-reduction methods with planar edge gadgets provably fail due to the $\qut(M)$ barrier. We prove two criteria of \#P-hardness for $PlGH(M)$: a spectral criterion and a determinant criterion. It is known that the core problem for the classification of $PlGH(M)$ for nonnegative matrices $M$ is for positive definite entry-wise positive matrices. We use the spectral criterion to show that $PlGH(M)$ is \#P-hard for all circulant matrices of prime order $q \ge 3$, while for $q=2$ it is precisely the matchgate case and is P-time computable by the FKT algorithm (for planar perfect matching). We also prove a complexity dichotomy for $\PlGH$ problems defined by tensor products of 2 by 2 matrices. This gives a complete complexity classification for this class of matrices, and the FKT algorithm together with a holographic transformation is \emph{universal}---every $PlGH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs; furthermore, $PlGH(M)$ in (2) consists of precisely those computable by FKT with a holographic transformation.

0.30