Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-16T16:58:18.075Z Has data issue: false hasContentIssue false
  • English
  • Français

Density of Real Zeros of the Tutte Polynomial

Part of: Graph theory

Published online by Cambridge University Press:  09 March 2018

SEONGMIN OK  and
THOMAS J. PERRETT
SEONGMIN OK
Affiliation:
School of Computational Sciences, Korea Institute for Advanced Study, Seoul 02455, Republic of Korea (e-mail: [email protected])
THOMAS J. PERRETT
Affiliation:
Department of Applied Mathematics and Computer Science, Technical University of Denmark, 2800 Kongens Lyngby, Denmark (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The Tutte polynomial of a graph is a two-variable polynomial whose zeros and evaluations encode many interesting properties of the graph. In this article we investigate the real zeros of the Tutte polynomials of graphs, and show that they form a dense subset of certain regions of the plane. This is the first density result for the real zeros of the Tutte polynomial in a region of positive volume. Our result almost confirms a conjecture of Jackson and Sokal except for one region which is related to an open problem on flow polynomials.

MSC classification

Primary: 05C31: Graph polynomials
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 3 , May 2018 , pp. 398 - 410
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Dong, F. M. and Jackson, B. (2011) A zero-free interval for chromatic polynomials of nearly 3-connected plane graphs. SIAM J. Discrete Math. 25 1103–1118.CrossRefGoogle Scholar
[2] Goldberg, L. A. and Jerrum, M. (2008) Inapproximability of the Tutte polynomial. Inform. Comput. 206 908–929.CrossRefGoogle Scholar
[3] Goldberg, L. A. and Jerrum, M. (2012) Inapproximability of the Tutte polynomial of a planar graph. Comput. Complexity 21 605–642.CrossRefGoogle Scholar
[4] Goldberg, L. and Jerrum, M. (2014) The complexity of computing the sign of the Tutte polynomial. SIAM J. Comput. 43 1921–1952.CrossRefGoogle Scholar
[5] Jackson, B. (1993) A zero-free interval for chromatic polynomials of graphs. Combin. Probab. Comput. 2 325–336.CrossRefGoogle Scholar
[6] Jackson, B. and Sokal, A. (2009) Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids. J. Combin. Theory Ser. B 99 869–903.CrossRefGoogle Scholar
[7] Jacobsen, J. and Salas, J. (2013) Is the five-flow conjecture almost false? J. Combin. Theory Ser. B 103 532–565.CrossRefGoogle Scholar
[8] Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108 35–53.CrossRefGoogle Scholar
[9] Royle, G. and Sokal, A. (2015) Linear bound in terms of maxmaxflow for the chromatic roots of series-parallel graphs. SIAM J. Discrete Math. 29 2117–2159.CrossRefGoogle Scholar
[10] Sokal, A. (2004) Chromatic roots are dense in the whole complex plane. Combin. Probab. Comput. 13 221–261.CrossRefGoogle Scholar
[11] Sokal, A. (2005) The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in Combinatorics, 2005 (Webb, B., ed.), Cambridge University Press, pp. 173–226.CrossRefGoogle Scholar
[12] Thomassen, C. (1997) The zero-free intervals for chromatic polynomials of graphs. Combin. Probab. Comput. 6 497–506.CrossRefGoogle Scholar
[13] Tutte, W. (1974) Chromials. In Hypergraph Seminar (Berge, C. and Ray-Chaudhuri, D., eds), Vol. 411 of Lecture Notes in Mathematics, Springer, pp. 243–266.CrossRefGoogle Scholar