Cutting planes for families implying Frankl’s conjecture
HTML articles powered by AMS MathViewer
- by Jonad Pulaj;
- Math. Comp. 89 (2020), 829-857
- DOI: https://doi.org/10.1090/mcom/3461
- Published electronically: July 25, 2019
- HTML | PDF | Request permission
Abstract:
We find previously unknown families of sets which ensure Frankl’s conjecture 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 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 Morris from 2006.References
- Martin Aigner and Günter M. Ziegler, Proofs from The Book, 4th ed., Springer-Verlag, Berlin, 2010. MR 2569612, DOI 10.1007/978-3-642-00856-6
- Ivica Bošnjak and Petar Marković, The 11-element case of Frankl’s conjecture, Electron. J. Combin. 15 (2008), no. 1, Research Paper 88, 17. MR 2426151, DOI 10.37236/812
- Henning Bruhn, Pierre Charbit, Oliver Schaudt, and Jan Arne Telle, The graph formulation of the union-closed sets conjecture, European J. Combin. 43 (2015), 210–219. MR 3266293, DOI 10.1016/j.ejc.2014.08.030
- Henning Bruhn and Oliver Schaudt, The journey of the union-closed sets conjecture, Graphs Combin. 31 (2015), no. 6, 2043–2074. MR 3417215, DOI 10.1007/s00373-014-1515-0
- Kevin K. H. Cheung, Ambros Gleixner, and Daniel E. Steffy, Verifying integer programming results, Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 10328, Springer, Cham, 2017, pp. 148–160. MR 3678781, DOI 10.1007/978-3-319-59250-3_{1}3
- William Cook, Thorsten Koch, Daniel E. Steffy, and Kati Wolter, A hybrid branch-and-bound approach for exact rational mixed-integer programming, Math. Program. Comput. 5 (2013), no. 3, 305–344. MR 3102373, DOI 10.1007/s12532-013-0055-6
- IBM ILOG CPLEX. V12. 1: User’s Manual for CPLEX. International Business Machines Corporation, 46(53):157, 2009.
- Gerald Gamrath, Tobias Fischer, Tristan Gally, Ambros M. Gleixner, Gregor Hendel, Thorsten Koch, Stephen J. Maher, Matthias Miltenberger, Benjamin Müller, 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.
- Weidong Gao and Hongquan Yu, Note on the union-closed sets conjecture, Ars Combin. 49 (1998), 280–288. MR 1633064
- Timothy Gowers, Polymath11–func4. https://gowers.wordpress.com. Accessed: 2017-07-17.
- LLC Gurobi Optimization. Gurobi Optimizer Reference Manual. http://www.gurobi.com. Accessed: 2017-07-17.
- Robert T. Johnson and Theresa P. Vaughan, On union-closed families. I, J. Combin. Theory Ser. A 84 (1998), no. 2, 242–249. MR 1652849, DOI 10.1006/jcta.1998.2888
- Filip Marić, Miodrag Živković, and Bojan Vučković, Formalizing Frankl’s conjecture: FC-families, International Conference on Intelligent Computer Mathematics, pages 248–263. Springer, 2012.
- Petar Marković, An attempt at Frankl’s conjecture, Publ. Inst. Math. (Beograd) (N.S.) 81(95) (2007), 29–43. MR 2401312, DOI 10.2298/PIM0795029M
- Robert Morris, FC-families and improved bounds for Frankl’s conjecture, European J. Combin. 27 (2006), no. 2, 269–282. MR 2199779, DOI 10.1016/j.ejc.2004.07.012
- Bjorn Poonen, Union-closed families, J. Combin. Theory Ser. A 59 (1992), no. 2, 253–268. MR 1149898, DOI 10.1016/0097-3165(92)90068-6
- Jonad Pulaj, Annie Raymond, and Dirk Theis, New conjectures for union-closed families, Electron. J. Combin. 23 (2016), no. 3, Paper 3.23, 19. MR 3558060, DOI 10.37236/5749
- Theresa P. Vaughan, Families implying the Frankl conjecture, European J. Combin. 23 (2002), no. 7, 851–860. MR 1932685, DOI 10.1006/eujc.2002.0586
- Theresa P. Vaughan, A note on the union-closed sets conjecture, J. Combin. Math. Combin. Comput. 45 (2003), 95–108. MR 1982637
- Theresa P. Vaughan, Three-sets in a union-closed family, J. Combin. Math. Combin. Comput. 49 (2004), 73–84. MR 2054964
- Bojan Vučković and Miodrag Živković, The 12 element case of frankl’s conjecture, preprint, 2012.
Bibliographic Information
- Jonad Pulaj
- Affiliation: Department of Mathematical Optimization, Zuse Institute Berlin (ZIB) Takustrasse 7, 14195 Berlin, Germany
- Address at time of publication: Department of Mathematics and Computer Science, Davidson College, Davidson, North Carolina, 28035
- MR Author ID: 1182719
- Email: jopulaj@davidson.edu
- Received by editor(s): June 3, 2018
- Received by editor(s) in revised form: February 20, 2019, and May 9, 2019
- Published electronically: July 25, 2019
- Additional Notes: The work for this article has been (partly) conducted within the Research Campus MODAL funded by the German Federal Ministry of Education and Research (BMBF grant number 05M14ZAM)
- © Copyright 2019 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 829-857
- MSC (2010): Primary 05D05, 90C10
- DOI: https://doi.org/10.1090/mcom/3461
- MathSciNet review: 4044452