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 条
  • [41] Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
    Dima Grigoriev
    Dmitrii V. Pasechnik
    computational complexity, 2005, 14 : 20 - 52
  • [42] An adaptive method for consistent estimation of real-valued non-minimum phase zeros in stable LTI systems
    Rojas, Cristian R.
    Hjalmarsson, Hakan
    Gerencser, Laszlo
    Martensson, Jonas
    AUTOMATICA, 2011, 47 (07) : 1388 - 1398
  • [43] Self-similar scaling of density in complex real-world networks
    Blagus, Neli
    Subelj, Lovro
    Bajec, Marko
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2012, 391 (08) : 2794 - 2802
  • [44] Rapid adaptation of predictive models during language comprehension: Aperiodic EEG slope, individual alpha frequency and idea density modulate individual differences in real-time model updating
    Bornkessel-Schlesewsky, Ina
    Sharrad, Isabella
    Howlett, Caitlin A.
    Alday, Phillip M.
    Corcoran, Andrew W.
    Bellan, Valeria
    Wilkinson, Erica
    Kliegl, Reinhold
    Lewis, Richard L.
    Small, Steven L.
    Schlesewsky, Matthias
    FRONTIERS IN PSYCHOLOGY, 2022, 13