Zeon and idem-Clifford formulations of hypergraph problems. (English) Zbl 1503.05088
Summary: Zeon algebras have proven to be useful for enumerating structures in graphs, such as paths, trails, cycles, matchings, cliques, and independent sets. In contrast to an ordinary graph, in which each edge connects exactly two vertices, an edge (or, “hyperedge”) can join any number of vertices in a hypergraph. Hypergraphs have been used for problems in biology, chemistry, image processing, wireless networks, and more. In the current work, zeon (“nil-Clifford”) and “idem-Clifford” graph-theoretic methods are generalized to hypergraphs. In particular, zeon and idem-Clifford methods are used to enumerate paths, trails, independent sets, cliques, and matchings in hypergraphs. An approach for finding minimum hypergraph transversals is developed, and zeon formulations of some open hypergraph problems are presented.
MSC:
| 05C65 | Hypergraphs |
| 05C30 | Enumeration in graph theory |
| 05E16 | Combinatorial aspects of groups and algebras |
| 81R05 | Finite-dimensional groups and algebras motivated by physics and their representations |
| 15A66 | Clifford algebras, spinors |
References:
| [1] | Bretto, A., Introduction to hypergraph theory and its use in engineering and image processing, Adv. Imaging Electron Phys., 131, 1-64 (2004) · doi:10.1016/S1076-5670(04)31001-3 |
| [2] | Bruhn, H.; Schaudt, O., The journey of the union-closed sets conjecture, Graphs Combin., 31, 2043-2074 (2015) · Zbl 1327.05249 · doi:10.1007/s00373-014-1515-0 |
| [3] | Cutler, J.; Radcliffe, AJ, Hypergraph independent sets, Combin. Probab. Comput., 22, 9-20 (2013) · Zbl 1257.05104 · doi:10.1017/S0963548312000454 |
| [4] | Davis, A.; Staples, GS, Zeon and idem-Clifford formulations of Boolean satisfiability, Adv. Appl. Clifford Algebras, 29, 60 (2019) · Zbl 1456.68123 · doi:10.1007/s00006-019-0978-8 |
| [5] | Ducournau, A.; Bretto, A., Random walks in directed hypergraphs and applications to semi-supervised image segmentation, Comput. Vis. Image Underst., 120, 91-102 (2014) · doi:10.1016/j.cviu.2013.10.012 |
| [6] | Eiter, T.; Gottlob, G.; Flesca, S.; Greco, S.; Ianni, G.; Leone, N., Hypergraph transversal computation and related problems in logic and AI, Logics in Artificial Intelligence. JELIA 2002. Lecture Notes in Computer Science (2002), Berlin: Springer, Berlin · Zbl 1013.68143 · doi:10.1007/3-540-45757-7_53 |
| [7] | Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput., 24, 1278-1304 (1995) · Zbl 0842.05070 · doi:10.1137/S0097539793250299 |
| [8] | Fang, Q.; Sang, J.; Xu, C.; Rui, Y., Topic-sensitive influencer mining in interest-based social media networks via hypergraph learning, IEEE Trans. Multimed., 16, 796-812 (2014) · doi:10.1109/TMM.2014.2298216 |
| [9] | Feng, Y.; You, H.; Zhang, Z.; Ji, R.; Gao, Y., Hypergraph neural networks, Proc. AAAI Conf. Artif. Intell., 33, 3558-3565 (2019) · doi:10.1609/aaai.v33i01.33013558 |
| [10] | Frankl’s union-closed sets conjecture | Open Problem Garden. http://www.openproblemgarden.org/op/frankls_union_closed_sets_conjecture. Accessed 04-06-2021 |
| [11] | Halldorsonn, MM; Losievskaja, E., Independent sets in bounded-degree hypergraphs, Discrete Appl. Math., 157, 1773-1786 (2009) · Zbl 1173.05035 · doi:10.1016/j.dam.2008.11.013 |
| [12] | Han, Z.; Song, L.; Zhang, H.; Zhang, Y., Hypergraph Theory in Wireless Communication Networks (2018), Berlin: Springer, Berlin · Zbl 1421.90001 |
| [13] | Henderson, J.R.: Permutation Decompositions of \((0,1)\)-matrices and decomposition transversals, Thesis, Caltech (1971). https://thesis.library.caltech.edu/5726/1/Hendersonjr1971.pdf. Accessed 04-06-2021 |
| [14] | Hu, T., Xiong, H., Zhou, W., Sung, S.Y., Luo, H.: Hypergraph partitioning for document clustering: a unified clique perspective. In: SIGIR ’08: Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 871-872 (2008). doi:10.1145/1390334.1390548 |
| [15] | Hwang, T., Tian, Z., Kuangy, R., Kocher, J.: Learning on weighted hypergraphs to integrate protein interactions and gene expressions for cancer outcome prediction. In: 2008 Eighth IEEE International Conference on Data Mining, 2008, pp. 293-302 (2008). doi:10.1109/ICDM.2008.37 |
| [16] | Klamt, S., Haus, U.-U., Theis, F.: Hypergraphs and cellular networks. PLoS Comput. Biol. 5, e1000385 (2009). doi:10.1371/journal.pcbi.1000385 |
| [17] | Konstantinova, E., Application of hypergraph theory in chemistry, Discrete Math., 235, 365-383 (2001) · Zbl 0977.05133 · doi:10.1016/S0012-365X(00)00290-9 |
| [18] | Open Problem Garden, a collection of unsolved problems in mathematics. http://www.openproblemgarden.org. Accessed 4 June 2021 |
| [19] | Ouvard, X.; Le Goff, JM; Marchand-Maillet, S., On adjacency and e-adjacency in general hypergraphs: towards a new e-adjacency tensor, Electron. Notes Discrete Math., 70, 71-76 (2018) · Zbl 1460.05136 · doi:10.1016/j.endm.2018.11.012 |
| [20] | “Ryser’s conjecture | Open Problem Garden”. http://www.openproblemgarden.org/op/rysers_conjecture. Accessed 04 June 2021 |
| [21] | Schott, R.; Staples, GS, Complexity of counting cycles using zeons, Comput. Math. Appl., 62, 1828-1837 (2011) · Zbl 1231.05250 · doi:10.1016/j.camwa.2011.06.026 |
| [22] | Schott, R.; Staples, GS, Generalized zeon algebras: theory and application to multi-constrained path problems, Adv. Appl. Clifford Algebras, 27, 45-57 (2017) · Zbl 1369.05056 · doi:10.1007/s00006-015-0595-0 |
| [23] | Staples, GS, A new adjacency matrix for finite graphs, Adv. Appl. Clifford Algebras, 18, 979-991 (2008) · Zbl 1194.05099 · doi:10.1007/s00006-008-0116-5 |
| [24] | Staples, GS, Clifford Algebras and Zeons: Geometry to Combinatorics and Beyond (2019), Singapore: World Scientific Publishing, Singapore · Zbl 1431.15001 · doi:10.1142/11340 |
| [25] | Staples, GS, Zeon matrix inverses and the zeon combinatorial Laplacian, Adv. Appl. Clifford Algebras, 31, 40 (2021) · Zbl 1471.15002 · doi:10.1007/s00006-021-01152-5 |
| [26] | Staples, GS; Stellhorn, T., Zeons, orthozeons, and graph colorings, Adv. Appl. Clifford Algebras, 27, 1825-1845 (2017) · Zbl 1365.05103 · doi:10.1007/s00006-016-0742-2 |
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.
