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

Authors

  • Ramón Flores Departamento de Geometría y Topología, Facultad de Matemáticas, Universidad de Sevilla, c/~Tarfia s/n, 41013 Sevilla, Spain https://orcid.org/0000-0002-4315-9957
  • Manuel Cárdenas Departamento de Geometría y Topología, Facultad de Matemáticas, Universidad de Sevilla, c/~Tarfia s/n, 41013 Sevilla, Spain
  • Antonio Quintero Departamento de Geometría y Topología, Facultad de Matemáticas, Universidad de Sevilla, c/~Tarfia s/n, 41013 Sevilla, Spain
  • Maria Trinidad Villar-Liñán Departamento de Geometría y Topología, Facultad de Matemáticas, Universidad de Sevilla, c/~Tarfia s/n, 41013 Sevilla, Spain

DOI:

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

Abstract

In this paper, Lusternik-Schinrelmann category and geometric category of finite spaces are considered. We define new numerical invariants of these spaces derived from the geometric category and present an algorithmic approach for its effective computation. The analysis is undertaken by combining homotopic features of the spaces, algorithms and tools from the theory of graphs and hypergraphs. We also provide a number of examples.

Downloads

Download data is not yet available.

References

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  MR  Zbl

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

J. A. Barmak, Algebraic topology of finite topological spaces and applications, Lecture Notes in Math. 2032, Springer, Heidelberg, 2011.  DOI  MR  Zbl

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 programming (Geneva, 2000), Lecture Notes in Comput. Sci. 1853, Springer, Berlin, 2000, pp. 588–599.  DOI  MR  Zbl

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, 2011.  DOI  MR  Zbl

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, RI, 2003.  DOI  MR  Zbl

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

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

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

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

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

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

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.  MR  Zbl

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

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, in 2016 35th Chinese Control Conference (CCC), Chengdu, China, 2016, pp. 2772–2777.  DOI

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.  DOI  MR  Zbl

Downloads

Published

2025-05-21

Issue

Vol. 68 No. 1 (2025)

Section

Article

License

Copyright (c) 2025 Ramón Flores, Manuel Cárdenas, Antonio Quintero, Maria Trinidad Villar-Liñán

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.