Canonical and monophonic convexities in hypergraphs

Known properties of “canonical connections” from database theory and of “closed sets” from statistics implicitly define a hypergraph convexity, here called canonical convexity   (cc-convexity  ), and provide an efficient algorithm to compute cc-convex hulls. We characterize the class of hypergraphs in which cc-convexity enjoys the Minkowski–Krein–Milman property. Moreover, we compare cc-convexity with the natural extension to hypergraphs of monophonic convexity (or mm-convexity), and prove that: (1) mm-convexity is coarser than cc-convexity, (2) mm-convexity and cc-convexity are equivalent in conformal hypergraphs, and (3) mm-convex hulls can be computed in the same efficient way as cc-convex hulls.