pith. sign in

An exponentially small gap of the Perron vector on independent sets

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

A classical result of Cioab\u{a} states that if $G$ is a connected graph with the unit Perron vector $\mathbf{x}$, then any independent set $S$ of $G$ satisfies $\sum_{v\in S} x_v^2 \le \frac{1}{2}$, with equality if and only if $G$ is a bipartite graph and $S$ is one of the partite sets. Let $\chi(G)= k $ be the chromatic number of $G$. A well-known conjecture of Gregory asserts that any independent set $S$ of $G$ satisfies $\frac{1}{2} - \sum_{v\in S}x_v^2 = \Omega ((k/n)^{1/2})$. Recently, Liu and Ning [J. Combin. Theory Ser. B 176 (2026)] disproved Gregory's conjecture by constructing a graph $G$ and an independent set $S$ such that $\frac{1}{2}- \sum_{v\in S}x_v^2 = O(k^5/n^3)$. Furthermore, they conjectured that this bound is tight up to a constant factor. In this paper, we first show that any cycle $C_n$ with odd integer $n\ge 7$ provides a simple counterexample to Gregory's conjecture. Second, we establish that for any independent set $S$, we have $\frac{1}{2} - \sum_{v\in S}x_v^2 = \frac{q}{4\lambda -2q}$, where $\lambda$ is the spectral radius of $G$, and $q$ is the Rayleigh quotient of $\mathbf{x}$ restricted to $\bar{S} :=V(G)\setminus S$. Third, we construct a graph with arbitrarily large chromatic number and find an independent set $S$ such that $\sum_{v\in S}x_v^2$ can be arbitrarily close to $\frac{1}{2}$, with an exponentially small gap. Our construction shows that there is no universal lower bound of the form $\Omega (k^{\alpha}/n^{\beta})$ for any $\alpha, \beta >0$. This settles both Gregory's original conjecture and the modified conjecture of Liu and Ning in the negative. Finally, we show the tightness of our construction and provide some local weighted lower bounds.

fields

math.CO 1

years

2026 1

verdicts

UNVERDICTED 1

representative citing papers

Spectral Sidorenko inequalities and edge-spectral supersaturation

math.CO · 2026-05-26 · unverdicted · novelty 7.0

Sidorenko's conjecture is equivalent to hom(H,G) ≥ λ(G)^{2e-v} M(G)^{v-e}, which yields asymptotically sharp supersaturation bounds for the number of K_{t,t} and C_{2t} in graphs with λ(G) > λ(S_{t-1,m}).

citing papers explorer

Showing 1 of 1 citing paper.

  • Spectral Sidorenko inequalities and edge-spectral supersaturation math.CO · 2026-05-26 · unverdicted · none · ref 4 · internal anchor

    Sidorenko's conjecture is equivalent to hom(H,G) ≥ λ(G)^{2e-v} M(G)^{v-e}, which yields asymptotically sharp supersaturation bounds for the number of K_{t,t} and C_{2t} in graphs with λ(G) > λ(S_{t-1,m}).