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

Abstract

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

How to cite

top

Francesco 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. [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. [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. [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. [4] R. Diestel, Graph Decompositions: A Study in Infinity Graph Theory (Clarendon Press, Oxford, 1990). Zbl0726.05001
  5. [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. [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. [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. [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. [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. [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. [11] F.M. Malvestuto, Decomposable convexities in graphs and hypergraphs, ISRN Com- binatorics 2013 Article ID 453808. doi:10.1155/2013/453808[Crossref] 
  12. [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. [13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2[Crossref] 
  14. [14] M. Van de Vel, Theory of Convex Structures (North-Holland Publishing Co., Ams- terdam, 1993). 
  15. [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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.