Density of Real Zeros of the Tutte Polynomial

被引:0
作者
Ok, Seongmin [1 ]
Perrett, Thomas J. [2 ]
机构
[1] Korea Inst Adv Study, Sch Computat Sci, Seoul 02455, South Korea
[2] Tech Univ Denmark, Dept Appl Math & Comp Sci, DK-2800 Lyngby, Denmark
基金
新加坡国家研究基金会;
关键词
CHROMATIC ROOTS; INAPPROXIMABILITY; COMPLEXITY; GRAPHS; PLANE;
D O I
10.1017/S0963548318000019
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:398 / 410
页数:13
相关论文
共 44 条
  • [1] Fourientations and the Tutte polynomial
    Backman, Spencer
    Hopkins, Sam
    RESEARCH IN THE MATHEMATICAL SCIENCES, 2017, 4
  • [2] Inapproximability of the Tutte Polynomial
    Goldberg, Leslie Ann
    Jerrum, Mark
    STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 459 - 468
  • [3] A Tutte Polynomial for Maps
    Goodall, Andrew
    Krajewski, Thomas
    Regts, Guus
    Vena, Lluis
    COMBINATORICS PROBABILITY & COMPUTING, 2018, 27 (06) : 913 - 945
  • [4] On the location of zeros of the Homfly polynomial
    Jin, Xian'an
    Zhang, Fuji
    JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2011,
  • [5] Fourientation activities and the Tutte polynomial
    Backman, Spencer
    Hopkins, Sam
    Traldi, Lorenzo
    EUROPEAN JOURNAL OF COMBINATORICS, 2018, 67 : 40 - 60
  • [6] Tutte polynomial of some multigraphs
    Allagan, Julian A.
    Mphako-Banda, Eunice
    QUAESTIONES MATHEMATICAE, 2015, 38 (05) : 709 - 724
  • [7] On Tutte polynomial uniqueness of twisted wheels
    Duan, Yinghua
    Wu, Haidong
    Yu, Qinglin
    DISCRETE MATHEMATICS, 2009, 309 (04) : 926 - 936
  • [8] THE COMPLEXITY OF COMPUTING THE SIGN OF THE TUTTE POLYNOMIAL
    Goldberg, Leslie Ann
    Jerrum, Mark
    SIAM JOURNAL ON COMPUTING, 2014, 43 (06) : 1921 - 1952
  • [9] Deletion-contraction and the surface Tutte polynomial
    Moffatt, Iain
    Thompson, Maya
    EUROPEAN JOURNAL OF COMBINATORICS, 2024, 118
  • [10] Csikvári's poset and Tutte polynomial
    Ding, Changxin
    DISCRETE MATHEMATICS, 2025, 348 (07)