Real roots of the flow polynomial
Status disproved high confidence
Welsh's conjecture that all real roots of nonzero flow polynomials are at most $4$ has been disproved: Haggard, Pearce, and Royle found bridgeless graphs whose flow polynomials have real roots exceeding $4$. Subsequently, Jacobsen and Salas proved that real flow roots can even exceed $5$, finding that the generalized Petersen graph $G(119,7)$ has real flow roots at $Q \approx 5.0000198$ and $Q \approx 5.1653$, raising the question of whether real flow roots are bounded above at all.
Cited literature (2)
-
Exhibits infinitely many real flow roots exceeding 5 within generalized Petersen graphs G(nk,k), disproving the relaxed Welsh conjecture (bound 5) and showing the original bound-of-4 conjecture was far from tight.
-
Surveys results on real zeros of flow polynomials, including the disproof of Welsh's conjecture and subsequent developments on zero-free intervals.
Reviewer notes. The Haggard-Pearce-Royle paper that first disproved the original Welsh conjecture (bound of 4) could not be located and independently verified by WebFetch; its existence is confirmed by citation in the Jacobsen-Salas arXiv paper and in Gordon Royle's 2010 blog post (symomega). The Dong survey has an unusual timeline: journal publication December 2019 preceded the arXiv posting of July 2020. The supremum of real flow roots of flow polynomials is unknown and remains an open problem.
Discussion
For every graph $ G $ , let $ P_G $ be the chromatic polynomial of $ G $ and let $ Q_G $ be the flow polynomial of $ G $ . If $ G $ is loopless, then $ P_G(k)>0 $ for all sufficiently large integers $ k $ (as $ P_G(k) $ = # of k-colorings of $ G $ ). It follows from Seymour's 6-flow theorem that if $ G $ has no bridge , then $ Q_G(k)>0 $ for all integers $ k>5 $ (as $ Q_G(k) $ = # of nowhere-zero flows in the group of integers modulo $ k $ ). It is natural to ask if all real roots of these polynomials are small. For the chromatic polynomial, $ P_G $ , this is not the case. There exist graphs with chromatic number 3 for which $ P_G $ has arbitrarily large real roots. The above conjecture asserts that the flow polynomial exhibits the opposite behavior. One word of caution, it is known that the set of roots of flow polynomials is dense in the complex plane.
Bibliography
-
[S]P.D. Seymour, Nowhere-Zero 6-Flows, J. Combinatorial Theory Ser. B 30 (1981) 130-135. MathSciNet MathSciNet