# Decomposability of Abstract and Path-Induced Convexities in Hypergraphs

Francesco Mario Malvestuto; Marina Moscarini

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 3, page 493-515
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topFrancesco Mario Malvestuto, and Marina Moscarini. "Decomposability of Abstract and Path-Induced Convexities in Hypergraphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 493-515. <http://eudml.org/doc/271209>.

@article{FrancescoMarioMalvestuto2015,

abstract = {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.},

author = {Francesco Mario Malvestuto, Marina Moscarini},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {convex hull; hypergraph convexity; path-induced convexity; con- vex geometry.; convex geometry},

language = {eng},

number = {3},

pages = {493-515},

title = {Decomposability of Abstract and Path-Induced Convexities in Hypergraphs},

url = {http://eudml.org/doc/271209},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Francesco Mario Malvestuto

AU - Marina Moscarini

TI - Decomposability of Abstract and Path-Induced Convexities in Hypergraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 3

SP - 493

EP - 515

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

LA - eng

KW - convex hull; hypergraph convexity; path-induced convexity; con- vex geometry.; convex geometry

UR - http://eudml.org/doc/271209

ER -

## References

top- [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] Zbl0624.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] Zbl0929.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] Zbl1058.05043
- [4] R. Diestel, Graph Decompositions: A Study in Infinity Graph Theory (Clarendon Press, Oxford, 1990). Zbl0726.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 Zbl0644.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] Zbl0672.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. Zbl0957.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] Zbl0591.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] Zbl1238.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] Zbl0454.68078