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.

Download full text files

Export metadata

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)