Your language?
Oct, 2017
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31

グラフの多項式不変量

グラフ , その 調 べることにより グラフ というのは , 調 べる ている このような graph polynomial については , Ellis-Monaghan Merino survey [ EMM11a EMM11b ] ある

有名 graph polynomial として chromatic polynomial がある Hersh Swartz [ HS08 ] によると Birkhoff により 1912 導入 されたらしい Chia による [ Chi97 ] がある Steingrimsson [ Ste01 ] , chromatic polynomial がある simplicial complex Stanley-Reisner ideal Hilbert series として わせることを した

  • chromatic polynomial
  • dichromatic polynomial
  • multivariate chromatic polynomial ( [ Whi11 ] )

Stanley による symmetric function としての [ Sta95 ] もある その refinement として Shareshian Wachs [ SW12 SW16 ] により chromatic quasisymmetric function 導入 された

  • chromatic symmetric function
  • chromatic quasisymmetric function

, Tutte [ Tut49 ] グラフ chromatic polynomial dual となるべき ものとして した flow polynomial というものもある

  • flow polynomial

その としては , Chen Stanley [ CS12 ] えられている modular flow polynomial とか integral flow polynomial とい たものがある

にも えられている

Ellis-Monaghan Merino [ EMM11a ] によると , そのような deletion/contraction reduction つものについては , Tutte polynomial universal なものらしい それを ribbon graph した Bollobas-Riordan polynomial というものもある

これらの 不変 , Khovanov Jones polynomial categorification , categorify する ことができる

このような から , グラフ 不変 不変 調 べるというのは , である Huggett Moffatt [ HM11 ] によると , [ Thi87 Jae88 Hug05 Mof08 DFK + 08 CP07 CV08 ] などが ある

があれば , その えたくなるが , Jackson [ Jac03 ] chromatic polynomial flow polynomial 分布 についての survey いている それ によると , 分布 については , Thomassen [ Tho97 ] により [ 3227 , ) dense であることが ている また , Sokal [ Sok04 ] より , 全体 dense であることが ている Jackson Sokal [ JS09 ] , それらの として multivariate Tutte polynomial nonzero region えている Ok Perrett [ OP ] , グラフ Tutte polynomial , のある dense subset にな ていることを して いる

グラフ については , グラフ chromatic polynomial 絶対 maximum degree bound されることが , Sokal [ Sok01 ] により されて いる

Tutte polynomial Potts model また Ising model partition function として Ising polynomial という 2 あるいは 3 されている Kotek [ Kot12 ] など

  • Ising polynomial

Chromatic polynomial flow polynomial arrangement characteristic polynomial として わすことができる この から , chromatic polynomial log-concavity する しているのは , Huh [ Huh12 ] , そして Katz との によるその [ HK12 ] である toric variety づけて していて

Tutte polynomial , subspace arrangement characteristic polynomial として わせないかという えているのは , Beifang Chen [ Che ] ある

また , Eastwood Huggett [ EH07 ] , configuration space braid arrangement であることに , graphic arrangement configuration space したものを えている として ると , その Euler として グラフ chromatic polynomial られることを して いる

にも , chromatic polynomial としては , Kac-Moody Lie algebra いたも [ VV15 ] もある

Graph hypergraph して しようと えるのは であるが , simplicial complex CW complex への えられている Møller Nord [ MN16 ] Beck Breuer Godkin Martin [ BBGM14 ] などである では , chromatic polynomial flow polynomial などの CW れている

グラフ として された グラフ として , Kirchhoff polynomial ある

  • Kirchhoff polynomial

その , affine space hypersurface になるので , から 調 べることが えられる , グラフ として Feynman graph をと たときが , Feynman motive 理論 として 研究 されている

  • Feynman motive

えば , Marcolli Tabuada [ MT ] Introduction げられている とよい この , Bloch, Esnault, Kreimer [ BEK ] のようで ある

なる アイデア づいた としては , Leinster graph magnitude [ Lei ] がある

  • graph magnitude

すように , 導入 した metric space magnitude , small category Euler , アイデア づくものである また , その categorification Hepworth Willerton [ HW ] により されている

References

[ABS04]     Richard Arratia, Béla Bollobás, and Gregory B. Sorkin. The interlace polynomial of a graph. J. Combin. Theory Ser. B , 92(2):199–233, 2004, arXiv:math/0209045 .

[AGM10]     Ilia Averbouch, Benny Godlin, and J. A. Makowsky. An extension of the bivariate polynomial. European J. Combin. , 31(1):1–17, 2010, http://dx.doi.org/10.1016/j.ejc.2009.05.006 .

[AvdH04]     Martin Aigner and Hein van der Holst. Interlace polynomials. Linear Algebra Appl. , 377:11–30, 2004, http://dx.doi.org/10.1016/j.laa.2003.06.010 .

[BBGM14]     Matthias Beck, Felix Breuer, Logan Godkin, and Jeremy L. Martin. Enumerating colorings, tensions and flows in cell complexes. J. Combin. Theory Ser. A , 122:82–106, 2014, arXiv:1212.6539 .

[BEK]     Spencer Bloch, Hélène Esnault, and Dirk Kreimer. On Motives Associated to Graph Polynomials, arXiv:math/0510011 .

[Che]     Beifang Chen. Orientations, lattice polytopes, and group arrangements III: Cartesian product arrangements and applications to the Tutte type polynomials of graphs, arXiv:1007.2453 .

[Chi97]     G. L. Chia. A bibliography on chromatic polynomials. Discrete Math. , 172(1-3):175–191, 1997, http://dx.doi.org/10.1016/S0012-365X(97)90031-5 . Chromatic polynomials and related topics (Shanghai, 1994).

[CP07]     Sergei Chmutov and Igor Pak. The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial. Mosc. Math. J. , 7(3):409–418, 573, 2007, arXiv:math/0609012 .

[CS12]     Beifang Chen and Richard P. Stanley. Orientations, lattice polytopes, and group arrangements II: Modular and integral flow polynomials of graphs. Graphs Combin. , 28(6):751–779, 2012, arXiv:1105.2677 .

[CV08]     Sergei Chmutov and Jeremy Voltz. Thistlethwaite’s theorem for virtual links. J. Knot Theory Ramifications , 17(10):1189–1198, 2008, arXiv:0704.1310 .

[DFK + 08]     Oliver T. Dasbach, David Futer, Efstratia Kalfagianni, Xiao-Song Lin, and Neal W. Stoltzfus. The Jones polynomial and graphs on surfaces. J. Combin. Theory Ser. B , 98(2):384–399, 2008, arXiv:math/0605571 .

[EH07]     Michael Eastwood and Stephen Huggett. Euler characteristics and chromatic polynomials. European J. Combin. , 28(6):1553–1560, 2007, http://dx.doi.org/10.1016/j.ejc.2006.09.005 .

[EMM11a]     Joanna A. Ellis-Monaghan and Criel Merino. Graph polynomials and their applications I: The Tutte polynomial. In Structural analysis of complex networks , pages 219–255. Birkhäuser/Springer, New York, 2011, arXiv:0803.3079 .

[EMM11b]     Joanna A. Ellis-Monaghan and Criel Merino. Graph polynomials and their applications II: Interrelations and interpretations. In Structural analysis of complex networks , pages 257–292. Birkhäuser/Springer, New York, 2011, arXiv:0806.4699 .

[HK12]     June Huh and Eric Katz. Log-concavity of characteristic polynomials and the Bergman fan of matroids. Math. Ann. , 354(3):1103–1116, 2012, arXiv:1104.2519 .

[HM11]     Stephen Huggett and Iain Moffatt. Expansions for the Bollobás-Riordan polynomial of separable ribbon graphs. Ann. Comb. , 15(4):675–706, 2011, arXiv:0710.4266 .

[HS08]     Patricia Hersh and Ed Swartz. Coloring complexes and arrangements. J. Algebraic Combin. , 27(2):205–214, 2008, arXiv:0706.3657 .

[Hug05]     Stephen Huggett. On tangles and matroids. J. Knot Theory Ramifications , 14(7):919–929, 2005, http://dx.doi.org/10.1142/S0218216505004147 .

[Huh12]     June Huh. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. J. Amer. Math. Soc. , 25(3):907–927, 2012, arXiv:1008.4749 .

[HW]     Richard Hepworth and Simon Willerton. Categorifying the magnitude of a graph, arXiv:1505.04125 .

[Jac03]     Bill Jackson. Zeros of chromatic and flow polynomials of graphs. J. Geom. , 76(1-2):95–109, 2003, arXiv:math/0205047 . Combinatorics, 2002 (Maratea).

[Jae88]     François Jaeger. Tutte polynomials and link polynomials. Proc. Amer. Math. Soc. , 103(2):647–654, 1988, http://dx.doi.org/10.2307/2047194 .

[JS09]     Bill Jackson and Alan D. Sokal. Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids. J. Combin. Theory Ser. B , 99(6):869–903, 2009, arXiv:0806.3249 .

[Kot12]     Tomer Kotek. Complexity of Ising polynomials. Combin. Probab. Comput. , 21(5):743–772, 2012, arXiv:1110.3639 .

[Lei]     Tom Leinster. The magnitude of a graph, arXiv:1401.4623 .

[MN16]     Jesper M. Møller and Gesche Nord. Chromatic polynomials of simplicial complexes. Graphs Combin. , 32(2):745–772, 2016, arXiv:1212.0305 .

[Mof08]     Iain Moffatt. Knot invariants and the Bollobás-Riordan polynomial of embedded graphs. European J. Combin. , 29(1):95–107, 2008, arXiv:math/0605466 .

[MT]     Matilde Marcolli and Goncalo Tabuada. Feynman quadrics-motive of the massive sunset graph, arXiv:1705.10307 .

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

[Sok01]     Alan D. Sokal. Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combin. Probab. Comput. , 10(1):41–77, 2001, arXiv:cond-mat/9904146 .

[Sok04]     Alan D. Sokal. Chromatic roots are dense in the whole complex plane. Combin. Probab. Comput. , 13(2):221–261, 2004, arXiv:cond-mat/0012369 .

[Sta95]     Richard P. Stanley. A symmetric function generalization of the chromatic polynomial of a graph. Adv. Math. , 111(1):166–194, 1995, http://dx.doi.org/10.1006/aima.1995.1020 .

[Ste01]     Einar Steingrímsson. The coloring ideal and coloring complex of a graph. J. Algebraic Combin. , 14(1):73–84, 2001, arXiv:math/0104063 .

[SW12]     John Shareshian and Michelle L. Wachs. Chromatic quasisymmetric functions and Hessenberg varieties. In Configuration spaces , volume 14 of CRM Series , pages 433–460. Ed. Norm., Pisa, 2012, arXiv:1106.4287 .

[SW16]     John Shareshian and Michelle L. Wachs. Chromatic quasisymmetric functions. Adv. Math. , 295:497–551, 2016, arXiv:1405.4629 .

[Thi87]     Morwen B. Thistlethwaite. A spanning tree expansion of the Jones polynomial. Topology , 26(3):297–309, 1987, http://dx.doi.org/10.1016/0040-9383(87)90003-6 .

[Tho97]     Carsten Thomassen. The zero-free intervals for chromatic polynomials of graphs. Combin. Probab. Comput. , 6(4):497–506, 1997, http://dx.doi.org/10.1017/S0963548397003131 .

[Tra10]     Lorenzo Traldi. A bracket polynomial for graphs. II. Links, Euler circuits and marked graphs. J. Knot Theory Ramifications , 19(4):547–586, 2010, arXiv:0901.1451 .

[Tra11a]     Lorenzo Traldi. A bracket polynomial for graphs, III. Vertex weights. J. Knot Theory Ramifications , 20(3):435–462, 2011, arXiv:0905.4879 .

[Tra11b]     Lorenzo Traldi. A bracket polynomial for graphs, IV. Undirected Euler circuits, graph-links and multiply marked graphs. J. Knot Theory Ramifications , 20(8):1093–1128, 2011, arXiv:1003.1560 .

[Tra13]     Lorenzo Traldi. On the interlace polynomials. J. Combin. Theory Ser. B , 103(1):184–208, 2013, arXiv:1008.0091 .

[Tut49]     W. T. Tutte. On the imbedding of linear graphs in surfaces. Proc. London Math. Soc. (2) , 51:474–483, 1949.

[TZ09]     Lorenzo Traldi and Louis Zulli. A bracket polynomial for graphs. I. J. Knot Theory Ramifications , 18(12):1681–1709, 2009, arXiv:0808.3392 .

[VV15]     R. Venkatesh and Sankaran Viswanath. Chromatic polynomials of graphs from Kac–Moody algebras. J. Algebraic Combin. , 41(4):1133–1142, 2015, arXiv:1303.1148 .

[Whi11]     Jacob A. White. On multivariate chromatic polynomials of hypergraphs and hyperedge elimination. Electron. J. Combin. , 18(1):Paper 160, 17, 2011, arXiv:1012.3423 .

[Yam89]     Shuji Yamada. An invariant of spatial graphs. J. Graph Theory , 13(5):537–551, 1989, http://dx.doi.org/10.1002/jgt.3190130503 .