PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Koyar Afrasyab

arXiv:2609.13476v1math.COcs.AI

TL;DR

The paper asks whether positive p-energy inherits the spectral-radius-style monotonicity under edge addition, including the conjectured regime p ≥ 3. It uses a chain construction and quotient-based sign arguments to show that no exponent p ≥ 1 restores universal monotonicity.

  • Problem

    The spectral-radius-style monotonicity conjecture for positive p-energy remained open for p ≥ 3 after earlier counterexamples covered 1 ≤ p < 3.

    Source: §1 · pp. 1–2

  • Method

    The proof uses a chain construction and quotient-based sign arguments, with different mechanisms at integer and noninteger exponents.

    Source: §7 · p. 11

  • Results

    For every real p > 2, infinitely many connected graphs have a missing edge whose addition decreases positive p-energy; with earlier results, failure holds for every p ≥ 1.

    Source: §1 · p. 2

  • Takeaways & Limitations

    No positive p-energy has a universal spectral-radius-style monotonicity under adding a missing edge.

    Source: §7 · p. 11

    The auxiliary three-block argument requires choosing its block-ratio parameter after fixing p, so no single parameter works uniformly up to 4; the chain construction makes it unnecessary for the main theorem.

    Source: §1 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

The paper disproves the conjectured extension of spectral-radius-style edge-addition monotonicity to positive p-energy. Its main theorem gives counterexamples for every real p > 2, completing the failure across all p ≥ 1 when combined with earlier results.

1 Introduction

  • The conjecture arose from the spectral-radius inequality and Guo's proposal that positive square energy should satisfy an analogous inequality.The square-energy conjecture was later refuted by an explicit graph example [4, Example 2.6].Source: §1 · pp. 1–2
  • Tang, Liu, and Wang [1] established counterexamples for 1 ≤ p < 3, while version 3 of their preprint conjectured monotonicity for p ≥ 3 [2, Conjecture 3].The published version frames the remaining regime as an open monotonicity problem [1].Source: §1 · p. 2
  • For every real p > 2, infinitely many connected graphs have a missing edge whose addition strictly decreases positive p-energy.This rules out any upper threshold beyond which the monotonicity would always hold.Source: §1 · p. 2
  • For every real p ≥ 1, positive p-energy is not monotone under edge addition, combining this paper's theorem with Tang–Liu–Wang [1].Their result covers 1 ≤ p < 3; this paper supplies the p ≥ 3 range, with overlap for 2 < p < 3.Source: §1 · p. 2
  • An earlier three-block family covers 2 < p < 4 only with a block-ratio parameter chosen after fixing p.No single parameter works uniformly up to 4, and the chain construction makes that auxiliary family unnecessary for the main theorem.Source: §1 · p. 2

2 The chain construction and the quotient limit

The construction connects clique blocks by regular bipartite graphs and uses an equitable quotient to study how adding an endpoint edge changes positive p-energy. In the limit, the core quotient is Q = I_k + cA(P_k).

2 The chain construction and the quotient limit

  • The graph consists of k disjoint n-vertex cliques linked consecutively by d-regular bipartite graphs, with endpoint vertices attached to the first and last cliques.There are no edges between nonconsecutive blocks; the resulting graph is connected when d ≥ 1.Source: §2 · pp. 2–3
  • The block partition is equitable, and its normalized block-constant quotient uses t ∈ [0, 1] as the weight of the endpoint edge.The orthogonal-complement restriction is identical at t = 0 and t = 1, so it cancels from energy differences.Source: §2 · p. 3
  • When d/n tends to c and Q has no zero eigenvalue, the core quotient converges to Q = I_k + cA(P_k).For sufficiently large n, one eigenvalue remains near each eigenvalue of Q while two others approach zero.Source: §2 · pp. 3–4
  • The two eigenvalues near zero contribute only O(1) positive p-energy at the endpoints, which is negligible compared with n^(p−2) for p > 2.The separated eigenvalues of order n supply the principal contribution in the limit.Source: §2 · p. 5

3 Noninteger exponents

For noninteger p > 2, the proof reduces the energy comparison to a fractional power of a path-based quotient. A binomial-series sign argument establishes the strict sign needed for counterexamples.

3 Noninteger exponents

  • For noninteger p > 2, the proof uses a generalized binomial series that converges absolutely when cρ(A) < 1.The argument applies the series to a fractional power involving the path adjacency matrix.Source: §3 · pp. 5–6
  • Every nonzero term in the endpoint entry has the same sign, and the first such term is nonzero.The endpoint sign follows from the diagonal sign product D_11D_kk = (−1)^(k−1).Source: §3 · p. 6
  • The strict sign yields counterexamples for infinitely many sufficiently large n.For rational c = a/b, the proof takes n through multiples of b so d = cn is integral.Source: §3 · p. 6

4 Integer exponents

For every integer m ≥ 3, the construction makes the positive m-energy decrease after adding an edge, completing the proof for all real p > 2. The integer case chooses a spectral threshold that leaves one negative eigenvalue and uses path locality to determine the sign of the positive spectral contribution.

4 Integer exponents

  • A choice of ϑ exists before the second spectral threshold, allowing the construction to cross the first threshold while meeting the required conditions.For m = 3 the second inequality is automatic; for m ≥ 4, cos ϑ > cos(2ϑ) leaves a nonempty interval.Source: §4 · pp. 6–7
  • The quotient eigenvalues are θj = 1 + 2c cos(jπ/(m + 1)); the chosen threshold gives θm < 0 < θm−1, so Q has exactly one negative eigenvalue and no zero eigenvalue.The normalized sine eigenvector for θm has an endpoint product used in the spectral-decomposition sign argument.Source: §4 · p. 7
  • Because the path endpoints are distance m − 1 and r = m − 3, path locality forces the positive spectral contribution to have negative sign.The spectral decomposition uses θm as the sole negative eigenvalue to establish the sign in (23).Source: §4 · p. 7
  • The integer construction proves the edge-addition energy difference is negative for every m ≥ 3, completing the theorem for all real p > 2.It uses n through multiples of the denominator of c and sets d = cn.Source: §4 · p. 7

5 An explicit p = 4 certificate

A 38-vertex graph pair gives a concrete p = 4 edge-addition counterexample. Its negative spectra and rational evaluations provide an exact certificate alongside the reported numerical energy difference.

5 An explicit p = 4 certificate

  • J0 uses four K9 cliques joined consecutively, with u and v attached to the end cliques and uv omitted; J1 adds uv.The graph has 38 vertices.Source: §5 · p. 7
  • The negative spectra are −1 with multiplicity 32 and −a, −b, −c for J0, versus −1 with multiplicity 34 and −7 for J1.The characteristic polynomial of J0 is (x + 1)^32(x^3 − 25x^2 + 46x + 153)(x^3 − 7x^2 − 98x − 9).Source: §5 · p. 7
  • The roots a, b, and c are specified through cubic equations, and direct rational evaluations are used in the certificate.Adding uv creates no new 4-cycle, and both endpoint degrees are 9; total fourth energy is the fourth spectral moment.Source: §5 · p. 8
  • The p = 4 energy difference for the 38-vertex pair is approximately −3.8556020556.The pair is J0 and J1 = J0 + uv.Source: §5 · pp. 7–8

6 A 17-vertex exact counterexample and its full failure interval

For a fixed 17-vertex graph pair, the paper determines exactly which exponents make edge addition decrease positive p-energy. The interval contains p = 3, giving an exact counterexample at the endpoint of the previously open range.

6 A 17-vertex exact counterexample and its full failure interval

  • The pair is an exact 17-vertex counterexample at p = 3, an endpoint of the previously open range.The proof also reports Δ(3) < 0.Source: §6 · pp. 9–10
  • A generalized Descartes rule bounds the distinct real zeros of the difference function by the number of coefficient sign changes.The coefficient sequence has exactly three sign changes, and one zero is the trivial zero.Source: §6 · pp. 9–10
  • For the 17-vertex pair, positive p-energy decreases after edge addition exactly when α < p < β, for unique α in (2, 3) and β in (3, 4).The sign pattern on p ≥ 1 and the absence of any other zeros establish the complete interval.Source: §6 · p. 11
  • Continuity yields α ∈ (2, 3) and β ∈ (3, 4); with p = 0 these are three distinct real zeros, and Lemma 2 excludes others, so signs at 2, 3, 4 force the stated pattern for p ≥ 1.Source: §6 · p. 11

7 Discussion

The discussion concludes that positive p-energy is not universally monotone under edge addition for any p ≥1, with distinct mechanisms at integer and noninteger exponents. It distinguishes this local question from global energy minimization and highlights two finite examples.

7 Discussion

  • No exponent p ≥1 gives universal edge-addition monotonicity for positive p-energy, despite the spectral radius satisfying the analogous inequality.The discussion identifies this as a complete negative resolution of Tang–Liu–Wang’s Conjecture 3, arXiv v3 [2].Source: §7 · p. 11
  • For noninteger exponents, a fractional-power binomial series yields a negative endpoint sign; at integers, one negative mode and path locality produce a strict negative sign.At integer exponents the leading term vanishes by locality, and crossing the first spectral threshold creates the negative mode.Source: §7 · p. 11
  • The 38-vertex example certifies failure at p = 4 with rational arithmetic, while one fixed 17-vertex pair fails only on a bounded exponent interval.The family construction instead supplies counterexamples at every exponent by changing the graph.Source: §7 · p. 11
  • Global path-minimality results, including positive p-energy at p = 4, do not imply local edge-addition monotonicity.The paper separates global minimization among connected graphs from the local effect of adding a missing edge.Source: §7 · p. 11
Loading 2609.13476v1…