×

Canonical and monophonic convexities in hypergraphs. (English) Zbl 1211.05093

Summary: Known properties of “canonical connections” from database theory and of “closed sets” from statistics 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.

MSC:

05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. Ass. Comp. Machinery, 30, 479-513 (1983) · Zbl 0624.68087
[2] Bishop, Y. M.; Fienberg, S. E.; Holland, P., Discrete Multivariate Analysis (1975), M.I.T. Press: M.I.T. Press Cambridge, MA
[3] Changat, M.; Mathew, J., On triangle path convexity in graphs, Discrete Math., 206, 91-95 (1999) · Zbl 0929.05046
[4] Changat, M.; Mulder, H. M.; Sierksma, G., Convexities related to path properties on graphs, Discrete Math., 290, 117-131 (2005) · Zbl 1058.05043
[5] D’Atri, A.; Moscarini, M., On hypergraph acyclicity and graph chordality, Inform. Process. Lett., 29, 271-274 (1988) · Zbl 0662.68111
[6] Diestel, R., Graph Decompositions (1990), Clarendon Press: Clarendon Press Oxford
[7] Dobra, A.; Fienberg, S. E., Bounds for cell entries in contingency tables given marginal totals and decomposable graphs, Proc. Natl. Acad. Sci., 97, 11885-11892 (2000) · Zbl 0960.62059
[8] Duchet, P., Convex sets in graphs II: Minimal path convexity, J. Combin. Theory Ser. B, 44, 307-316 (1988) · Zbl 0672.52001
[9] Duchet, P., (Graham, R. L.; Grötschel, M.; Lovász, L., Hypergraphs. Hypergraphs, Handbook of Combinatorics, vol. I (1995), North-Holland), 381-432 · Zbl 0859.05063
[10] Fagin, R., Degrees of acyclicity for hypergraphs and relational database schemes, J. Assoc. Comput. Mach., 30, 514-5550 (1983) · Zbl 0624.68088
[11] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Alg. Disc. Math., 7, 433-444 (1986) · Zbl 0591.05056
[12] Haberman, S. J., Log-linear Models for Contingency Tables (1974), University of Chicago Press: University of Chicago Press Chicago
[13] Jamison, R. E., Copoints in antimatroids, Congressus Numerantium, 29, 535-554 (1980) · Zbl 0463.05005
[14] Jamison, R. E., A perspective on abstract convexity: Classifying alignments by varieties, (Kay, D. C.; Breen, M., Convexity and Related Combinatorial Geometry (1982), Marcel Dekker: Marcel Dekker New York) · Zbl 0482.52001
[15] Lauritzen, S. L., Graphical Models (1996), Clarendon Press: Clarendon Press Oxford · Zbl 0907.62001
[16] Leimer, H.-G., Optimal decomposition by clique separators, Discrete Math., 113, 99-123 (1993) · Zbl 0793.05128
[17] Maier, D.; Ullman, J. D., Connections in acyclic hypergraphs, Theoret. Comput. Sci., 32, 185-199 (1984) · Zbl 0557.05054
[18] Malvestuto, F. M., A hypergraph-theoretic analysis of collapsibility and decomposability for extended log-linear models, Stat. Comput., 11, 155-169 (2001)
[19] Malvestuto, F. M.; Moscarini, M., A fast algorithm for query optimization in universal-relation databases, J. Comput. System Sci., 56, 299-309 (1998) · Zbl 0913.68060
[20] Malvestuto, F. M.; Moscarini, M., Decomposition of a hypergraph by partial-edge separators, Theoret. Comput. Sci., 237, 57-79 (2000) · Zbl 0939.68089
[21] Tarjan, R. E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 566-579 (1984) · Zbl 0545.68062
[22] Van de Vel, M., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
[23] Welsh, D. J.A., (Graham, R. L.; Grötschel, M.; Lovász, L., Matroids: Fundamental Concepts. Matroids: Fundamental Concepts, Handbook of Combinatorics, vol. I (1995), North-Holland), 481-526 · Zbl 0853.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.