Extremal blowup conjecture for the maximum spectral gap s1,js_{1,j}

From papers

Let j1j\geq 1. For a graph GG, write s1,js_{1,j} for the maximum of the normalized spectral gap under consideration in the paper, and let KnK_n^* denote the complete graph KnK_n with loops on all vertices. The graph Kj+2Kj+1K_{j+2}\cup K_{j+1}^* is the disjoint union of Kj+2K_{j+2} and Kj+1K_{j+1}^*; a tt-blowup replaces every vertex by an independent set of size tt and every edge or loop according to the corresponding adjacency pattern.

Extremal blowup conjecture. For any j1j\geq 1, we have

s1,j=j+22j+3.s_{1,j}=\frac{j+2}{2j+3}.

If the conjecture holds, the lower bound is achieved by any graph which is a tt-blowup of Kj+2Kj+1K_{j+2}\cup K_{j+1}^*.

The construction gives the lower bound s1,j(j+2)/(2j+3)s_{1,j}\geq (j+2)/(2j+3), while the paper notes that this value is close to the known upper bound for large jj. The asserted equality and the extremal characterization remain open in the supplied source.

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

George Brooks, William Linz and Linyuan Lu, “Maximum spectral gaps of graphs”, arXiv:2408.15476 (2025).

Additional references

2 papers in this index state this conjecture (2019–2024). The statement above is taken from the most recent of them; the others are arXiv:1906.04084.

Solutions 0

No solutions have been posted yet.