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 条
  • [21] Zeros of the Jones polynomial are dense in the complex plane
    Jin, Xian'an
    Zhang, Fuji
    Dong, Fengming
    Tay, Eng Guan
    ELECTRONIC JOURNAL OF COMBINATORICS, 2010, 17 (01)
  • [22] Computing the Tutte polynomial of lattice path matroids using determinantal circuits
    Morton, Jason
    Turner, Jacob
    THEORETICAL COMPUTER SCIENCE, 2015, 598 : 150 - 156
  • [23] Quasi-tree expansion for the Bollobas-Riordan-Tutte polynomial
    Champanerkar, Abhijit
    Kofman, Ilya
    Stoltzfus, Neal
    BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2011, 43 : 972 - 984
  • [24] Zeros of the Jones Polynomial for Multiple Crossing-Twisted Links
    Jin, Xian'an
    Zhang, Fuji
    JOURNAL OF STATISTICAL PHYSICS, 2010, 140 (06) : 1054 - 1064
  • [25] Fast Linear Homotopy to Find Approximate Zeros of Polynomial Systems
    Beltran, Carlos
    Miguel Pardo, Luis
    FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2011, 11 (01) : 95 - 129
  • [26] A survey on the study of real zeros of flow polynomials
    Dong, Fengming
    JOURNAL OF GRAPH THEORY, 2019, 92 (04) : 361 - 376
  • [27] FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
    Gebauer, Heidi
    Okamoto, Yoshio
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2009, 20 (01) : 25 - 44
  • [28] FAST COMPUTATION OF ZEROS OF POLYNOMIAL SYSTEMS WITH BOUNDED DEGREE UNDER FINITE-PRECISION
    Briquel, Irenee
    Cucker, Felipe
    Pena, Javier
    Roshchina, Vera
    MATHEMATICS OF COMPUTATION, 2014, 83 (287) : 1279 - 1317
  • [29] Density of Roots of the Yamada Polynomial of Spatial Graphs
    Li, Miaowang
    Lei, Fengchun
    Li, Fengling
    Vesnin, Andrei Yu.
    PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS, 2019, 305 (01) : 135 - 148
  • [30] MAXIMAL AND TYPICAL TOPOLOGY OF REAL POLYNOMIAL SINGULARITIES
    Lerario, Antonio
    Stecconi, Michele
    ANNALES DE L INSTITUT FOURIER, 2024, 74 (02) : 589 - 626