Cutting Planes for Families Implying Frankl's Conjecture
Please always quote using this URN: urn:nbn:de:0297-zib-60626
- 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.
Author: | Jonad Pulaj |
---|---|
Document Type: | ZIB-Report |
Tag: | extremal combinatorics, extremal set theory, cutting plane, exact integer programming |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) |
CCS-Classification: | A. General Literature |
PACS-Classification: | 00.00.00 GENERAL |
Date of first Publication: | 2016/10/19 |
Series (Serial Number): | ZIB-Report (16-51) |
ISSN: | 1438-0064 |