Geodesic
Decomposability of Abstract and Path-Induced Convexities in Hypergraphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 493-515 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: convex hull, hypergraph convexity, path-induced convexity, con- vex geometry 
@article{DMGT_2015_35_3_a8,
     author = {Malvestuto, Francesco Mario and Moscarini, Marina},
     title = {Decomposability of {Abstract} and {Path-Induced} {Convexities} in {Hypergraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {493--515},
     year = {2015},
     volume = {35},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a8/}
}
TY  - JOUR
AU  - Malvestuto, Francesco Mario
AU  - Moscarini, Marina
TI  - Decomposability of Abstract and Path-Induced Convexities in Hypergraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 493
EP  - 515
VL  - 35
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a8/
LA  - en
ID  - DMGT_2015_35_3_a8
ER  - 
%0 Journal Article
%A Malvestuto, Francesco Mario
%A Moscarini, Marina
%T Decomposability of Abstract and Path-Induced Convexities in Hypergraphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 493-515
%V 35
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a8/
%G en
%F DMGT_2015_35_3_a8
Malvestuto, Francesco Mario; Moscarini, Marina. Decomposability of Abstract and Path-Induced Convexities in Hypergraphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 493-515. http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a8/

[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

[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

[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

[4] R. Diestel, Graph Decompositions: A Study in Infinity Graph Theory (Clarendon Press, Oxford, 1990).

[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

[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

[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.

[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

[9] H.-G. Leimer, Optimal decomposition by clique separators, Discrete Math. 113 (1993) 99-123. doi:10.1016/0012-365X(93)90510-Z

[10] F.M. Malvestuto, Canonical and monophonic convexities in hypergraphs, Discrete Math. 309 (2009) 4287-4298. doi:10.1016/j.disc.2009.01.003

[11] F.M. Malvestuto, Decomposable convexities in graphs and hypergraphs, ISRN Com- binatorics 2013 Article ID 453808. doi:10.1155/2013/453808

[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

[13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2

[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