Equivariant simplicial reconstruction. (English) Zbl 1454.05127
Summary: We introduce and analyze parallelizable algorithms to compress and accurately reconstruct finite simplicial complexes that have nontrivial automorphisms. The compressed data-called a complex of groups-amounts to a functor from (the poset of simplices in) the orbit space to the 2-category of groups, whose higher structure is prescribed by isomorphisms arising from conjugation. Using this functor, we show how to algorithmically recover the original complex up to equivariant simplicial isomorphism. Our algorithms are derived from generalizations (by Bridson-Haefliger, Carbone-Rips, and Corson, among others) of the classical Bass-Serre theory for reconstructing group actions on trees.
MSC:
| 05E18 | Group actions on combinatorial structures |
| 05E45 | Combinatorial aspects of simplicial complexes |
| 20F65 | Geometric group theory |
| 18N10 | 2-categories, bicategories, double categories |
| 57M07 | Topological methods in group theory |
| 06A07 | Combinatorics of partially ordered sets |
Software:
MagmaReferences:
| [1] | E. Babson and D. N. Kozlov, Group actions on posets, J. Algebra, 285 (2005), pp. 439-450. · Zbl 1084.18004 |
| [2] | H. Bass, Covering theory for graphs of groups, J. Pure Appl. Algebra, 89 (1993), pp. 3-47. · Zbl 0805.57001 |
| [3] | M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15 (2003), pp. 1373-1396. · Zbl 1085.68119 |
| [4] | W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system. \textupI. The user language, J. Symbolic Comput., 24 (1997), pp. 235-265, https://doi.org/10.1006/jsco.1996.0125. · Zbl 0898.68039 |
| [5] | G. E. Bredon, Introduction to Compact Transformation Groups, Pure Appl. Math. 46, Academic Press, New York, London, 1972. · Zbl 0246.57017 |
| [6] | M. R. Bridson and A. Haefliger, Metric Spaces of Non-positive Curvature, Grundlehren Math. Wiss. 319, Springer-Verlag, Berlin, 1999. · Zbl 0988.53001 |
| [7] | L. Carbone and E. Rips, Reconstructing group actions, Internat. J. Algebra Comput., 23 (2013), pp. 255-323. · Zbl 1266.22022 |
| [8] | A. M. Cegarra, Homotopy fiber sequences induced by 2-functors, J. Pure Appl. Algebra, 215 (2011), pp. 310-334. · Zbl 1213.18004 |
| [9] | I. Chevyrev and A. Kormilitzin, A Primer on the Signature Method in Machine Learning, preprint, https://arxiv.org/abs/1603.03788, 2016. |
| [10] | J. M. Corson, Complexes of groups, Proc. London Math. Soc. (3), 65 (1992), pp. 199-224. · Zbl 0792.57004 |
| [11] | J. Curry, Sheaves, Cosheaves and Applications, preprint, https://arxiv.org/abs/1303.3255, 2013. |
| [12] | M. W. Davis, The Geometry and Topology of Coxeter Groups, Princeton University Press, Princeton, NJ, 2008. · Zbl 1142.20020 |
| [13] | O. Delgado-Friedrichs, V. Robins, and A. Sheppard, Skeletonization and partitioning of digital images using discrete Morse theory, IEEE Trans. Pattern Anal. Mach. Intell., 37 (2014), pp. 654-666. |
| [14] | W. Dicks and M. J. Dunwoody, Groups Acting on Graphs, Cambridge Stud. Adv. Math. 17, Cambridge University Press, Cambridge, 1989. · Zbl 0665.20001 |
| [15] | T. Fiore, W. Lück, and R. Sauer, Euler characteristics of categories and homotopy colimits, Doc. Math., 16 (2011), pp. 301-354. · Zbl 1267.18011 |
| [16] | T. Gao, J. Brodzki, and S. Mukherjee, The Geometry of Synchronization Problems and Learning Group Actions, preprint, https://arxiv.org/abs/1610.09051, 2016. |
| [17] | R. Ghrist, Barcodes: The persistent topology of data, Bull. Amer. Math. Soc. (N.S.), 45 (2009), pp. 61-75. · Zbl 1391.55005 |
| [18] | K. Grove and W. Ziller, Polar manifolds and actions, J. Fixed Point Theory Appl., 11 (2012), pp. 279-313. · Zbl 1266.53039 |
| [19] | A. Haefliger, Extensions of complexes of groups, Ann. Inst. Fourier (Grenoble), 42 (1992), pp. 275-311. · Zbl 0762.20018 |
| [20] | A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002. · Zbl 1044.55001 |
| [21] | D. F. Holt, B. Eick, and E. A. O’Brien, Handbook of Computational Group Theory, Chapman and Hall/CRC, Boca Raton, FL, 2005. · Zbl 1091.20001 |
| [22] | T. W. Hungerford, Algebra, Grad. Texts in Math. 73, Springer-Verlag, New York, Berlin, 1980. · Zbl 0442.00002 |
| [23] | S. Krishnan, Flow-Cut Dualities for Sheaves on Graphs, preprint, https://arxiv.org/abs/1409.6712, 2014. |
| [24] | S. Lack, A 2-categories companion, in Towards Higher Categories, J. C. Baez and J. P. May, eds., Springer, New York, 2010, pp. 105-191, https://doi.org/10.1007/978-1-4419-1524-5_4. · Zbl 1223.18003 |
| [25] | T. Leinster, Basic Bicategories, preprint, https://arxiv.org/abs/math/9810017, 1998. |
| [26] | S. Lim and A. Thomas, Covering theory for complexes of groups, J. Pure Appl. Algebra, 212 (2008), pp. 1632-1663, https://doi.org/10.1016/j.jpaa.2007.10.012. · Zbl 1182.57003 |
| [27] | S. Mac Lane, Categories for the Working Mathematician, Grad. Texts in Math. 5, Springer-Verlag, New York, Berlin, 1971. · Zbl 0232.18001 |
| [28] | N. Martins-Ferreira, Pseudo-categories, J. Homotopy Relat. Struct., 1 (2006), pp. 47-78. · Zbl 1125.18005 |
| [29] | N. J. Mitra, L. Guibas, and M. Pauly, Partial and approximate symmetry detection for 3D geometry, in ACM SIGGRAPH 2006 Papers, Association for Computing Machinery, New York, 2006, pp. 560-568. |
| [30] | I. Moerdijk and D. A. Pronk, Orbifolds, sheaves and groupoids, K-Theory, 12 (1997), pp. 3-21. · Zbl 0883.22005 |
| [31] | I. Moerdijk and D. A. Pronk, Simplicial cohomology of orbifolds, Indag. Math. (N.S.), 10 (1999), pp. 269-293. · Zbl 1026.55007 |
| [32] | B. Noohi, Foundations of Topological Stacks I, preprint, https://arxiv.org/abs/math/0503247, 2005. |
| [33] | J.-P. Serre, Trees, translated from the French by John Stillwell, Springer-Verlag, Berlin, 1980. · Zbl 0548.20018 |
| [34] | E. H. Spanier, Algebraic Topology, McGraw-Hill, New York, Toronto, London 1966. · Zbl 0145.43303 |
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.
