Cutting planes for families implying Frankl's conjecture

DOI10.1090/MCOM/3461MaRDI QIDQ5207443zbMATH OpenOpenAlexWikidataFDO

Authors Jonad Pulaj

Publication date 27 December 2019

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.05947

zbMATH Keywords

cutting-plane methodextremal combinatoricsFrankl's conjectureinteger programmingunion-closed families

Mathematics Subject Classification ID

Extremal set theory (05D05) Integer programming (90C10)

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 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 imply 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.

Recommendations

• Characterizing 3-Sets in Union-Closed Families
• FC-families and improved bounds for Frankl's conjecture
• Families implying the Frankl conjecture
• A lower bound for the minimal counter-example to Frankl's conjecture
• An attempt at frankl’s conjecture

Cites work

• A hybrid branch-and-bound approach for exact rational mixed-integer programming
• An attempt at frankl’s conjecture
• Families implying the Frankl conjecture
• FC-families and improved bounds for Frankl's conjecture
• Formalizing Frankl's conjecture: FC-families
• scientific article; zbMATH DE number 2065940 (Why is no real title available?)
• scientific article; zbMATH DE number 2114680 (Why is no real title available?)
• New conjectures for union-closed families
• Note on the union-closed sets conjecture
• On union-closed families. I
• Proofs from THE BOOK
• The 11-element case of Frankl's conjecture
• The journey of the union-closed sets conjecture
• Union-closed families
• Verifying integer programming results

Cited in

(12)

• Cutting planes from a mixed integer Farkas lemma.
• Formalizing Frankl's conjecture: FC-families
• scientific article; zbMATH DE number 3947998 (Why is no real title available?)
• Minimal weight in union-closed families
• A computational status update for exact rational mixed integer programming
• A computational status update for exact rational mixed integer programming
• Characterizing 3-Sets in Union-Closed Families
• Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework
• Cutting planes for union-closed families
• Local Configurations in Union-Closed Families
• An ILP approach to determine smallest 4-regular non-Hamiltonian, nontraceable, and nonhomogeneously traceable graphs
• Satisfiability modulo theories for verifying MILP certificates

Describes a project that uses

Uses Software

• SCIP
• VIPR
• Gurobi
• CPLEX

This page was built for publication: Cutting planes for families implying Frankl's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207443)