The componentwise inertia sum-of-squares conjecture

About 12 years old · traced to

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+}≥n−1\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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.