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 条
  • [31] On trees with real-rooted independence polynomial
    Bencs, Ferenc
    DISCRETE MATHEMATICS, 2018, 341 (12) : 3321 - 3330
  • [32] Continued Fraction Expansion of Real Roots of Polynomial Systems
    Mantzaflaris, Angelos
    Mourrain, Bernard
    Tsigaridas, Elias
    SNC'09: PROCEEDINGS OF THE 2009 INTERNATIONAL WORKSHOP ON SYMBOLIC-NUMERIC COMPUTATION, 2009, : 85 - 94
  • [33] TOPOLOGICAL COMPLEXITY AND SCHWARZ GENUS OF GENERAL REAL POLYNOMIAL EQUATION
    Vassiliev, V. A.
    MOSCOW MATHEMATICAL JOURNAL, 2011, 11 (03) : 617 - 625
  • [34] Computing real radicals and S-radicals of polynomial systems
    El Din, Mohab Safey
    Yang, Zhi-Hong
    Zhi, Lihong
    JOURNAL OF SYMBOLIC COMPUTATION, 2021, 102 : 259 - 278
  • [35] PROBABILISTIC ALGORITHM FOR POLYNOMIAL OPTIMIZATION OVER A REAL ALGEBRAIC SET
    Greuet, Aurelien
    El Din, Mohab Safey
    SIAM JOURNAL ON OPTIMIZATION, 2014, 24 (03) : 1313 - 1343
  • [36] Counting Real Roots in Polynomial-Time via Diophantine Approximation
    Rojas, J. Maurice
    FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2024, 24 (02) : 639 - 681
  • [37] APPROXIMATION ALGORITHMS FOR POLYNOMIAL-EXPANSION AND LOW-DENSITY GRAPHS
    Har-Peled, Sariel
    Quanrud, Kent
    SIAM JOURNAL ON COMPUTING, 2017, 46 (06) : 1712 - 1744
  • [38] On polynomial submersions of degree 4 and the real Jacobian conjecture in R2
    Braun, Francisco
    Orefice-Okamoto, Bruna
    JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 2016, 443 (02) : 688 - 706
  • [39] Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks
    Bonifaci, Vincenzo
    Marchetti-Spaccamela, Alberto
    Megow, Nicole
    Wiese, Andreas
    IEEE 34TH REAL-TIME SYSTEMS SYMPOSIUM (RTSS 2013), 2013, : 236 - 245
  • [40] Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
    Dima Grigoriev
    Dmitrii V. Pasechnik
    computational complexity, 2005, 14 : 20 - 52