Cutting planes for union-closed families

dc.contributor.advisorGrötschel, Martin
dc.contributor.authorPulaj, Jonad
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeGrötschel, Martin
dc.contributor.refereeBorndörfer, Ralf
dc.date.accepted2017-11-06
dc.date.accessioned2017-12-12T11:05:07Z
dc.date.available2017-12-12T11:05:07Z
dc.date.issued2017
dc.description.abstractDie Vermutung von Frankl besagt, dass es in jeder unter Vereinigung abgeschlossenen, endlichen Mengenfamilie (UC Familie) ein Element gibt, das in mindestens der Hälfte der Mengen liegt. Wir berechnen über hundert bisher unbekannte Mengenfamilien, deren Existenz zeigt, dass Frankls Vermutung für alle Familien gilt, die eine dieser Familien enthalten. Poonens Theorem charakterisiert die Existenz von Gewichten, die bestimmen, ob eine gegebene UC-Familie dafür sorgt, dass Frankls Vermutung fr alle UC-Familien gilt, die diese Familie enthalten. Wir entwerfen und implementieren ein Schnittebenenverfahren, dass die Gewichte für Poonens Theorem berechnet. Mit dieser Methode können wir mehrere offene Fragen und Vermutungen in Bezug auf strukturelle Eigenschaften von UC-Familien beantworten, einschlielich des Beweises einer Vermutung von Morris aus dem Jahr 2006 über die minimale Anzahl von Mengen der Grösse 3, die sicherstellen, dass Frankls Vermutung für alle Familien gilt, die sie enthalten.de
dc.description.abstractFrankl’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.en
dc.identifier.urihttps://depositonce.tu-berlin.de//handle/11303/7258
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-6534
dc.language.isoenen
dc.rights.urihttps://creativecommons.org/licenses/by-nc-sa/4.0/en
dc.subject.ddc510 Mathematikde
dc.subject.othercutting planesen
dc.subject.otherextremal combinatoricsen
dc.subject.otherunion-closeden
dc.subject.otherFranklen
dc.subject.otherSchnittebenenverfahrende
dc.subject.otherextremale Kombinatorikde
dc.titleCutting planes for union-closed familiesen
dc.title.translatedSchnittebenenverfahren für vereinigungsabgeschlossene Mengenfamiliende
dc.typeDoctoral Thesisen
dc.type.versionacceptedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften>Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
Files
Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
pulaj_jonad.pdf
Size:
696.29 KB
Format:
Adobe Portable Document Format
Description:
Collections