Matiyasevich formula for chromatic and flow polynomials and Feynman amplitudes. (English) Zbl 1511.05109
Summary: Matiyasevich formula which expresses the chromatic polynomial of an arbitrary graph through a linear combination of flow polynomials of subgraphs of the original graph is generalized by using the Feynman amplitudes technique. The article presents a formula expressing a flow polynomial through a linear combination of chromatic polynomials of constricted graphs. This proof is obtained by using the Feynman amplitudes technique. A simple proof of Matiyasevich formula and its consequences are derived by using the same technique.
MSC:
| 05C31 | Graph polynomials |
| 05C15 | Coloring of graphs and hypergraphs |
| 42A38 | Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type |
Keywords:
chromatic polynomial; flow polynomial; Matiyasevich formula; Feynman amplitides; Fourier transformReferences:
| [1] | P. Seymour, ‘‘Nowhere-zero 6-flows,’’ J. Combin. Theory, Ser. B, No 30, 130-135 (1981). · Zbl 0474.05028 |
| [2] | Lovász, L. M.; Thomassen, C.; Wu, Y.; Zhang, C. Q., “Nowhere-zero 3-flows and modulo k-orientations,” J. Combin. Theory, Ser. B, 103, 587-598 (2013) · Zbl 1301.05154 |
| [3] | Kuptsov, A. P.; Lerner, E. Yu.; Mukhamedjanova, S. A., Flow polynomials as Feynman amplitudes and their \(\alpha \), Electron. J. Combin., 24, 11-19 (2017) · Zbl 1355.05136 · doi:10.37236/6396 |
| [4] | Lerner, E. Yu.; Mukhamedjanova, S. A., Explicit formulas forchromatic polynomials of some series-parallel graphs, Electron. J. Combin., 24, 11-19 (2017) |
| [5] | Matiyasevich, Yu. V., On a certain representation of the chromatic polynomial, Diskret. Anal., 91, 61-70 (1977) · Zbl 0435.05025 |
| [6] | Distel, R., Graph Theory (2005), New York: Springer, New York |
| [7] | V. A. Smirnov, Renormalization and Asymptotic Expansions, Vol. 14 of Progress in Physics (Birkhäuser, Basel, 1991). · Zbl 0744.46072 |
| [8] | Sokal, A. D., The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, Surv. Comb., 327, 173-226 (2005) · Zbl 1110.05020 |
| [9] | Biggs, N., Algebraic Graph Theory (1993), Cambridge: Cambridge Univ. Press, Cambridge · Zbl 0797.05032 |
| [10] | D. J. A. Welsh, Complexity: Knots, Colourings and Counting, Vol. 186 of London Mathematical Society Lecture Note Series (Cambridge Univ. Press, Cambridge, 1993). · Zbl 0799.68008 |
| [11] | Ireland, K.; Rosen, M., A Classical Introduction to Modern Number Theory (1991), Berlin: Springer, Berlin · Zbl 0712.11001 |
| [12] | M. Aigner, Combinatorial Theory, Vol. 234 of Grundlehren der Mathematischen Wissenschaften (Springer, Berlin, 1979). · Zbl 0415.05001 |
| [13] | B. Bychkov, A. Kazakov, and D. Talalaev, ‘‘Functional relations on anisotropic Potts models: From Biggs formula to the tetrahedron equation,’’ SIGMA 17, 035 (2021). · Zbl 1465.82002 |
| [14] | N. Biggs, Interaction Models, Vol. 30 of London Mathematical Society Lecture Note Series (Cambridge Univ. Press, Cambridge, 1977). · Zbl 0375.05039 |
| [15] | Lerner, E. Yu., Feynman integrals of p-adic argument in the momentum space. II. Explicit expressions, Theor. Math. Phys., 104, 1061-1077 (1995) · Zbl 0923.46075 · doi:10.1007/BF02068739 |
| [16] | Huh, J.; Katz, E., Log-concavity of characteristic polynomials and the Bergman fan of matroids, Math. Ann., 354, 1103-1116 (2012) · Zbl 1258.05021 · doi:10.1007/s00208-011-0777-6 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
