Geodesic
Tensor networks and the enumerative geometry of graphs
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXXIII, Tome 507 (2021), pp. 26-34 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We propose a universal approach to a range of enumeration problems in graphs by means of tensor networks. The key point is in contracting suitably chosen symmetric tensors placed at the vertices of a graph along the edges. This approach leads to simple formulas that count, in particular, the number of $d$-regular subgraphs of an arbitrary graph (including the number of $d$-factors) and proper edge colorings. We briefly discuss the problem of the computational complexity of the algorithms based on these formulas. 
@article{ZNSL_2021_507_a2,
     author = {P. G. Zograf},
     title = {Tensor networks and the enumerative geometry of graphs},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {26--34},
     year = {2021},
     volume = {507},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2021_507_a2/}
}
TY  - JOUR
AU  - P. G. Zograf
TI  - Tensor networks and the enumerative geometry of graphs
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2021
SP  - 26
EP  - 34
VL  - 507
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2021_507_a2/
LA  - en
ID  - ZNSL_2021_507_a2
ER  - 
%0 Journal Article
%A P. G. Zograf
%T Tensor networks and the enumerative geometry of graphs
%J Zapiski Nauchnykh Seminarov POMI
%D 2021
%P 26-34
%V 507
%U http://geodesic.mathdoc.fr/item/ZNSL_2021_507_a2/
%G en
%F ZNSL_2021_507_a2
P. G. Zograf. Tensor networks and the enumerative geometry of graphs. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial methods. Part XXXIII, Tome 507 (2021), pp. 26-34. http://geodesic.mathdoc.fr/item/ZNSL_2021_507_a2/

[1] S. V. Chmutov, S. V. Duzhin, A. I. Kaishev, “The algebra of $3$-graphs”, Trans. Steklov Math. Inst., 221 (1998), 157–186 | Zbl

[2] D. Bar-Natan, “Lie algebras and the four color theorem”, Combinatorica, 17 (1997), 43–52 | DOI | MR | Zbl

[3] I. Markov, Y. Shi, “Simulating quantum computation by contracting tensor networks”, SIAM J. Comput., 38 (2005), 963–981 | DOI

[4] R. Penrose, “Applications of negative dimensional tensors”, Combinatorial Mathematics and Its Applications, ed. D. J. A. Welsh, Academic Press, 1971, 221–244

[5] N. Robertson, P. D. Seymour, “Graph minors. X. Obstructions to tree-decompositions”, J. Combin. Theory Ser. B, 52 (1991), 153–190 | DOI | MR | Zbl

[6] J. Sylvester, “Sur les covariants irréductibles du quantic binaire de huitième order”, Collected Mathematical Papers of J. J. Sylvester, v. III, Cambridge Univ. Press, 1909, 481–488

[7] W. T. Tutte, Graph Theory, Addison-Wesley, 1984 | Zbl

[8] P. Zograf, The enumeration of edge colorings and Hamiltonian cycles by means of symmetric tensors, arXiv: math.CO/0403339

[9] P. Zograf, Tensor networks and the enumeration of regular subgraphs, arXiv: math.CO/0605256