Weight systems and invariants of graphs and embedded graphs

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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 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 gl(N)-weight system. These relations are based on Kazarian's idea of extending the 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.

About the authors

Maxim Eduardovich Kazarian

HSE University; Skolkovo Institute of Science and Technology

Email: kazarian@mccme.ru
Doctor of physico-mathematical sciences, no status

Sergei Konstantinovich Lando

HSE University; Skolkovo Institute of Science and Technology

Email: lando@mccme.ru
Doctor of physico-mathematical sciences

References

  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
  2. M. Aguiar, N. Bergeron, F. Sottile, “Combinatorial Hopf algebras and generalized Dehn–Sommerville relations”, Compos. Math., 142:1 (2006), 1–30
  3. M. Aguiar, 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
  4. R. Arratia, B. Bollobas, G. B. Sorkin, “A two-variable interlace polynomial”, Combinatorica, 24:4 (2004), 567–584
  5. D. Bar-Natan, “On the Vassiliev knot invariants”, Topology, 34:2 (1995), 423–472
  6. D. Bar-Natan, H. T. Vo, “Proof of a conjecture of Kulakova et al. related to the mathfraksl2 weight system”, European J. Combin., 45 (2015), 65–70
  7. A. Bigeni, “A generalization of the Kreweras triangle through the universal mathfraksl2 weight system”, J. Combin. Theory Ser. A, 161 (2019), 309–326
  8. B. Bollobas, O. Riordan, “A polynomial of graphs on surfaces”, Math. Ann., 323:1 (2002), 81–96
  9. A. Bouchet, “Maps and Delta-matroids”, Discrete Math., 78:1-2 (1989), 59–71
  10. A. Bouchet, “Circle graph obstructions”, J. Combin. Theory Ser. B, 60:1 (1994), 107–144
  11. A. Bouchet, A. Duchamp, “Representability of Delta-matroids over mathbfGF(2)”, Linear Algebra Appl., 146 (1991), 67–78
  12. R. Brijder, H. J. Hoogeboom, “Interlace polynomials for multimatroids and delta-matroids”, European J. Combin., 40 (2014), 142–167
  13. В. М. Бухштабер, Н. Ю. Ероховец, “Многогранники, числа Фибоначчи, алгебры Хопфа и квазисимметрические функции”, УМН, 66:2(398) (2011), 67–162
  14. Б. С. Бычков, А. В. Михайлов, “Полиномиальные инварианты графов и иерархии линейных уравнений”, УМН, 74:2(446) (2019), 189–190
  15. S. Chmutov, “Generalized duality for graphs on surfaces and the signed Bollobas–Riordan polynomial”, J. Combin. Theory Ser. B, 99:3 (2009), 617–638
  16. S. V. Chmutov, S. V. Duzhin, 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
  17. S. Chmutov, S. Duzhin, J. Mostovoy, Introduction to Vassiliev knot invariants, Cambridge Univ. Press, Cambridge, 2012, xvi+504 pp.
  18. S. Chmutov, M. Kazarian, S. Lando, “Polynomial graph invariants and the KP hierarchy”, Selecta Math. (N. S.), 26:3 (2020), 34, 22 pp.
  19. S. V. Chmutov, S. K. Lando, “Mutant knots and intersection graphs”, Algebr. Geom. Topol., 7:3 (2007), 1579–1598
  20. S. V. Chmutov, A. N. Varchenko, “Remarks on the Vassiliev knot invariants coming from sl2”, Topology, 36:1 (1997), 153–178
  21. C. Chun, I. Moffatt, S. D. Noble, R. Rueckriemen, “On the interplay between embedded graphs and delta-matroids”, Proc. Lond. Math. Soc. (3), 118:3 (2019), 675–700
  22. C. Chun, I. Moffatt, S. D. Noble, R. Rueckriemen, “Matroids, delta-matroids and embedded graphs”, J. Combin. Theory Ser. A, 167 (2019), 7–59
  23. O. T. Dasbach, D. Futer, E. Kalfagianni, Xiao-Song Lin, N. Stoltzfus, “Alternating sum formulae for the determinant and other link invariants”, J. Knot Theory Ramifications, 19:6 (2010), 765–782
  24. R. Dogra, S. Lando, Skew characteristic polynomial of graphs and embedded graphs, 2022, 26 pp.
  25. A. Dunaykin, V. Zhukov, “Transition polynomial as a weight system for binary delta-matroids”, Mosc. Math. J., 22:1 (2022), 69–81
  26. С. В. Дужин, М. В. Карев, “Определение ориентации струнных зацеплений при помощи инвариантов конечного типа”, Функц. анализ и его прил., 41:3 (2007), 48–59
  27. J. A. Ellis-Monaghan, I. Moffatt, Graphs on surfaces. Dualities, polynomials, and knots, SpringerBriefs Math., Springer, New York, 2013, xii+139 pp.
  28. J. A. Ellis-Monaghan, I. Moffatt, “The Las Vergnas polynomial for embedded graphs”, European J. Combin., 50 (2015), 97–114
  29. J. M. Figueroa-O'Farrill, T. Kimura, A. Vaintrob, “The universal Vassiliev invariant for the Lie superalgebra gl(1|1)”, Comm. Math. Phys., 185:1 (1997), 93–127
  30. П. A. Филиппова, “Значения весовой системы, отвечающей алгебре Ли mathfraksl2, на полных двудольных графах”, Функц. анализ и его прил., 54:3 (2020), 73–93
  31. П. А. Филиппова, “Значения mathfraksl2-весовой системы на семействе графов, не являющихся графами пересечений хордовых диаграмм”, Матем. сб., 213:2 (2022), 115–148
  32. S. Heil, C. Ji, “On an algorithm for comparing the chromatic symmetric functions of trees”, Australas. J. Combin., 75:2 (2019), 210–222
  33. J. Huh, “Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs”, J. Amer. Math. Soc., 25:3 (2012), 907–927
  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
  35. S. A. Joni, G.-C. Rota, “Coalgebras and bialgebras in combinatorics”, Stud. Appl. Math., 61:2 (1979), 93–139
  36. Б. Б. Кадомцев, В. И. Петвиашвили, “Об устойчивости уединeнных волн в слабо диспергирующих средах”, Докл. АН СССР, 192:4 (1970), 753–756
  37. М. Э. Казарян, С. К. Ландо, “Комбинаторные решения интегрируемых иерархий”, УМН, 70:3(423) (2015), 77–106
  38. N. Kodaneva, The interlace polynomial of binary delta-matroids and link invariants, 2020, 17 pp.
  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
  40. E. Krasilnikov, “An extension of the mathfraksl2 weight system to graphs with nle8 vertices”, Arnold Math. J., 7:4 (2021), 609–618
  41. E. Kulakova, S. Lando, T. Mukhutdinova, G. Rybnikov, “On a weight system conjecturally related to mathfraksl2”, European J. Combin., 41 (2014), 266–277
  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
  43. S. K. Lando, “On a Hopf algebra in graph theory”, J. Combin. Theory Ser. B, 80:1 (2000), 104–121
  44. С. К. Ландо, “J-инварианты орнаментов и оснащенные хордовые диаграммы”, Функц. анализ и его прил., 40:1 (2006), 1–13
  45. S. Lando, V. Zhukov, “Delta-matroids and Vassiliev invariants”, Mosc. Math. J., 17:4 (2017), 741–755
  46. А. К. Звонкин, С. К. Ландо, Графы на поверхностях и их приложения, МЦНМО, М., 2010, 480 с.
  47. J. W. Milnor, J. C. Moore, “On the structure of Hopf algebras”, Ann. of Math. (2), 81:2 (1965), 211–264
  48. I. Moffatt, E. Mphako-Banda, “Handle slides for delta-matroids”, European J. Combin., 59 (2017), 23–33
  49. A. Morse, “The interlace polynomial”, Graph polynomials, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2017, 1–23
  50. M. Nenasheva, V. Zhukov, “An extension of Stanley's chromatic symmetric function to binary delta-matroids”, Discrete Math., 344:11 (2021), 112549, 10 pp.
  51. N. Netrusova, The interlace polynomial and knot invariants, preprint, 2011
  52. S. D. Noble, D. J. A. Welsh, “A weighted graph polynomial from chromatic invariants of knots”, Ann. Inst. Fourier (Grenoble), 49:3 (1999), 1057–1087
  53. А. Окуньков, Г. Ольшанский, “Сдвинутые функции Шура”, Алгебра и анализ, 9:2 (1997), 73–146
  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
  55. S. M. Roman, G.-C. Rota, “The umbral calculus”, Adv. Math., 27:2 (1978), 95–188
  56. G.-C. Rota, Jianhong Shen, 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
  57. W. R. Schmitt, “Incidence Hopf algebras”, J. Pure Appl. Algebra, 96:3 (1994), 299–330
  58. W. R. Schmitt, “Hopf algebra methods in graph theory”, J. Pure Appl. Algebra, 101:1 (1995), 77–90
  59. E. Soboleva, “Vassiliev knot invariants coming from Lie algebras and 4-invariants”, J. Knot Theory Ramifications, 10:1 (2001), 161–169
  60. R. P. Stanley, “A symmetric function generalization of the chromatic polynomial of a graph”, Adv. Math., 111:1 (1995), 166–194
  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
  62. Zhuoke Yang, On values of mathfraksl3 weight system on chord diagrams whose intersection graph is complete bipartite, 2021, 17 pp.
  63. Zhuoke Yang, New approaches to mathfrakgl(N) weight system, 2022, 18 pp.
  64. Zhuoke Yang, On the Lie superalgebra mathfrakgl(m|n) weight system, 2022, 16 pp.
  65. П. Закорко, “Значения mathfraksl2-весовой системы на хордовых диаграммах с полным графом пересечения” (в печати)

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2022 Kazarian M.E., Lando S.K.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».