|
Zapiski Nauchnykh Seminarov POMI, 2021, Volume 507, Pages 26–34
(Mi znsl7159)
|
|
|
|
Tensor networks and the enumerative geometry of graphs
P. G. Zografab a St. Petersburg Department of Steklov Institute of Mathematics, St. Petersburg, Russia
b Chebyshev Laboratory, St. Petersburg State University, St. Petersburg, Russia
Abstract:
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.
Key words and phrases:
tensor network, $d$-regular subgraph, $d$-factor, edge coloring.
Received: 18.11.2021
Citation:
P. G. Zograf, “Tensor networks and the enumerative geometry of graphs”, Representation theory, dynamical systems, combinatorial methods. Part XXXIII, Zap. Nauchn. Sem. POMI, 507, POMI, St. Petersburg, 2021, 26–34
Linking options:
https://www.mathnet.ru/eng/znsl7159 https://www.mathnet.ru/eng/znsl/v507/p26
|
Statistics & downloads: |
Abstract page: | 97 | Full-text PDF : | 43 | References: | 23 |
|