Revista de la
Unión Matemática Argentina
Covering-based numbers related to the LS-category of finite spaces
Manuel Cárdenas, Ramón Flores, Antonio Quintero, and María Trinidad Villar-Liñán

Volume 68, no. 1 (2025), pp. 205–229    

Published online (final version): May 21, 2025

https://doi.org/10.33044/revuma.3601

Download PDF

Abstract

In this paper, we consider the Lusternik–Schnirelmann and geometric categories of finite spaces. We define new numerical invariants for these spaces derived from the geometric category and present an algorithmic approach for their effective computation. Our analysis combines homotopy-theoretic properties of these spaces with algorithms and tools from graph and hypergraph theory. We also provide several examples to illustrate our results.

References

  1. C. G. T. de A. Moreira and Y. Kohayakawa, Bounds for optimal coverings, Discrete Appl. Math. 141 no. 1-3 (2004), 263–276.  DOI  MR  Zbl
  2. S. Aaronson and N. A. Scoville, Lusternik–Schnirelmann category for simplicial complexes, Illinois J. Math. 57 no. 3 (2013), 743–753.  DOI  MR  Zbl
  3. P. Alexandroff, Diskrete Räume, Rec. Math. Moscou, n. Ser. 2(44) no. 3 (1937), 501–519. Available at https://mathnet.ru/eng/msb/v44/i3/p501.  Zbl
  4. J. A. Barmak, Algebraic topology of finite topological spaces and applications, Lecture Notes in Math. 2032, Springer, Heidelberg, 2011.  DOI  MR  Zbl
  5. C. Berge, Hypergraphs, North-Holland Mathematical Library 45, North-Holland, Amsterdam, 1989.  MR  Zbl
  6. E. Boros, V. Gurvich, L. Khachiyan, and K. Makino, Generating partial and multiple transversals of a hypergraph, in Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci. 1853, Springer, Berlin, 2000, pp. 588–599.  DOI  MR  Zbl
  7. A. Bretto, Hypergraph theory, Mathematical Engineering, Springer, Cham, 2013.  DOI  MR  Zbl
  8. D. Cheng and H. Qi, Semi-tensor product of matrices—theory and applications, Science Press, Beijing, 2007.
  9. D. Cheng, H. Qi, and Z. Li, Analysis and control of Boolean networks, Communications and Control Engineering Series, Springer London, London, 2011.  DOI  MR  Zbl
  10. E. Clader, Inverse limits of finite topological spaces, Homology Homotopy Appl. 11 no. 2 (2009), 223–227.  DOI  MR  Zbl
  11. O. Cornea, G. Lupton, J. Oprea, and D. Tanré, Lusternik–Schnirelmann category, Math. Surveys Monogr. 103, American Mathematical Society, Providence, RI, 2003.  DOI  MR  Zbl
  12. D. Duffus and I. Rival, Crowns in dismantlable partially ordered sets, in Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai 18, North-Holland, Amsterdam-New York, 1978, pp. 271–292.  MR  Zbl
  13. T. Eiter and G. Gottlob, Hypergraph transversal computation and related problems in logic and AI, in Logics in artificial intelligence, Lecture Notes in Comput. Sci. 2424, Springer, Berlin, 2002, pp. 549–564.  DOI  MR  Zbl
  14. T. Eiter, K. Makino, and G. Gottlob, Computational aspects of monotone dualization: A brief survey, Discrete Appl. Math. 156 no. 11 (2008), 2035–2049.  DOI  MR  Zbl
  15. D. Fernández-Ternero, E. Macías-Virgós, and J. A. Vilches, Lusternik–Schnirelmann category of simplicial complexes and finite spaces, Topology Appl. 194 (2015), 37–50.  DOI  MR  Zbl
  16. W. Fischl, G. Gottlob, and R. Pichler, General and fractional hypertree decompositions: Hard and easy cases, in Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018, pp. 17–32.  DOI
  17. M. L. Fredman and L. Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 no. 3 (1996), 618–628.  DOI  MR  Zbl
  18. Z. Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 no. 2 (1988), 115–206.  DOI  MR  Zbl
  19. M. R. Garey and D. S. Johnson, Computers and intractability, W. H. Freeman, San Francisco, CA, 1979.  MR  Zbl
  20. J. González, Simplicial complexity: Piecewise linear motion planning in robotics, New York J. Math. 24 (2018), 279–292. Available at https://nyjm.albany.edu/j/2018/24-16.html.  MR  Zbl
  21. D. Gries, A. J. Martin, J. L. A. van de Snepscheut, and J. T. Udding, An algorithm for transitive reduction of an acyclic graph, Sci. Comput. Programming 12 no. 2 (1989), 151–155.  DOI  MR  Zbl
  22. M. J. Kukieła, On homotopy types of Alexandroff spaces, Order 27 no. 1 (2010), 9–21.  DOI  MR  Zbl
  23. E. L. Lawler, Covering problems: Duality relations and a new method of solution, SIAM J. Appl. Math. 14 (1966), 1115–1132.  DOI  MR  Zbl
  24. J. P. May, Finite spaces and larger contexts. Available at https://math.uchicago.edu/%7Emay/FINITE/FINITEBOOK/FINITEBOOKCollatedDraft.pdf.
  25. M. C. McCord, Singular homology groups and homotopy groups of finite topological spaces, Duke Math. J. 33 (1966), 465–474.  DOI  MR  Zbl
  26. M. Meng, J. Feng, and X. Li, A matrix method to hypergraph transversal and covering problems with application in simplifying Boolean functions, in 2016 35th Chinese Control Conference (CCC), Chengdu, China, 2016, pp. 2772–2777.  DOI
  27. G. Raptis, Homotopy theory of posets, Homology Homotopy Appl. 12 no. 2 (2010), 211–230.  DOI  MR  Zbl
  28. I. Rival, A fixed point theorem for finite partially ordered sets, J. Combinatorial Theory Ser. A 21 no. 3 (1976), 309–318.  DOI  MR  Zbl
  29. R. E. Stong, Finite topological spaces, Trans. Amer. Math. Soc. 123 (1966), 325–340.  DOI  MR  Zbl
  30. K. Tanaka, Lusternik–Schnirelmann category for cell complexes and posets, Illinois J. Math. 59 no. 3 (2015), 623–636.  DOI  MR  Zbl
  31. K. Tanaka, Lusternik–Schnirelmann category of relation matrices on finite spaces and simplicial complexes, Fund. Math. 249 no. 2 (2020), 149–167.  DOI  MR  Zbl