グラフの多項式の零点

グラフ からは, 様々な方法で多項式が定義されるが, その零点を調べている人もいる。

Jackson は [Jac03] で chromatic polynomial と flow polynomial の 零点の分布についての survey を書いている。 それによると, 実解の分布については, Thomassen の [Tho97] により \([\frac{32}{27},\infty )\) でdenseであることが分かっている。 また複素数解は, Sokal の結果 [Sokb] により, 複素平面全体で dense であることが分かっている。 Jackson と Sokal は [JS09] で, それらの結果の一般化として multivariate Tutte polynomial の nonzero region を考えている。 Ok と Perrett [OP] は, グラフの Tutte polynomial の零点は, 平面のある領域の dense subset になっていることを示している。

個別のグラフについては, グラフの chromatic polynomial の零点の絶対値は, maximum degree の定数倍でboundされることが, Sokal [Soka] により示されている。

References

[Jac03]

Bill Jackson. “Zeros of chromatic and flow polynomials of graphs”. In: J. Geom. 76.1-2 (2003). Combinatorics, 2002 (Maratea), pp. 95–109. arXiv: math/0205047.

[JS09]

Bill Jackson and Alan D. Sokal. “Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids”. In: J. Combin. Theory Ser. B 99.6 (2009), pp. 869–903. arXiv: 0806.3249. url: http://dx.doi.org/10.1016/j.jctb.2009.03.002.

[OP]

Seongmin Ok and Thomas J. Perrett. Density of Zeros of the Tutte Polynomial. arXiv: 1608.08747.

[Soka]

Alan D. Sokal. Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions. arXiv: cond-mat/9904146.

[Sokb]

Alan D. Sokal. Chromatic roots are dense in the whole complex plane. arXiv: cond-mat/0012369.

[Tho97]

Carsten Thomassen. “The zero-free intervals for chromatic polynomials of graphs”. In: Combin. Probab. Comput. 6.4 (1997), pp. 497–506. url: https://doi.org/10.1017/S0963548397003131.