Convex geometries yielded by transit functions

• Autorzy: Changat Manoj , Sheela Lekshmi Kamal K. , Peterin Iztok , Shanavas Ameera Vaheeda

Identyfikatory

DOI

10.7494/OpMath.2025.45.4.423

• Języki publikacji: EN

Abstrakty

EN

Let V be a finite nonempty set. A transit function is a map R : V x V → 2V such that R(u, u) = {u}, R(u, v) = R(v, u) and u ∈ R(u, v) holds for every u, v ∈ V . A set K ⊆ V is R-convex if R(u, v) ⊂ K for every u, v ∈ K and all R-convex subsets of V form a convexity CR. We consider the Minkowski–Krein–Milman property that every R-convex set K in a convexity CR is the convex hull of the set of extreme points of K from axiomatic point of view and present a characterization of it. Later we consider several well-known transit functions on graphs and present the use of the mentioned characterizations on them.

Słowa kluczowe

EN

Minkowski–Krein–Milman property; convexity; convex geometry; transit function

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 4
• Strony: 423--450
• Opis fizyczny: Bibliogr. 43 poz., rys., wykr.

Twórcy

autor

Changat Manoj

• University of Kerala, Department of Futures Studies, Thiruvananthapuram – 695581, India

• https://orcid.org/0000-0001-7257-6031

autor

Sheela Lekshmi Kamal K.

• University of Kerala, Department of Futures Studies, Thiruvananthapuram – 695581, India

• https://orcid.org/0000-0002-8527-3280

autor

Peterin Iztok

• Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška 46, 2000 Maribor, Slovenia
• Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia

• https://orcid.org/0000-0002-1990-6967

autor

Shanavas Ameera Vaheeda

• University of Kerala, Department of Futures Studies, Thiruvananthapuram – 695581, India

Bibliografia

• [1] K. Adaricheva, J.B. Nation, Classes of Semidistributive Lattices, [in:] G. Grätzer, F. Wehrung (eds), Lattice Theory: Special Topics and Applications, Birkäuser, Cham, 2015, 59–101.
• [2] K. Adaricheva, G. Czédli, Note on the description of join-distributive lattices by permutations, Algebra Universalis 72 (2014), 155–162.
• [3] L. Alcon, A note on path domination, Discuss. Math. Graph Theory 36 (2016), 1021–1034.
• [4] L. Alcon, B. Brešar, T. Gologranc, M. Gutierrez, T. Kraner Šumenjak, I. Peterin, A. Tepeh, Toll convexity, European J. Combin. 46 (2015), 161–175.
• [5] J.P. Barthélemy, F. Brucker, Binary clustering, Discr. Appl. Math. 156 (2008), 1237–1250.
• [6] J.R. Calder, Some elementary properties of interval convexities, J. Lond. Math. Soc. (2) 3 (1971), 422–428.
• [7] M. Changat, S. Klavžar, H.M. Mulder, The all-paths transit function of a graph, Czech. Math. J. 51 (2001), 439–448.
• [8] M. Changat, A.K. Lakshmikuttyamma, J. Mathews, I. Peterin, P.G. Narasimha-Shenoi, G. Seethakuttyamma, S. Špacapan, A forbidden subgraph characterization of some graph classes using betweenness axioms, Discrete Math. 313 (2013), 951–958.
• [9] M. Changat, J. Mathew, Induced path transit function, monotone and Peano axioms, Discrete Math. 286 (2004), 185–194.
• [10] M. Changat, J. Mathews, H.M. Mulder, The induced path function, monotonicity and betweenness, Discrete Appl. Math. 158 (2010), 426–433.
• [11] M. Changat, J. Mathews, I. Peterin, P.G. Narasimha-Shenoi, n-ary transit functions in graphs, Discuss. Math. Graph Theory 30 (2010), 671–685.
• [12] M. Changat, P.G. Narasimha-Shenoi, P.F. Stadler, Axiomatic characterization of transit functions of weak hierarchies, Art Discr. Appl. Math. 2 (2019), #P1.01.
• [13] M. Changat, F.H. Nezhad, P.F. Stadler, Axiomatic characterization of transit functions of hierarchies, Ars Math. Contemp. 14 (2018), 117–128.
• [14] M. Changat, F.H. Nezhad, P.F. Stadler, Cut-vertex transit functions of hypergraphs, [in:] A. Mudgal, C.R. Subramanian (eds), Algorithms and Discrete Applied Mathematics, CALDAM 2021, volume 12601 of Lecture Notes Comp. Sci., Springer, Cham, 2021, 222–233.
• [15] V. Chvatal, D. Rautenbach, P.M. Schafer, Finite Sholander trees, trees, and their betweenness, Discrete Math. 311 (2011), 2143–2147.
• [16] V. Chvátal, Antimatroids, Betweenness, Convexity, [in:] W. Cook, L. Lovász, J. Vygen (eds), Research Trends in Combinatorial Optimization, Springer, Berlin, Heidelberg, 2009, 57–64.
• [17] G. Cźedli, Coordinatization of finite join-distributive lattices, Algebra Universalis 71 (2014), 385–404.
• [18] M. Dewar, D. Pike, J. Proos, Connectivity in hypergraphs, Canad. Math. Bull. 61 (2018), 252–271.
• [19] J.P. Doignon, J.C. Falmagne, Knowledge Spaces, Springer-Verlag, Berlin, 1999.
• [20] M.C. Dourado, M. Gutierrez, F. Protti, S. Tondato, Weakly toll convexity and proper interval graphs, arXiv:2203.17056.
• [21] M.C. Dourado, M. Gutierrez, F. Protti, R. Sampaio, S. Tondato, Characterizations of graph classes via convex geometries: A survey, Discrete Appl. Math. 360 (2025), 246–257.
• [22] F. Dragan, F. Nicolai, A. Brandstädt, Convexity and HHD-free graphs, SIAM J. Discrete Math. 12 (1999), 119–135.
• [23] P. Duchet, Classical perfect graphs: An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 12 (1984), 67–96.
• [24] P.H. Edelman, R.E. Jamison, The theory of convex geometries, Geometriae Dedicata 19 (1985), 247–270.
• [25] J.C. Falmagne, J.P. Doignon, Learning Spaces, Springer-Verlag, Berlin, 2011.
• [26] M. Farber, R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods 7 (1986), 433–444.
• [27] O. Goecke, B. Korte, L. Lovász, Examples and algorithmic properties of greedoids, [in:] Combinatorial Optimization (Como, 1986), volume 1403 of Lecture Notes in Mathematics, Springer, Berlin, 1989, 113–161.
• [28] E. Howorka, A characterization of ptolemaic graphs, J. Graph Theory 5 (1981), 323–331.
• [29] D. Kay, G. Chartrand, A characterization of certain ptolemaic graphs, Canad. J. Math. 17 (1965), 342–346.
• [30] B. Korte, L. Lovász, R. Schrader, Transposition Greedoids, [in:] Greedoids, volume 4 of Algorithms and Combinatorics, Springer-Verlag, Berlin, 1991, 141–151.
• [31] C.G. Lekkerkerker, J.C. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962) 45–64.
• [32] B. Monjardet, A use for frequently rediscovering a concept, Order 1 (1985), 415–417.
• [33] B. Monjardet, The consequences of Dilworth’s work on lattices with unique irreducible decompositions, [in:] K.P. Bogart, R. Freese, J.P.S. Kung (eds), The Dilworth Theorems: Selected Theorems of Robert P. Dilworth, Birkhäuser, Boston, 1990, 192–199.
• [34] B. Monjardet, Statement of precedence and a comment on IIA terminology, Games and Economic Behavior 62 (2008), 736–738.
• [35] M.A. Morgana, H.M. Mulder, The induced path convexity, betweenness and svelte graphs, Discrete Math. 254 (2002), 349–370.
• [36] H.M. Mulder, The Interval Function of a Graph, MC Tract 132, Mathematisch Centrum, Amsterdam, 1980.
• [37] H.M. Mulder, Transit functions on graphs (and posets), Proc. Int. Conf. – Convexity in Discrete Structures 5 (2008), 117–130.
• [38] H.M. Mulder, L. Nebeský, Axiomatic characterization of the interval function of a graph, European J. Combin. 30 (2009), 1172–1185.
• [39] S. Olariu, Weak bipolarizable graphs, Discrete Math. 74 (1989), 159–171.
• [40] L.K. Sheela, M. Changat, J. Jacob, The weak-toll function of a graph: axiomatic characterizations and first-order non-definability, [in:] S. Kalyanasundaram, A. Maheshwari (eds), Algorithms and Discrete Applied Mathematics, Lecture Notes in Computer Science, vol. 14508, Springer, Cham, 2024, 286–301.
• [41] L.K. Sheela, M. Changat, I. Peterin, Axiomatic characterization of the toll walk function of some graph classes, Lecture Notes Comput. Sci. 13947 (2023), 427–446.
• [42] M. Stern, Semimodular Lattices: Theory and Applications, Encyclopedia of Mathematics and its Applications, vol. 73, Cambridge University Press, 1999.
• [43] M.L.J. van de Vel, Theory of Convex Structures, Elsevier, North Holland, Amsterdam, 1993.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)