×

zbMATH — the first resource for mathematics

Cutting planes for families implying Frankl’s conjecture. (English) Zbl 1429.05199
Summary: We find previously unknown families of sets which ensure Frankl’s conjecture [P. Frankl, Extremal set systems, in: Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland); Cambridge, MA: MIT Press. 1293–1329 (1995; Zbl 0844.05094)] holds for all families that contain them using an algorithmic framework. The conjecture states that for any nonempty finite union-closed (UC) family there exists an element of the ground set in at least half the sets of the considered UC family. Poonen’s theorem [B. Poonen, J. Comb. Theory, Ser. A 59, No. 2, 253–268 (1992; Zbl 0758.05096)] characterizes the existence of weights which determine whether a given UC family implies the conjecture for all UC families which contain it. We design a cutting-plane method that computes the explicit weights which satisfy the existence conditions of Poonen’s theorem. This method enables us to answer several open questions regarding structural properties of UC families, including the construction of a counterexample to a conjecture of R. Morris [Eur. J. Comb. 27, No. 2, 269–282 (2006; Zbl 1082.05092)].
MSC:
05D05 Extremal set theory
90C10 Integer programming
Software:
CPLEX; Gurobi; SCIP; VIPR
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aigner, Martin; Ziegler, G\"unter M., Proofs from The Book, viii+274 pp. (2010), Springer-Verlag, Berlin · Zbl 1185.00001
[2] Bo\vsnjak, Ivica; Markovi\'c, Petar, The 11-element case of Frankl’s conjecture, Electron. J. Combin., 15, 1, Research Paper 88, 17 pp. (2008) · Zbl 1180.05119
[3] Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne, The graph formulation of the union-closed sets conjecture, European J. Combin., 43, 210-219 (2015) · Zbl 1301.05183
[4] Bruhn, Henning; Schaudt, Oliver, The journey of the union-closed sets conjecture, Graphs Combin., 31, 6, 2043-2074 (2015) · Zbl 1327.05249
[5] Cheung, Kevin K. H.; Gleixner, Ambros; Steffy, Daniel E., Verifying integer programming results. Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci. 10328, 148-160 (2017), Springer, Cham · Zbl 1418.90176
[6] Cook, William; Koch, Thorsten; Steffy, Daniel E.; Wolter, Kati, A hybrid branch-and-bound approach for exact rational mixed-integer programming, Math. Program. Comput., 5, 3, 305-344 (2013) · Zbl 1305.90310
[7] CPLEX IBM ILOG CPLEX. \newblock V12. 1: User’s Manual for CPLEX. \newblock \em International Business Machines Corporation, 46(53):157, 2009.
[8] SCIP Gerald Gamrath, Tobias Fischer, Tristan Gally, Ambros M. Gleixner, Gregor Hendel, Thorsten Koch, Stephen J. Maher, Matthias Miltenberger, Benjamin M\"uller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Sebastian Schenker, Robert Schwarz, Felipe Serrano, Yuji Shinano, Stefan Vigerske, Dieter Weninger, Michael Winkler, Jonas T. Witt, and Jakob Witzig, \newblock The SCIP Optimization Suite 3.2. \newblock Technical Report 15-60, ZIB, Takustr.7, 14195 Berlin, 2016.
[9] Gao, Weidong; Yu, Hongquan, Note on the union-closed sets conjecture, Ars Combin., 49, 280-288 (1998) · Zbl 0963.05129
[10] Gowers Timothy Gowers, \newblock Polymath11-func4. \newblock \urlhttps://gowers.wordpress.com. \newblock Accessed: 2017-07-17.
[11] Gurobi LLC Gurobi Optimization. \newblock Gurobi Optimizer Reference Manual. \newblock \urlhttp://www.gurobi.com. \newblock Accessed: 2017-07-17.
[12] Johnson, Robert T.; Vaughan, Theresa P., On union-closed families. I, J. Combin. Theory Ser. A, 84, 2, 242-249 (1998) · Zbl 0917.05078
[13] Serbs Filip Mari\'c, Miodrag \v Zivkovi\'c, and Bojan Vu\v ckovi\'c, \newblock \em Formalizing Frankl’s conjecture: FC-families, \newblock International Conference on Intelligent Computer Mathematics, pages 248-263. Springer, 2012.
[14] Markovi\'c, Petar, An attempt at Frankl’s conjecture, Publ. Inst. Math. (Beograd) (N.S.), 81(95), 29-43 (2007) · Zbl 1246.05004
[15] Morris, Robert, FC-families and improved bounds for Frankl’s conjecture, European J. Combin., 27, 2, 269-282 (2006) · Zbl 1082.05092
[16] Poonen, Bjorn, Union-closed families, J. Combin. Theory Ser. A, 59, 2, 253-268 (1992) · Zbl 0758.05096
[17] Pulaj, Jonad; Raymond, Annie; Theis, Dirk, New conjectures for union-closed families, Electron. J. Combin., 23, 3, Paper 3.23, 19 pp. (2016) · Zbl 1412.05193
[18] Vaughan, Theresa P., Families implying the Frankl conjecture, European J. Combin., 23, 7, 851-860 (2002) · Zbl 1021.05096
[19] Vaughan, Theresa P., A note on the union-closed sets conjecture, J. Combin. Math. Combin. Comput., 45, 95-108 (2003) · Zbl 1148.05320
[20] Vaughan, Theresa P., Three-sets in a union-closed family, J. Combin. Math. Combin. Comput., 49, 73-84 (2004) · Zbl 1053.05116
[21] 12case Bojan Vu\v ckovi\'c and Miodrag \v Zivkovi\'c, \newblock \em The 12 element case of frankl’s conjecture, \newblock preprint, 2012.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.