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

Cutting Planes for Families Implying Frankl's Conjecture

Zitieren Sie bitte immer diese 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Jonad Pulaj
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:extremal combinatorics, extremal set theory, cutting plane, exact integer programming
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx)
CCS-Klassifikation:A. General Literature
PACS-Klassifikation:00.00.00 GENERAL
Datum der Erstveröffentlichung:19.10.2016
Schriftenreihe (Bandnummer):ZIB-Report (16-51)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.