×

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:

SCIP; CPLEX; VIPR; Gurobi
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aigner, Martin; Ziegler, G\"{u}nter M., Proofs from The Book, viii+274 pp. (2010), Springer-Verlag, Berlin · Zbl 1185.00001
[2] Bo\v{s}njak, 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. V12. 1: User’s Manual for CPLEX. 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, The SCIP Optimization Suite 3.2. 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, Polymath11-func4. https://gowers.wordpress.com. Accessed: 2017-07-17.
[11] Gurobi LLC Gurobi Optimization. Gurobi Optimizer Reference Manual. http://www.gurobi.com. 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 Zivkovi\'c, and Bojan Vuckovi\'c, Formalizing Frankl’s conjecture: FC-families, International Conference on Intelligent Computer Mathematics, pages 248-263. Springer, 2012. · Zbl 1360.68758
[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, The 12 element case of frankl’s conjecture, 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. 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.