Weight systems and invariants of graphs and embedded graphs

M. E. Kazarian   ; S. K. Lando

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 77 (2022) no. 5, pp. 893-942

Résumé

The recent progress in the theory of weight systems, which are functions on the chord diagrams satisfying the so-called 4-relations, is described. Most attention is given to methods for constructing concrete weight systems. The two main sources of the constructions discussed are invariants of the intersection graphs of chord diagrams that satisfy the 4-term relations for graphs, and metrized Lie algebras. In the simplest non-trivial case of the metrized Lie algebra $\mathfrak{sl}(2)$ the recent results on the explicit form of the generating functions of the values of a weight system on important series of chord diagrams are presented. The computations are based on the Chmutov–Varchenko recurrence relations. Another recent result presented is the construction of recurrence relations for the values of the $\mathfrak{gl}(N)$-weight system. These relations are based on Kazarian's idea of extending the $\mathfrak{gl}(N)$-weight system to arbitrary permutations. In a number of recent papers an approach to the extension of weight systems and graph invariants to arbitrary embedded graphs was proposed, which is based on an analysis of the structure of the relevant Hopf algebras. The main principles of this approach are described. Weight systems defined on embedded graphs correspond to finite-order invariants of links ('knots' with several components). Bibliography: 65 titles.

Détail

Keywords: knot and link invariant, weight system, embedded graph, delta-matroid, Lie algebra, Hopf algebra.
Mots-clés : graph invariant

Bibliographie

[1] N. H. Abel, “Beweis eines Ausdruckes, von welchem die Binomial-Formel ein einzelner Fall ist”, J. Reine Angew. Math., 1826:1 (1826), 159–160 | DOI | MR | Zbl

[2] M. Aguiar, N. Bergeron, and F. Sottile, “Combinatorial Hopf algebras and generalized Dehn–Sommerville relations”, Compos. Math., 142:1 (2006), 1–30 | DOI | MR | Zbl

[3] M. Aguiar and S. Mahajan, “Hopf monoids in the category of species”, Hopf algebras and tensor categories, Contemp. Math., 585, Amer. Math. Soc., Providence, RI, 2013, 17–124 | DOI | MR | Zbl

[4] R. Arratia, B. Bollobás, and G. B. Sorkin, “A two-variable interlace polynomial”, Combinatorica, 24:4 (2004), 567–584 | DOI | MR | Zbl

[5] D. Bar-Natan, “On the Vassiliev knot invariants”, Topology, 34:2 (1995), 423–472 | DOI | MR | Zbl

[6] D. Bar-Natan and H. T. Vo, “Proof of a conjecture of Kulakova et al. related to the $\mathfrak{sl}_2$ weight system”, European J. Combin., 45 (2015), 65–70 | DOI | MR | Zbl

[7] A. Bigeni, “A generalization of the Kreweras triangle through the universal $\mathfrak{sl}_2$ weight system”, J. Combin. Theory Ser. A, 161 (2019), 309–326 | DOI | MR | Zbl

[8] B. Bollobás and O. Riordan, “A polynomial of graphs on surfaces”, Math. Ann., 323:1 (2002), 81–96 | DOI | MR | Zbl

[9] A. Bouchet, “Maps and $\Delta$-matroids”, Discrete Math., 78:1-2 (1989), 59–71 | DOI | MR | Zbl

[10] A. Bouchet, “Circle graph obstructions”, J. Combin. Theory Ser. B, 60:1 (1994), 107–144 | DOI | MR | Zbl

[11] A. Bouchet and A. Duchamp, “Representability of $\Delta$-matroids over $\mathbf{GF}(2)$”, Linear Algebra Appl., 146 (1991), 67–78 | DOI | MR | Zbl

[12] R. Brijder and H. J. Hoogeboom, “Interlace polynomials for multimatroids and delta-matroids”, European J. Combin., 40 (2014), 142–167 | DOI | MR | Zbl

[13] V. M. Buchstaber and N. Yu. Erokhovets, “Polytopes, Fibonacci numbers, Hopf algebras, and quasi-symmetric functions”, Uspekhi Mat. Nauk, 66:2(398) (2011), 67–162 ; English transl. in Russian Math. Surveys, 66:2 (2011), 271–367 | DOI | MR | Zbl | DOI

[14] B. S. Bychkov and A. V. Mikhailov, “Polynomial graph invariants and linear hierarchies”, Uspekhi Mat. Nauk, 74:2(446) (2019), 189–190 ; English transl. in Russian Math. Surveys, 74:2 (2019), 366–368 | DOI | MR | Zbl | DOI

[15] S. Chmutov, “Generalized duality for graphs on surfaces and the signed Bollobás–Riordan polynomial”, J. Combin. Theory Ser. B, 99:3 (2009), 617–638 | DOI | MR | Zbl

[16] S. V. Chmutov, S. V. Duzhin, and S. K. Lando, “Vassiliev knot invariants. III. Forest algebra and weighted graphs”, Singularities and bifurcations, Adv. Soviet Math., 21, Amer. Math. Soc., Providence, RI, 1994, 135–145 | DOI | MR | Zbl

[17] S. Chmutov, S. Duzhin, and J. Mostovoy, Introduction to Vassiliev knot invariants, Cambridge Univ. Press, Cambridge, 2012, xvi+504 pp. | DOI | MR | Zbl

[18] S. Chmutov, M. Kazarian, and S. Lando, “Polynomial graph invariants and the KP hierarchy”, Selecta Math. (N. S.), 26:3 (2020), 34, 22 pp. | DOI | MR | Zbl

[19] S. V. Chmutov and S. K. Lando, “Mutant knots and intersection graphs”, Algebr. Geom. Topol., 7:3 (2007), 1579–1598 | DOI | MR | Zbl

[20] S. V. Chmutov and A. N. Varchenko, “Remarks on the Vassiliev knot invariants coming from $sl_2$”, Topology, 36:1 (1997), 153–178 | DOI | MR | Zbl

[21] C. Chun, I. Moffatt, S. D. Noble, and R. Rueckriemen, “On the interplay between embedded graphs and delta-matroids”, Proc. Lond. Math. Soc. (3), 118:3 (2019), 675–700 | DOI | MR | Zbl

[22] C. Chun, I. Moffatt, S. D. Noble, and R. Rueckriemen, “Matroids, delta-matroids and embedded graphs”, J. Combin. Theory Ser. A, 167 (2019), 7–59 | DOI | MR | Zbl

[23] O. T. Dasbach, D. Futer, E. Kalfagianni, Xiao-Song Lin, and N. Stoltzfus, “Alternating sum formulae for the determinant and other link invariants”, J. Knot Theory Ramifications, 19:6 (2010), 765–782 | DOI | MR | Zbl

[24] R. Dogra and S. Lando, Skew characteristic polynomial of graphs and embedded graphs, 2022, 26 pp., arXiv: 2201.07084

[25] A. Dunaykin and V. Zhukov, “Transition polynomial as a weight system for binary delta-matroids”, Mosc. Math. J., 22:1 (2022), 69–81 | DOI | MR | Zbl

[26] S. V. Duzhin and M. V. Karev, “Detecting the orientation of string links by finite type invariants”, Funktsional. Anal. i Prilozhen., 41:3 (2007), 48–59 ; English transl. in Funct. Anal. Appl., 41:3 (2007), 208–216 | DOI | MR | Zbl | DOI

[27] J. A. Ellis-Monaghan and I. Moffatt, Graphs on surfaces. Dualities, polynomials, and knots, SpringerBriefs Math., Springer, New York, 2013, xii+139 pp. | DOI | MR | Zbl

[28] J. A. Ellis-Monaghan and I. Moffatt, “The Las Vergnas polynomial for embedded graphs”, European J. Combin., 50 (2015), 97–114 | DOI | MR | Zbl

[29] J. M. Figueroa-O'Farrill, T. Kimura, and A. Vaintrob, “The universal Vassiliev invariant for the Lie superalgebra $gl(1|1)$”, Comm. Math. Phys., 185:1 (1997), 93–127 | DOI | MR | Zbl

[30] P. A. Filippova, “Values of the $\mathfrak{sl}_2$ weight system on complete bipartite graphs”, Funktsional. Anal. i Prilozhen., 54:3 (2020), 73–93 ; English transl. in Funct. Anal. Appl., 54:3 (2020), 208–223 | DOI | MR | Zbl | DOI

[31] P. A. Filippova, “Values of the $\mathfrak{sl}_2$ weight system on a family of graphs that are not the intersection graphs of chord diagrams”, Mat. Sb., 213:2 (2022), 115–148 ; English transl. in Sb. Math., 213:2 (2022), 235–267 | DOI | MR | Zbl | DOI

[32] S. Heil and C. Ji, “On an algorithm for comparing the chromatic symmetric functions of trees”, Australas. J. Combin., 75:2 (2019), 210–222 | MR | Zbl

[33] J. Huh, “Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs”, J. Amer. Math. Soc., 25:3 (2012), 907–927 | DOI | MR | Zbl

[34] F. Jaeger, “On transition polynomial for 4-regular graphs”, Cycles and rays (Montreal, PQ 1987), NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., 301, Kluwer Acad. Publ., Dordrecht, 1990, 123–150 | DOI | MR | Zbl

[35] S. A. Joni and G.-C. Rota, “Coalgebras and bialgebras in combinatorics”, Stud. Appl. Math., 61:2 (1979), 93–139 | DOI | MR | Zbl

[36] B. B. Kadomtsev and V. I. Petviashvili, “On the stability of solitary waves in weakly dispersive media”, Dokl. Akad. Nauk SSSR, 192:4 (1970), 753–756 ; English transl. in Soviet Phys. Dokl., 15 (1970), 539–541 | Zbl

[37] M. E. Kazarian and S. K. Lando, “Combinatorial solutions to integrable hierarchies”, Uspekhi Mat. Nauk, 70:3(423) (2015), 77–106 ; English transl. in Russian Math. Surveys, 70:3 (2015), 453–482 | DOI | MR | Zbl | DOI

[38] N. Kodaneva, The interlace polynomial of binary delta-matroids and link invariants, 2020, 17 pp., arXiv: 2002.12440

[39] M. Kontsevich, “Vassiliev knot invariants”, I. M. Gel'fand seminar, Part 2, Adv. Soviet Math., 16, Part 2, Amer. Math. Soc., Providence, RI, 1993, 137–150 | DOI | MR | Zbl

[40] E. Krasilnikov, “An extension of the $\mathfrak{sl}_2$ weight system to graphs with $n\le 8$ vertices”, Arnold Math. J., 7:4 (2021), 609–618 | DOI | MR | Zbl

[41] E. Kulakova, S. Lando, T. Mukhutdinova, and G. Rybnikov, “On a weight system conjecturally related to $\mathfrak{sl}_2$”, European J. Combin., 41 (2014), 266–277 | DOI | MR | Zbl

[42] S. Lando, “On primitive elements in the bialgebra of chord diagrams”, Topics in singularity theory, Amer. Math. Soc. Transl. Ser. 2, 180, Adv. Math. Sci., 34, Amer. Math. Soc., Providence, RI, 1997, 167–174 | DOI | MR | Zbl

[43] S. K. Lando, “On a Hopf algebra in graph theory”, J. Combin. Theory Ser. B, 80:1 (2000), 104–121 | DOI | MR | Zbl

[44] S. K. Lando, “$J$-invariants of plane curves and framed chord diagrams”, Funktsional. Anal. i Prilozhen., 40:1 (2006), 1–13 ; English transl. in Funct. Anal. Appl., 40:1 (2006), 1–10 | DOI | MR | Zbl | DOI

[45] S. Lando and V. Zhukov, “Delta-matroids and Vassiliev invariants”, Mosc. Math. J., 17:4 (2017), 741–755 | DOI | MR | Zbl

[46] S. K. Lando and A. K. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia Math. Sci., 141, Low-Dimensional Topology, II, Springer-Verlag, Berlin, 2004, xvi+455 pp. | DOI | MR | Zbl

[47] J. W. Milnor and J. C. Moore, “On the structure of Hopf algebras”, Ann. of Math. (2), 81:2 (1965), 211–264 | DOI | MR | Zbl

[48] I. Moffatt and E. Mphako-Banda, “Handle slides for delta-matroids”, European J. Combin., 59 (2017), 23–33 | DOI | MR | Zbl

[49] A. Morse, “The interlace polynomial”, Graph polynomials, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2017, 1–23 | DOI | MR | Zbl

[50] M. Nenasheva and V. Zhukov, “An extension of Stanley's chromatic symmetric function to binary delta-matroids”, Discrete Math., 344:11 (2021), 112549, 10 pp. | DOI | MR | Zbl

[51] N. Netrusova, The interlace polynomial and knot invariants, preprint, 2011

[52] S. D. Noble and D. J. A. Welsh, “A weighted graph polynomial from chromatic invariants of knots”, Ann. Inst. Fourier (Grenoble), 49:3 (1999), 1057–1087 | DOI | MR | Zbl

[53] A. Okounkov and G. Olshanskii, “Shifted Schur functions”, Algebra i Analiz, 9:2 (1997), 73–146 ; English transl. in St. Petersburg Math. J., 9:2 (1998), 239–300 | MR | Zbl

[54] G. I. Olshanskii, “Representations of infinite-dimensional classical groups, limits of enveloping algebras, and Yangians”, Topics in representation theory, Adv. Soviet Math., 2, Amer. Math. Soc., Providence, RI, 1991, 1–66 | DOI | MR | Zbl

[55] S. M. Roman and G.-C. Rota, “The umbral calculus”, Adv. Math., 27:2 (1978), 95–188 | DOI | MR | Zbl

[56] G.-C. Rota, J. Shen, and B. D. Taylor, “All polynomials of binomial type are represented by Abel polynomials”, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4), 25:3-4 (1997), 731–738 | MR | Zbl

[57] W. R. Schmitt, “Incidence Hopf algebras”, J. Pure Appl. Algebra, 96:3 (1994), 299–330 | DOI | MR | Zbl

[58] W. R. Schmitt, “Hopf algebra methods in graph theory”, J. Pure Appl. Algebra, 101:1 (1995), 77–90 | DOI | MR | Zbl

[59] E. Soboleva, “Vassiliev knot invariants coming from Lie algebras and $4$-invariants”, J. Knot Theory Ramifications, 10:1 (2001), 161–169 | DOI | MR | Zbl

[60] R. P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph”, Adv. Math., 111:1 (1995), 166–194 | DOI | MR | Zbl

[61] V. A. Vassiliev, “Cohomology of knot spaces”, Theory of singularities and its applications, Adv. Soviet Math., 1, Amer. Math. Soc., Providence, RI, 1990, 23–69 | DOI | MR | Zbl

[62] Z. Yang, On values of $\mathfrak{sl}_3$ weight system on chord diagrams whose intersection graph is complete bipartite, 2021, 17 pp., arXiv: 2102.00888

[63] Z. Yang, New approaches to $\mathfrak{gl}(N)$ weight system, 2022, 18 pp., arXiv: 2202.12225

[64] Z. Yang, On the Lie superalgebra $\mathfrak{gl}(m|n)$ weight system, 2022, 16 pp., arXiv: 2207.00327

[65] P. Zakorko, “Values of the $\mathfrak{sl}_2$-weight system on chord diagrams with complete intersection graph” (to appear)