The componentwise inertia sum-of-squares conjecture

From papers

Let GG be a simple undirected graph with nn vertices and κ\kappa connected components. Let μ1μn\mu_1\geq\cdots\geq\mu_n be the eigenvalues of its adjacency matrix, and let π\pi and ν\nu be the numbers of positive and negative eigenvalues, counted with multiplicity. Define

s+=i=1πμi2,s=i=nν+1nμi2.s^+=\sum_{i=1}^{\pi}\mu_i^2,\qquad s^-=\sum_{i=n-\nu+1}^{n}\mu_i^2.

Componentwise inertia sum-of-squares conjecture. One has

min{s,s+}nκ.\min\{s^-,s^+\}\geq n-\kappa.

For a connected graph, this specializes to the conjectured lower bound min{s,s+}n1\min\{s^-,s^+\}\geq n-1, and either one-sided inequality implies the corresponding Hong-type bound. The supplied source gives no evidence of a resolution for the general disconnected-graph formulation.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Clive Elphick, Felix Goldberg, Miriam Farber and Pawel Wocjan, “Conjectured bounds for the sum of squares of positive eigenvalues of a graph”, arXiv:1409.2079 (2015).

Solutions 0

No solutions have been posted yet.