6062
eng
reportzib
0
--
2016-10-19
--
Cutting Planes for Families Implying Frankl's Conjecture
We find previously unknown families which imply Frankl’s conjecture using an algorithmic framework. The conjecture states that for any non-empty union-closed (or Frankl) family there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine whether a given Frankl family implies the conjecture for all Frankl families which contain it. A Frankl family is Non–Frankl-Complete (Non–FC), if it does not imply the conjecture in its elements for some Frankl family that contains it. We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem. This method allows us to find a counterexample to a ten-year-old conjecture by R. Morris about the structure of generators for Non–FC-families.
1438-0064
urn:nbn:de:0297-zib-60626
Jonad Pulaj
Jonad Pulaj
ZIB-Report
16-51
eng
uncontrolled
extremal combinatorics, extremal set theory, cutting plane, exact integer programming
General Literature
GENERAL
COMBINATORICS (For finite fields, see 11Txx)
Mathematical Optimization
Mathematical Optimization Methods
Pulaj, Jonad
MIP-ZIBOPT
MODAL-SynLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6062/ZIB_Report_16_51.pdf
https://opus4.kobv.de/opus4-zib/files/6062/revisedPulaj.pdf