Cutting Planes for Families Implying Frankl's Conjecture

under review
  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Jonad Pulaj
Document Type:Article
Year of first publication:2016
Preprint:urn:nbn:de:0297-zib-60626