Extremal blowup conjecture for the maximum spectral gap
Extremal blowup conjecture for the maximum spectral gap
Let . For a graph , write for the maximum of the normalized spectral gap under consideration in the paper, and let denote the complete graph with loops on all vertices. The graph is the disjoint union of and ; a -blowup replaces every vertex by an independent set of size and every edge or loop according to the corresponding adjacency pattern.
Extremal blowup conjecture. For any , we have
If the conjecture holds, the lower bound is achieved by any graph which is a -blowup of .
The construction gives the lower bound , while the paper notes that this value is close to the known upper bound for large . 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
Sign in to submit a solution.
No solutions have been posted yet.