×

Axiomatic characterization of transit functions of weak hierarchies. (English) Zbl 1421.05029

Summary: Transit functions provide a unified approach to study notions of intervals, convexities, and betweenness. Recently, their scope has been extended to certain set systems associated with clustering. We characterize here the class of set systems that correspond to \(k\)-ary monotonic transit functions. Convexities form a subclass and are characterized in terms of transit functions by two additional axioms. We then focus on axiom systems associated with weak hierarchies as well as other generalizations of hierarchical set systems.

MSC:

05C05 Trees
05C99 Graph theory
52A01 Axiomatic and generalized convexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Balakrishnan, M. Changat, A. K. Lakshmikuttyamma, J. Mathew, H. M. Mulder, P. G. Narasimha-Shenoi and N. Narayanan, Axiomatic characterization of the interval function of a block graph,Discrete Math.338(2015), 885-894, doi:10.1016/j.disc.2015.01.004. · Zbl 1371.05170
[2] H.-J. Bandelt and A. W. M. Dress, Weak hierarchies associated with similarity measures— an additive clustering technique,Bull. Math. Biol.51(1989), 133-166, doi:10.1016/ s0092-8240(89)80053-9. · Zbl 0666.62058
[3] H.-J. Bandelt and A. W. M. Dress, An order theoretic framework for overlapping clustering, Discrete Math.136(1994), 21-37, doi:10.1016/0012-365x(94)00105-r. · Zbl 0832.92032
[4] J.-P. Barth´elemy and F. Brucker, Binary clustering,Discrete Appl. Math.156(2008), 1237- 1250, doi:10.1016/j.dam.2007.05.024. · Zbl 1143.91358
[5] A. Batbedat, Les isomorphismes HTS et HTE (apr‘es la bijection de Benz´ecri-Johnson),Metron 46(1988), 47-59. · Zbl 0724.05055
[6] P. Bertrand, Systems of sets such that each set properly intersects at most one other set— application to cluster analysis,Discrete Appl. Math.156(2008), 1220-1236, doi:10.1016/j. dam.2007.05.023. · Zbl 1295.05247
[7] P. Bertrand and F. Brucker, On lower-maximal paired-ultrametrics, in: P. Brito, G. Cucumel, P. Bertrand and F. de Carvalho (eds.),Selected Contributions in Data Analysis and Classification, Springer, Berlin, Heidelberg, Studies in Classification, Data Analysis, and Knowledge Organization, pp. 455-464, 2007, doi:10.1007/978-3-540-73560-1 42. · Zbl 1170.62335
[8] P. Bertrand and J. Diatta, Weak hierarchies: a central clustering structure, in: F. Aleskerov, B. Goldengorin and P. M. Pardalos (eds.),Clusters, Orders, and Trees: Methods and Applications, Springer, New York, NY, volume 92 ofSpringer Optimization and Its Applications, 2014, doi:10.1007/978-1-4939-0742-7 14, papers from the International Workshop held at the National Research University Higher School of Economics (NRU HSE), Moscow, December 12 - 13, 2012. · Zbl 1365.62231
[9] P. Bertrand and J. Diatta, Multilevel clustering models and interval convexities,Discrete Appl. Math.222(2017), 54-66, doi:10.1016/j.dam.2016.12.019. · Zbl 1403.62113
[10] P. Bertrand and M. F. Janowitz, Thek-weak hierarchical representations: an extension of the indexed closed weak hierarchies,Discrete Appl. Math.127(2003), 199-220, doi: 10.1016/s0166-218x(02)00206-8. · Zbl 1012.62067
[11] M. Changat, S. Klavˇzar and H. M. Mulder, The all-paths transit function of a graph,Czechoslovak Math. J.51(2001), 439-448, doi:10.1023/a:1013715518448. · Zbl 0977.05135
[12] M. Changat, J. Mathew and H. M. Mulder, The induced path function, monotonicity and betweenness,Discrete Appl. Math.158(2010), 426-433, doi:10.1016/j.dam.2009.10.004. · Zbl 1225.05146
[13] M. Changat and J. Mathews, Induced path transit function, monotone and Peano axioms,Discrete Math.286(2004), 185-194, doi:10.1016/j.disc.2004.02.017. · Zbl 1056.05044
[14] M. Changat, J. Mathews, I. Peterin and P. G. Narasimha-Shenoi,n-ary transit functions in graphs,Discuss. Math. Graph Theory30(2010), 671-685, doi:10.7151/dmgt.1522. · Zbl 1217.05081
[15] M. Changat, H. M. Mulder and G. Sierksma, Convexities related to path properties on graphs, Discrete Math.290(2005), 117-131, doi:10.1016/j.disc.2003.07.014. · Zbl 1058.05043
[16] M. Changat, P. G. Narasimha-Shenoi, M. Kovˇse, F. Hosseinnezhad, S. Mohandas, A. Ramachandran and P. F. Stadler, Topological representation of the transit sets ofk-point crossover operators, 2017,arXiv:1712.09022[math.CO].
[17] M. Changat, F. H. Nezhad and P. F. Stadler, Axiomatic characterization of transit functions of hierarchies,Ars Math. Contemp.14(2018), 117-128,https://amc-journal.eu/ index.php/amc/article/view/831. · Zbl 1391.05079
[18] M. Changat, G. N. Prasanth and J. Mathews, Triangle path transit functions, betweenness and pseudo-modular graphs,Discrete Math.309(2009), 1575-1583, doi:10.1016/j.disc.2008.02. 043. · Zbl 1228.05190
[19] J. Diatta, Dissimilarit´es multivoies et g´en´eralisations d’hypergraphes sans triangles,Math. Inform. Sci. Humaines138(1997), 57-73,http://www.numdam.org/item?id=MSH_1997__138__57_0. · Zbl 0910.62062
[20] E. Diday, Orders and overlapping clusters in pyramids, in: J. de Leeuw, W. Heiser, J. Meulman and F. Critchley (eds.),Multidimensional Data Analysis, DSWO Press, Leiden, volume 7 ofM&T Series, pp. 201-234, 1986, proceedings of a workshop held at Pembroke College, Cambridge University, England, June 30 - July 2, 1985.
[21] A. W. M. Dress, Towards a theory of holistic clustering, in: B. Mirkin, F. R. McMorris, F. S. Roberts and A. Rzhetsky (eds.),Mathematical Hierarchies and Biology, American Mathematical Society, Providence, RI, volume 37 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 271-290, 1997, papers from the DIMACS Workshop held in Piscataway, NJ, November 13 - 15, 1996. · Zbl 1125.91425
[22] P. Gitchoff and G. P. Wagner, Recombination induced hypergraphs:a new approach to mutation-recombination isomorphism,Complexity2(1996), 37-43, doi:10.1002/(sici) 1099-0526(199609/10)2:1h37::aid-cplx9i3.0.co;2-c.
[23] M. A. Morgana and H. M. Mulder, The induced path convexity, betweenness, and svelte graphs, Discrete Math.254(2002), 349-370, doi:10.1016/s0012-365x(01)00296-5. · Zbl 1003.05090
[24] H. M. Mulder,The Interval Function of a Graph, volume 132 ofMathematical Centre Tracts, Vrij University, Amsterdam, 1981.
[25] H. M. Mulder, Transit functions on graphs (and posets), in: M. Changat, S. Klavˇzar, H. M. Mulder and A. Vijayakumar (eds.),Convexity in Discrete Structures, Ramanujan Mathematical Society, Mysore, volume 5 ofRamanujan Mathematical Society Lecture Notes Series, 2008 pp. 117-130, joint proceedings of the International Instructional Workshop held in Thiruvananthapuram, March 22 - April 2, 2006 and the International Workshop on Metric and Convex Graph Theory held in Barcelona, June 12 - 16, 2006. · Zbl 1166.05019
[26] H. M. Mulder and L. Nebesk´y, Axiomatic characterization of the interval function of a graph, European J. Combin.30(2009), 1172-1185, doi:10.1016/j.ejc.2008.09.007. · Zbl 1205.05074
[27] P. F. Stadler and G. P. Wagner, Algebraic theory of recombination spaces,Evol. Comput.5 (1997), 241-275, doi:10.1162/evco.1997.5.3.241.
[28] M. · Zbl 0785.52001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.