math.COSep 11, 2026

Edge-addition monotonicity of positive p-energy fails for every p >= 1

Authors: Koyar Afrasyab

Abstract

At a 2021 AIM workshop, Guo conjectured that the positive square energy s+ = E+_2 should inherit the familiar edge-addition monotonicity of the spectral radius, rho(G + uv) >= rho(G). That conjecture was subsequently shown to fail at p = 2. Tang, Liu, and Wang then introduced positive p-energy, proved nonmonotonicity for every 1 <= p < 3, and in version 3 of their preprint (26 March 2025) explicitly conjectured that monotonicity should hold for p >= 3. We disprove this conjectured high-exponent extension completely: for every real p > 2 there are infinitely many connected graphs G and nonedges uv such that E+_p(G + uv) < E+_p(G). Together with the Tang-Liu-Wang counterexamples below 3, this shows that no exponent p >= 1 restores the spectral-radius-style monotonicity: positive p-energy can decrease under the addition of an edge for every real p >= 1. The construction is a chain of clique blocks joined by regular bipartite graphs. An equitable quotient converges to Q = I + cA(P_k). For noninteger p, a binomial-series sign argument for a fractional power of I - cA(P_k) gives the required negative endpoint entry. At integer exponents, choosing c across the first spectral threshold leaves exactly one negative eigenvalue, and path locality forces the positive spectral contribution to have negative sign. We also give a fully rational 38-vertex certificate at p = 4 and determine the complete failure interval of a fixed 17-vertex counterexample at p = 3.

Explore similar work

Aug 16, 2026

A Counterexample to the Tang Zhang Schatten Norm Conjecture and Sharp Positive Results

For m≥2m\geq 2, let cp(m)c_p(m) be the all-dimensional best constant in ∥∑k=1mAk∥p≤cp(m)∥∑k=1m∣Ak∣∥p.\left\|\sum_{k=1}^m A_k\right\|_p \leq c_p(m)\left\|\sum_{k=1}^m |A_k|\right\|_p. Tang and Zhang conjectured an explicit formula for every finite p>1p>1. We disprove the conjecture with two explicit real 2×22\times 2 rank-one matrices at p=3/2p=3/2. The comparison is certified by seven strict rational inequalities and, in particular, places the attained ratio above 207/200207/200, while the conjectured constant lies below 207/200207/200. On the positive side, we prove the conjectured sharp bound for every family of rank-at-most-one summands when 2≤p<∞2\leq p<\infty, and classify all equality cases. We also prove the corresponding endpoint statement for p=∞p=\infty. Finally, for arbitrary complex matrices, we establish the conjectured sharp constant in the case m=2m=2, p=4p=4.
Sep 9, 2026

Nonmaximal sums of maximally monotone operators under Rockafellar's constraint qualification

We construct counterexamples to Rockafellar's sum conjecture in which two maximally monotone operators satisfy the interior-domain condition but their sum is not maximally monotone, thereby providing the complete disproof of the conjecture. We establish a general construction theorem that computes the entire monotone polar of a class of graphs, gives a necessary and sufficient condition for their maximal monotonicity, and shows how a positive rank-one perturbation yields a nonmaximal sum under this condition. We verify the theorem's hypotheses and its maximality criterion on c0c_0, thereby obtaining a counterexample to the conjecture. Furthermore, we construct a bounded linear surjection from ℓ1\ell^1 onto c0c_0 and use it to obtain the counterexample on ℓ1\ell^1. Lean formalizations of the c0c_0 counterexample and the pullback lemma are also provided.
Jul 8, 2026

Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspaces

Spectral positional encodings (PEs) for directed graphs face two obstacles: magnetic Laplacians require an O(n3)O(n^3) Hermitian eigendecomposition per potential, and their complex eigenvectors are defined only up to unitary gauge, which prior work handles with basis-invariant architectures. We propose learnable spectral PEs of the form hθ(Aq) Rh_θ(A_q)\,R, where AqA_q is a normalized magnetic operator, hθh_θ a learnable scalar spectral response, and RR a block of random probes. Because the PE is a matrix function of the operator, it is gauge-invariant by construction. We compute it in a Hermitian block Krylov subspace from sparse matrix--vector products only, prove that k=O(log⁡(1/ε))k = O(\log(1/\varepsilon)) block steps suffice uniformly over heat--resolvent response families, and give a covering-number argument for why low-dimensional structured families generalize where free per-eigenvalue weights overfit. On a directed SBM whose symmetrization is uninformative by construction, direction-blind PEs stay at chance while magnetic Krylov PEs converge to the exact-eigendecomposition oracle as the depth grows. The same probes yield gauge-invariant pairwise features with 1/s1/\sqrt{s} Monte-Carlo error, and the undirected q=0q{=}0 case improves heterophilous benchmarks over no-PE and polynomial baselines.