Covering-based numbers related to the LS-category of finite spaces

• Manuel Cárdenas ^[1] ; Ramón Flores ^[1] ; Antonio Quintero ^[1] ; María Trinidad Villar-Liñán ^[1]
  1. [1] Universidad de Sevilla

     Universidad de Sevilla

     Sevilla, España

     
• Localización: Revista de la Unión Matemática Argentina, ISSN 0041-6932, ISSN-e 1669-9637, Vol. 68, Nº. 1, 2025, págs. 205-229
• Idioma: inglés
• DOI: 10.33044/revuma.3601
• Enlaces
  • Texto completo
• Resumen

  • 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.

• Referencias bibliográficas
  • 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
  • S. Aaronson and N. A. Scoville, Lusternik–Schnirelmann category for simplicial complexes, Illinois J. Math. 57 no. 3 (2013), 743–753. DOI...
  • 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....
  • J. A. Barmak, Algebraic topology of finite topological spaces and applications, Lecture Notes in Math. 2032, Springer, Heidelberg, 2011. DOI...
  • C. Berge, Hypergraphs, North-Holland Mathematical Library 45, North-Holland, Amsterdam, 1989. MR Zbl
  • E. Boros, V. Gurvich, L. Khachiyan, and K. Makino, Generating partial and multiple transversals of a hypergraph, in Automata, languages and...
  • A. Bretto, Hypergraph theory, Mathematical Engineering, Springer, Cham, 2013. DOI MR Zbl
  • D. Cheng and H. Qi, Semi-tensor product of matrices—theory and applications, Science Press, Beijing, 2007.
  • D. Cheng, H. Qi, and Z. Li, Analysis and control of Boolean networks, Communications and Control Engineering Series, Springer London, London,...
  • E. Clader, Inverse limits of finite topological spaces, Homology Homotopy Appl. 11 no. 2 (2009), 223–227. DOI MR Zbl
  • O. Cornea, G. Lupton, J. Oprea, and D. Tanré, Lusternik–Schnirelmann category, Math. Surveys Monogr. 103, American Mathematical Society, Providence,...
  • D. Duffus and I. Rival, Crowns in dismantlable partially ordered sets, in Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976),...
  • T. Eiter and G. Gottlob, Hypergraph transversal computation and related problems in logic and AI, in Logics in artificial intelligence, Lecture...
  • T. Eiter, K. Makino, and G. Gottlob, Computational aspects of monotone dualization: A brief survey, Discrete Appl. Math. 156 no. 11 (2008),...
  • D. Fernandez-Ternero, E. Macías-Virgos, and J. A. Vilches, Lusternik–Schnirelmann category of simplicial complexes and finite spaces, Topology...
  • W. Fischl, G. Gottlob, and R. Pichler, General and fractional hypertree decompositions: Hard and easy cases, in Proceedings of the 37th ACM...
  • M. L. Fredman and L. Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 no. 3 (1996), 618–628....
  • Z. Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 no. 2 (1988), 115–206. DOI MR Zbl
  • M. R. Garey and D. S. Johnson, Computers and intractability, W. H. Freeman, San Francisco, CA, 1979. MR Zbl
  • 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....
  • 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....
  • M. J. Kukieła, On homotopy types of Alexandroff spaces, Order 27 no. 1 (2010), 9–21. DOI MR Zbl
  • E. L. Lawler, Covering problems: Duality relations and a new method of solution, SIAM J. Appl. Math. 14 (1966), 1115–1132. DOI MR Zbl
  • J. P. May, Finite spaces and larger contexts. Available at https://math.uchicago.edu/%7Emay/FINITE/FINITEBOOK/FINITEBOOKCollatedDraft.pdf.
  • M. C. McCord, Singular homology groups and homotopy groups of finite topological spaces, Duke Math. J. 33 (1966), 465–474. DOI MR Zbl
  • M. Meng, J. Feng, and X. Li, A matrix method to hypergraph transversal and covering problems with application in simplifying Boolean functions,...
  • G. Raptis, Homotopy theory of posets, Homology Homotopy Appl. 12 no. 2 (2010), 211–230. DOI MR Zbl
  • 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
  • R. E. Stong, Finite topological spaces, Trans. Amer. Math. Soc. 123 (1966), 325–340. DOI MR Zbl
  • K. Tanaka, Lusternik–Schnirelmann category for cell complexes and posets, Illinois J. Math. 59 no. 3 (2015), 623–636. DOI MR Zbl
  • K. Tanaka, Lusternik–Schnirelmann category of relation matrices on finite spaces and simplicial complexes, Fund. Math. 249 no. 2 (2020), 149–167....