Opuscula Math. 45, no. 4 (2025), 423-450
https://doi.org/10.7494/OpMath.2025.45.4.423

 
Opuscula Mathematica

Convex geometries yielded by transit functions

Manoj Changat
Lekshmi Kamal K. Sheela
Iztok Peterin
Ameera Vaheeda Shanavas

Abstract. Let \(V\) be a finite nonempty set. A transit function is a map \(R:V\times V\rightarrow 2^V\) such that \(R(u,u)=\{u\}\), \(R(u,v)=R(v,u)\) and \(u\in R(u,v)\) holds for every \(u,v\in V\). A set \(K\subseteq V\) is \(R\)-convex if \(R(u,v)\subset K\) for every \(u,v\in K\) and all \(R\)-convex subsets of \(V\) form a convexity \(\mathcal{C}_R\). We consider the Minkowski-Krein-Milman property that every \(R\)-convex set \(K\) in a convexity \(\mathcal{C}_R\) 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.

Keywords: Minkowski-Krein-Milman property, convexity, convex geometry, transit function.

Mathematics Subject Classification: 52A01, 05C38.

Full text (pdf)

  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. https://doi.org/10.1007/978-3-319-44236-5_3
  2. K. Adaricheva, G. Czédli, Note on the description of join-distributive lattices by permutations, Algebra Universalis 72 (2014), 155-162. https://doi.org/10.1007/s00012-014-0295-y
  3. L. Alcon, A note on path domination, Discuss. Math. Graph Theory 36 (2016), 1021-1034. https://doi.org/10.7151/dmgt.1917
  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. https://doi.org/10.1016/j.ejc.2015.01.002
  5. J.P. Barthélemy, F. Brucker, Binary clustering, Discr. Appl. Math. 156 (2008), 1237-1250. https://doi.org/10.1016/j.dam.2007.05.024
  6. J.R. Calder, Some elementary properties of interval convexities, J. Lond. Math. Soc. (2) 3 (1971), 422-428. https://doi.org/10.1112/jlms/s2-3.3.422
  7. M. Changat, S. Klavžar, H.M. Mulder, The all-paths transit function of a graph, Czech. Math. J. 51 (2001), 439-448. https://doi.org/10.1023/a:1013715518448
  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. https://doi.org/10.1016/j.disc.2013.01.013
  9. M. Changat, J. Mathew, Induced path transit function, monotone and Peano axioms, Discrete Math. 286 (2004), 185-194. https://doi.org/10.1016/j.disc.2004.02.017
  10. M. Changat, J. Mathews, H.M. Mulder, The induced path function, monotonicity and betweenness, Discrete Appl. Math. 158 (2010), 426-433. https://doi.org/10.1016/j.dam.2009.10.004
  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. https://doi.org/10.7151/dmgt.1522
  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. https://doi.org/10.26493/2590-9770.1260.989
  13. M. Changat, F.H. Nezhad, P.F. Stadler, Axiomatic characterization of transit functions of hierarchies, Ars Math. Contemp. 14 (2018), 117-128. https://doi.org/10.26493/1855-3974.831.e12
  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. https://doi.org/10.1007/978-3-030-67899-9_17
  15. V. Chvatal, D. Rautenbach, P.M. Schafer, Finite Sholander trees, trees, and their betweenness, Discrete Math. 311 (2011), 2143-2147. https://doi.org/10.1016/j.disc.2011.06.011
  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. https://doi.org/10.1007/978-3-540-76796-1_3
  17. G. Cźedli, Coordinatization of finite join-distributive lattices, Algebra Universalis 71 (2014), 385-404. https://doi.org/10.1007/s00012-014-0282-3
  18. M. Dewar, D. Pike, J. Proos, Connectivity in hypergraphs, Canad. Math. Bull. 61 (2018), 252-271. https://doi.org/10.4153/cmb-2018-005-9
  19. J.P. Doignon, J.C. Falmagne, Knowledge Spaces, Springer-Verlag, Berlin, 1999. https://doi.org/10.1007/978-3-642-58625-5
  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. https://doi.org/10.2139/ssrn.4383265
  22. F. Dragan, F. Nicolai, A. Brandstädt, Convexity and HHD-free graphs, SIAM J. Discrete Math. 12 (1999), 119-135. https://doi.org/10.1137/s0895480195321718
  23. P. Duchet, Classical perfect graphs: An introduction with emphasis on triangulated and interval graphs, Ann. Discrete Math. 12 (1984), 67-96. https://doi.org/10.1016/s0304-0208(08)72924-4
  24. P.H. Edelman, R.E. Jamison, The theory of convex geometries, Geometriae Dedicata 19 (1985), 247-270. https://doi.org/10.1007/bf00149365
  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. https://doi.org/10.1137/0607049
  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. https://doi.org/10.1007/bfb0083463
  28. E. Howorka, A characterization of ptolemaic graphs, J. Graph Theory 5 (1981), 323-331. https://doi.org/10.1002/jgt.3190050314
  29. D. Kay, G. Chartrand, A characterization of certain ptolemaic graphs, Canad. J. Math. 17 (1965), 342-346. https://doi.org/10.4153/cjm-1965-034-0
  30. B. Korte, L. Lovász, R. Schrader, Transposition Greedoids, [in:] Greedoids, volume 4 of Algorithms and Combinatorics, Springer-Verlag, Berlin, 1991, 141-151. https://doi.org/10.1007/978-3-642-58191-5_10
  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. https://doi.org/10.4064/fm-51-1-45-64
  32. B. Monjardet, A use for frequently rediscovering a concept, Order 1 (1985), 415-417. https://doi.org/10.1007/bf00582748
  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. https://doi.org/10.1007/978-1-4899-3558-8_17
  34. B. Monjardet, Statement of precedence and a comment on IIA terminology, Games and Economic Behavior 62 (2008), 736-738. https://doi.org/10.1016/j.geb.2007.07.004
  35. M.A. Morgana, H.M. Mulder, The induced path convexity, betweenness and svelte graphs, Discrete Math. 254 (2002), 349-370. https://doi.org/10.1016/s0012-365x(01)00296-5
  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. https://doi.org/10.1016/j.ejc.2008.09.007
  39. S. Olariu, Weak bipolarizable graphs, Discrete Math. 74 (1989), 159-171. https://doi.org/10.1016/0012-365x(89)90208-2
  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. https://doi.org/10.1007/978-3-031-52213-0_20
  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. https://doi.org/10.1007/978-3-031-25211-2_33
  42. M. Stern, Semimodular Lattices: Theory and Applications, Encyclopedia of Mathematics and its Applications, vol. 73, Cambridge University Press, 1999. https://doi.org/10.1017/cbo9780511665578
  43. M.L.J. van de Vel, Theory of Convex Structures, Elsevier, North Holland, Amsterdam, 1993.
  • Iztok Peterin (corresponding author)
  • ORCID iD https://orcid.org/0000-0002-1990-6967
  • 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
  • Ameera Vaheeda Shanavas
  • University of Kerala, Department of Futures Studies, Thiruvananthapuram - 695581, India
  • Communicated by Ingo Schiermeyer.
  • Received: 2024-10-07.
  • Revised: 2025-06-10.
  • Accepted: 2025-06-10.
  • Published online: 2025-07-16.
Opuscula Mathematica - cover

Cite this article as:
Manoj Changat, Lekshmi Kamal K. Sheela, Iztok Peterin, Ameera Vaheeda Shanavas, Convex geometries yielded by transit functions, Opuscula Math. 45, no. 4 (2025), 423-450, https://doi.org/10.7494/OpMath.2025.45.4.423

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise that this website uses cookies to help us understand how the site is used. All data is anonymized. Recent versions of popular browsers provide users with control over cookies, allowing them to set their preferences to accept or reject all cookies or specific ones.