Is the five-flow conjecture almost false?

Abstract

The number of nowhere zero Z_Q flows on a graph G can be shown to be a polynomial in Q, defining the flow polynomial Φ_G(Q). According to Tutte's five-flow conjecture, Φ_G(5) > 0 for any bridgeless G.A conjecture by Welsh that Φ_G(Q) has no real roots for Q \in (4,\infty) was recently disproved by Haggard, Pearce and Royle. These authors conjectured the absence of roots for Q \in [5,\infty). We study the real roots of Φ_G(Q) for a family of non-planar cubic graphs known as generalised Petersen graphs G(m,k). We show that the modified conjecture on real flow roots is also false, by exhibiting infinitely many real flow roots Q>5 within the class G(nk,k). In particular, we compute explicitly the flow polynomial of G(119,7), showing that it has real roots at Q\approx 5.0000197675 and Q\approx 5.1653424423. We moreover prove that the graph families G(6n,6) and G(7n,7) possess real flow roots that accumulate at Q=5 as n\to\infty (in the latter case from above and below); and that Q_c(7)\approx 5.2352605291 is an accumulation point of real zeros of the flow polynomials for G(7n,7) as n\to\infty.

44 pages (LaTeX2e). Includes tex file, three sty files, and a mathematica script polyG119_7.m. Many improvements from version 3, in particular Sections 3 and 4 have been mostly re-writen, and Sections 7 and 8 have been eliminated. (This material can now be found in arXiv:1303.5210.) Final version published in J. Combin. Theory B

References in corpus (7)

• Phase diagram of the chromatic polynomial on a torus
• Character decomposition of Potts model partition functions. I. Cyclic geometry
• Eigenvalue amplitudes of the Potts model on a torus
• Combinatorial aspects of boundary loop models
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• A generalized Beraha conjecture for non-planar graphs
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings

Cited by in corpus (7)

• Q-colourings of the triangular lattice: Exact exponents and conformal field theory
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• Phase diagram of the triangular-lattice Potts antiferromagnet
• A generalized Beraha conjecture for non-planar graphs
• The phase diagram for the bisected-hexagonal-lattice five-state Potts antiferromagnet
• A survey on the study of real zeros of flow polynomials
• On zeros of the characteristic polynomial of matroids of bounded tree-width