Feb. 16 2009 2:00PM

Feb. 16 2009 3:30PM

Known properties of "collapsibility" from probability theory implicitly define a hypergraph convexity, here called canonical convexity (c-convexity), and provide an efficient algorithm to compute c-convex hulls. We characterize the class of hypergraphs in which c-convexity enjoys the Minkowski-Krein-Milman property. Moreover, we compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or m-convexity), and prove that: (1) m-convexity is coarser than c-convexity, (2) m-convexity and c-convexity are equivalent in conformal hypergraphs, and (3) m-convex hulls can be computed in the same efficient way as c-convex hulls.
Reference:
F.M. Malvestuto, Canonical and monophonic convexities in hypergraphs, Discrete Mathematics (article in press)

Pravidelný seminář Inteligentní systémy (Contact person: Tomáš Kroupa)