The Graham–Lovász conjecture on unimodality of normalized tree coefficients
Let be a tree of order . For a graph of order , write for the coefficients of its distance characteristic polynomial and define the normalized coefficients
for . A sequence is unimodal if it is nondecreasing up to some index and nonincreasing thereafter. Graham–Lovász's conjecture. The sequence is unimodal and its peak occurs at .
The conjecture concerns the shape of the coefficients of the distance characteristic polynomial of a tree.
References
Status
- Refuted: Karen L. Collins. On a Conjecture of Graham and Lovász about Distance Matrices (Linear Algebra and its Applications, 1985) https://kcollins.web.wesleyan.edu/publications/unimodal.pdf
Source: Leslie Hogben and Carolyn Reinhart, “Spectra of variants of distance matrices of graphs and digraphs: a survey”, arXiv:2103.00647 (2021).
Progress summary
The original conjecture is false about where the peak occurs, but a published proof establishes the remaining claim that the normalized coefficients always rise and then fall.
The conjecture combines unimodality of the normalized coefficients with a prescribed peak at . Collins disproved that peak location in 1985; the surviving question is the unimodality itself and the sharper Collins–Shor bounds on the peak.
Known results
- Collins, 1985: the prescribed peak at is false; for paths it is asymptotically near .
- Collins: normalized coefficients are unimodal for paths and stars.
- The 2015 result proves log-concavity, hence unimodality, for every tree.
- The same work gives a universal peak upper bound near , a diameter-dependent lower bound, and computational confirmation through order .
2015 proof of unimodality
A 2015 paper titled Proof of a Conjecture of Graham and Lovász concerning Unimodality of Coefficients of the Distance Characteristic Polynomial of a Tree claims log-concavity and therefore unimodality of both the absolute and normalized coefficient sequences for every tree. It leaves the corrected peak-location question open; the claim is reported here as unverified.
Current status (as of September 2026): The original peak-location assertion is refuted, while unimodality is claimed proved for all trees; the corrected Collins–Shor peak-location conjecture remains open.
Solutions 0
No solutions have been posted yet.