Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 12 von 15
Zurück zur Trefferliste

Cutting Planes for Union-Closed Families

  • Frankl’s (union-closed sets) conjecture states that for any nonempty finite union-closed (UC) family of distinct sets there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine whether a given UC family ensures Frankl’s conjecture holds for all UC families which contain it. The weight systems are nontrivial to identify for a given UC family, and methods to determine such weight systems have led to several other open questions and conjectures regarding structures in UC families. We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem using computational integer programming coupled with redundant verification routines that ensure correctness. We find over one hundred previously unknown families of sets which ensure Frankl’s conjecture holds for all families that contain any of them. This improves significantly on all previous results of the kind. Our framework allows us to answer several open questions and conjectures regarding structural properties of UC families, including proving the 3-sets conjecture of Morris from 2006 which characterizes the minimum number of 3-sets that ensure Frankl’s conjecture holds for all families that contain them. Furthermore, our method provides a general algorithmic road-map for improving other known results and uncovering structures in UC families.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Jonad Pulaj
Dokumentart:Dissertation
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Titel verleihende Institution:Technische Universität Berlin
Betreuer:Martin Grötschel, Ralf Borndörfer
Jahr der Erstveröffentlichung:2017
URL:https://depositonce.tu-berlin.de//handle/11303/7258
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.