A Hopf algebra for counting cycles. (English) Zbl 1383.05173
Summary: Cycles, also known as self-avoiding polygons, elementary circuits or simple cycles, are closed walks which are not allowed to visit any vertex more than once. We present an exact formula for enumerating such cycles of any length on any directed graph involving a sum over its induced subgraphs. This result stems from a Hopf algebra, which we construct explicitly, and which provides further means of counting cycles. Finally, we obtain a more general theorem asserting that any Lie idempotent can be used to enumerate cycles.
References:
| [1] | Alon, N.; Yuster, R.; Zwick, U., Finding and counting given length cycles, Algorithmica, 17, 209-223 (1997) · Zbl 0865.68093 |
| [2] | Bax, Eric, Inclusion and exclusion algorithm for the Hamiltonian path problem, Inform. Process. Lett., 47, 4, 203-207 (1993) · Zbl 0778.68069 |
| [3] | Bax, Eric; Franklin, Joel, A finite-difference sieve to count paths and cycles by length, Inform. Process. Lett., 60, 4, 171-176 (1996) · Zbl 0900.68230 |
| [4] | Björklund, Andreas, Determinant sums for undirected hamiltonicity, SIAM J. Comput., 43, 1, 280-299 (2014) · Zbl 1292.05244 |
| [5] | Cartier, Pierre; Foata, Dominique, (Problèmes Combinatoires de Commutation et Réarrangements. Problèmes Combinatoires de Commutation et Réarrangements, Lecture Notes in Mathematics, vol. 85 (1969)) · Zbl 0186.30101 |
| [6] | Cash, Gordon G., The number of n-cycles in a graph, Appl. Math. Comput., 184, 2, 1080-1083 (2007) · Zbl 1115.05043 |
| [7] | Choffrut, Christian; Goldwurm, Massimiliano, Determinants and Mobius functions in trace monoids, Discrete Math., 194, 1, 239-247 (1999) · Zbl 0929.20043 |
| [8] | Diekert, Volker, Transitive orientations, möbius functions, and complete semi-thue systems for free partially commutative monoids, (Automata, Languages and Programming (1988), Springer), 176-187 · Zbl 0986.68513 |
| [9] | Diekert, Volker, Combinatorics on Traces, Vol. 454 (1990), Springer Science & Business Media · Zbl 0717.68002 |
| [10] | Duminil-Copin, Hugo; Smirnov, Stanislav, The connective constant of the honeycomb lattice equals \(\sqrt{2 + \sqrt{2}} \), Ann. of Math., 175, 1653-1665 (2012) · Zbl 1253.82012 |
| [11] | Espinasse, Thibault; Rochet, Paul, Relations between connected and self-avoiding hikes in labelled complete digraphs, Graphs Combin., 1-21 (2016) · Zbl 1349.05152 |
| [12] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001 |
| [13] | Pierre-Louis Giscard, Nils Kriege, Richard C. Wilson, A general purpose algorithm for counting simple cycles and simple paths of any length, 2016. arXiv preprint arXiv:1612.05531; Pierre-Louis Giscard, Nils Kriege, Richard C. Wilson, A general purpose algorithm for counting simple cycles and simple paths of any length, 2016. arXiv preprint arXiv:1612.05531 · Zbl 1423.05171 |
| [14] | Giscard, Pierre-Louis; Rochet, Paul, Algebraic combinatorics on trace monoids: extending number theory to walks on graphs, SIAM J. Discrete Math., 31, 2, 1428-1453 (2017) · Zbl 1366.05049 |
| [15] | Darij Grinberg, Victor Reiner, Hopf Algebras in Combinatorics, 2014. arXiv:1409.8356v4; Darij Grinberg, Victor Reiner, Hopf Algebras in Combinatorics, 2014. arXiv:1409.8356v4 |
| [16] | Johnson, D. B., Finding all the elementary circuits of a directed graph, SIAM J. Comput., 4, 1, 77-84 (1975) · Zbl 0275.05112 |
| [17] | Karp, Richard M., Dynamic programming meets the principle of inclusion and exclusion, Oper. Res. Lett., 1, 2, 49-51 (1982) · Zbl 0486.90083 |
| [18] | Khomenko, N. P.; Golovko, L. D., Identifying certain types of parts of a graph and computing their number, Ukr. Matematicheskii Zh., 24, 385-396 (1972) · Zbl 0238.05113 |
| [19] | Madras, Neal; Slade, Gordon, (The Self-Avoiding Walk. The Self-Avoiding Walk, Modern Birkhäuser Classics (2013), Birkhäuser) · Zbl 1254.01051 |
| [20] | Menous, Frederic; Patras, Frédéric, Logarithmic derivatives and generalized dynkin operators, J. Algebraic Combin., 38, 4, 901-913 (2013) · Zbl 1364.17004 |
| [21] | Merris, Russell, Single-hook characters and Hamiltonian circuits, Linear Multilinear Algebra, 14, 21-35 (1983) · Zbl 0526.20008 |
| [22] | Merris, Russell, Immanantal invariants of graphs, Linear Algebra Appl., 401, 67-75 (2005) · Zbl 1062.05093 |
| [23] | Milnor, John W.; Moore, John C., On the structure of Hopf algebras, Ann. of Math., 81, 211-264 (1965) · Zbl 0163.28202 |
| [24] | Montgomery, Susan, (Hopf Algebras and Their Actions on Rings. Hopf Algebras and Their Actions on Rings, CBMS Regional Conference Series in Mathematics, vol. 82 (1993), Published for the Conference Board of the Mathematical Sciences by the American Mathematical Society) · Zbl 0793.16029 |
| [25] | Patras, Frédéric; Reutenauer, Christophe, Higher Lie idempotents, J. Algebra, 222, 51-64 (1999) · Zbl 0956.16017 |
| [26] | Patras, Frédéric; Reutenauer, Christophe, On Dynkin and Klyachko idempotents in graded bialgebras, Adv. Math., 28, 560-579 (2002) · Zbl 1024.16021 |
| [27] | Rota, Gian-Carlo, On the foundations of combinatorial theory, (Classic Papers in Combinatorics (1987), Springer), 332-360 |
| [28] | Schmitt, William R., Antipodes and incidence coalgebras, J. Combin. Theory Ser. A, 46, 264-290 (1987) · Zbl 0699.05003 |
| [29] | Schmitt, William R., Hopf algebras and identities in free partially commutative monoids, Theoret. Comput. Sci., 73, 335-340 (1990) · Zbl 0694.68056 |
| [30] | Schmitt, William R., Incidence hopf algebras, J. Pure Appl. Algebra, 96, 299-330 (1994) · Zbl 0808.05101 |
| [31] | Schott, René.; Stacey Staples, G., Complexity of counting cycles using zeons, Comput. Math. Appl., 62, 4, 1828-1837 (2011) · Zbl 1231.05250 |
| [32] | Schramm, Oded; Lawler, Gregory; Werner, Wendelin, Fractal geometry and applications: a jubilee of Benoît Mandelbrot, Proc. Sympos. Pure Math., 72, 339-364 (2004) · Zbl 1069.60089 |
| [33] | Jean-Yves Thibon, Lie Idempotents in Descent Algebras. Online resource www.igm.univ-mlv.fr/ jyt/TALKS/lieids.ps; Jean-Yves Thibon, Lie Idempotents in Descent Algebras. Online resource www.igm.univ-mlv.fr/ jyt/TALKS/lieids.ps |
| [34] | Waldenfels, Wilhelm von, Zur charakterisierung Liescher elemente in freien algebren, Arch. Math, 17, 44-48 (1966) · Zbl 0141.02706 |
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.
