An abstract convexity space on a connected hypergraph H with vertex set V (H) is a family C of subsets of V (H) (to be called the convex sets of H) such that: (i) C contains the empty set and V (H), (ii) C is closed under intersection, and (iii) every set in C is connected in H. A convex set X of H is a minimal vertex convex separator of H if there exist two vertices of H that are separated by X and are not separated by any convex set that is a proper subset of X. A nonempty subset X of V (H) is a cluster of H if in H every two vertices in X are not separated by any convex set. The cluster hypergraph of H is the hypergraph with vertex set V (H) whose edges are the maximal clusters of H. A convexity space on H is called decomposable if it satisfies the following three properties: (C1) the cluster hypergraph of H is acyclic, (C2) every edge of the cluster hypergraph of H is convex, (C3) for every nonempty proper subset X of V (H), a vertex v does not belong to the convex hull of X if and only if v is separated from X in H by a convex cluster. It is known that the monophonic convexity (i.e., the convexity induced by the set of chordless paths) on a connected hypergraph is decomposable. In this paper we first provide two characterizations of decomposable convexities and then, after introducing the notion of a hereditary path family in a connected hypergraph H, we show that the convexity space on H induced by any hereditary path family containing all chordless paths (such as the families of simple paths and of all paths) is decomposable.
@article{bwmeta1.element.doi-10_7151_dmgt_1815,
author = {Francesco Mario Malvestuto and Marina Moscarini},
title = {Decomposability of Abstract and Path-Induced Convexities in Hypergraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {493-515},
zbl = {1317.05134},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1815}
}
Francesco Mario Malvestuto; Marina Moscarini. Decomposability of Abstract and Path-Induced Convexities in Hypergraphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 493-515. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1815/
[1] C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirability of acyclic database schemes, J. ACM 30 (1983) 479-513. doi:10.1145/2402.322389[Crossref] | Zbl 0624.68087
[2] M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999) 91-95. doi:10.1016/S0012-365X(98)00394-X[Crossref] | Zbl 0929.05046
[3] 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[Crossref] | Zbl 1058.05043
[4] R. Diestel, Graph Decompositions: A Study in Infinity Graph Theory (Clarendon Press, Oxford, 1990). | Zbl 0726.05001
[5] P. Duchet, Convexity in combinatorial structures, in: Proceedings of the 14th Winter School on Abstract Analysis, Frolik, Souček and Fabián (Eds), (Circolo Matematico di Palermo, Palermo 1987), Serie II 14 261-293 | Zbl 0644.52001
[6] P. Duchet, Convex sets in graphs II: minimal path convexity, J. Combin. Theory Ser. B 44 (1988) 307-316. doi:10.1016/0095-8956(88)90039-1[Crossref] | Zbl 0672.52001
[7] P. Duchet, Discrete convexity: retractions, morphisms and the partition problem, in: Proceedings of the Conference on Graph Connections, Balakrishnan, Mulder and Vijayakumar (Ed(s)), (Allied Publishers, New Delhi, 1999) 10-18. | Zbl 0957.05030
[8] M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs, SIAM J. Alge- braic Discrete Methods 7 (1986) 433-444. doi:10.1137/0607049[Crossref] | Zbl 0591.05056
[9] H.-G. Leimer, Optimal decomposition by clique separators, Discrete Math. 113 (1993) 99-123. doi:10.1016/0012-365X(93)90510-Z[Crossref]
[10] F.M. Malvestuto, Canonical and monophonic convexities in hypergraphs, Discrete Math. 309 (2009) 4287-4298. doi:10.1016/j.disc.2009.01.003[Crossref][WoS]
[11] F.M. Malvestuto, Decomposable convexities in graphs and hypergraphs, ISRN Com- binatorics 2013 Article ID 453808. doi:10.1155/2013/453808[Crossref]
[12] F.M. Malvestuto, M. Mezzini and M. Moscarini, Equivalence between hypergraph convexities ISRN Discrete Mathematics 2011 Article ID 806193. doi:10.5402/2011/806193[Crossref] | Zbl 1238.05186
[13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2[Crossref]
[14] M. Van de Vel, Theory of Convex Structures (North-Holland Publishing Co., Ams- terdam, 1993).
[15] S. Whitesides, An Algorithm for finding clique cut-sets, Inform. Process. Lett. 12 (1981) 31-32. doi:10.1016/0020-0190(81)90072-7 [Crossref] | Zbl 0454.68078