Polyhedral methods applied to extremal combinatorics problems
| dc.contributor.advisor | Grötschel, Martin | en |
| dc.contributor.author | Raymond, Annie | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.contributor.referee | Grötschel, Martin | en |
| dc.contributor.referee | Borndörfer, Ralf | en |
| dc.date.accepted | 2014-06-23 | |
| dc.date.accessioned | 2015-11-20T23:44:20Z | |
| dc.date.available | 2014-08-21T12:00:00Z | |
| dc.date.issued | 2014-08-21 | |
| dc.date.submitted | 2014-08-19 | |
| dc.description.abstract | Wir untersuchen Polytope, die zwei bekannte Probleme beschreiben: das Hypergraphen-Problem von Turán und die Vermutung von Frankl. Das Hypergraphen-Problem von Turán bestimmt die maximale Anzahl der r-Kanten in einem r-Hypergraph mit n Knoten, so dass der daraus entstandene r-Teil-Hypergraph keine Clique der Größe a enthält. Wenn r=2 ist, also für Graphen, ist die Antwort bekannt und wird in Turáns Satz beschrieben. Jedoch, wenn r>=3 ist, bleibt das Problem offen. Wir modellieren das Problem als ein ganzzahliges lineares Programm. Wir ziehen eine Parallele zwischen dem Stabile-Mengen-Polytop und etwas, das wir Turán-Polytop nennen möchten. Damit zeigen wir, dass generalisierte und transformierte Versionen von den Cliquen-, Zirkulanten- und Rad-Ungleichungen auch facettendefinierend für das Turán-Polytop sind. Wir veranschaulichen, dass andere Rangungleichungen und Verdoppelungsungleichungen facettendefinierend sind. Diese Facetten führen zu einem einfachen neuen polyedrischen Beweis von Turáns Satz für Graphen und ergeben Schranken für das Problem für Hypergraphen. Die Vermutung von Frankl besagt, dass es in jeder unter Vereinigung abgeschlossenen, endlichen Mengenfamilie ein Element gibt, das in mindestens der Hälfte der Mengen liegt. Wir modellieren dieses Problem auch als ein ganzzahliges lineares Programm und präsentieren hilfreiche Schnittebenen und Facetten, die hinzugefügt werden können. Die Rechenergebnisse führen zu einer neuen Vermutung: Wir behaupten, dass die maximale Anzahl der Mengen in einer Familie, in der jedes Element in maximal a Mengen enthalten ist, unabhängig von der Anzahl n der Elemente der Mengenfamilie ist, wenn n>=log_2(a)+1 ist. Wir stellen auch eine Minimierungsversion dieser Vermutung vor und zeigen, dass beide Vermutungen äquivalent sind. Wir beweisen diese Aussage für n>=a. Mit einem kürzlich vorgestellten Satz von Balla, Bollobás und Eccles zeigen wir, dass diese neue Vermutung impliziert, dass die Vermutung von Frankl für alle Familien mit m Mengen, m in [2/3*2^i, 2^i], i in N, die unter Vereinigung abgeschlossen sind, wahr ist. Außerdem impliziert ein Beweis der neuen Vermutung, dass jede Familie die unter Vereinigung abgeschlossen ist, ein Element enthält, welches in mindestens 6/13*m der m Mengen enthalten ist. Dies verbessert die aktuelle Schranke von (m-1)/(log_2 m) auf 6/13*m. Abschließend stellen wir das Konzept von Zwillings-Mengen vor, und diskutieren, welche wichtige Rolle es im Zusammenhang mit der neuen Vermutung spielt. Die Ergebnisse bezüglich Frankls Vermutung wurden gemeinsam mit Jonad Pulaj von dem Konrad-Zuse-Zentrum und Dirk Theis von der Universität von Tartu erzielt. | de |
| dc.description.abstract | We study the polytopes describing two famous problems: the Turán hypergraph problem and the Frankl union-closed sets conjecture. The Turán hypergraph problem asks to find the maximum number of r-edges in an r-uniform hypergraph on n vertices that does not contain a clique of size a. When r=2, i.e. for graphs, the answer is well-known and can be found in Turán's theorem. However, when r>=3, the problem remains open. We model the problem as an integer program. We draw parallels between the stable set polytope and what we call the Turán polytope; we show that generalized and transformed versions of the clique, web, and wheel inequalities are also facet-defining for the Turán polytope. We also show that some other rank inequalities as well as doubling inequalities are facet-defining. These facets lead to a simple new polyhedral proof of Turán's theorem for graphs and yield some bounds in the case of the problem for hypergraphs. The Frankl conjecture on the other hand states that there always exists an element contained in more than half of the sets of a non-empty union-closed family. We also model this problem as an integer program and discuss some helpful cuts and facets that can be added. The computations lead to a new conjecture: we claim that the maximum number of sets in a non-empty union-closed family where each element is present at most a times is independent of the number of elements n spanned by the sets if n>=log_2(a)+1. We also present a minimization version of this conjecture and show that both conjectures are equivalent. We prove this new conjecture partially for n>=a. By using a recent theorem of Balla, Bollobás and Eccles, we show that proving this new conjecture would imply that the original Frankl conjecture holds for all union-closed families of m sets when 2/3*2^i <=m<= 2^i for some i in N. Moreover, proving the new conjecture would yield that any non-empty union-closed family of m sets contains an element in at least 6/13*m of those sets, a much better bound than the current (m-1)/(log_2 m). Finally, we introduce the concept of twin sets and discuss its importance for the new conjecture. The work on the Frankl conjecture was done jointly with Jonad Pulaj of the Konrad-Zuse-Zentrum and Dirk Theis of the University of Tartu. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus4-56106 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/4463 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-4166 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 500 Naturwissenschaften und Mathematik | en |
| dc.subject.other | Turán | de |
| dc.subject.other | Frankl | de |
| dc.subject.other | Polytop | de |
| dc.subject.other | Hypergraph | de |
| dc.subject.other | Turán | en |
| dc.subject.other | Frankl | en |
| dc.subject.other | polytope | en |
| dc.subject.other | hypergraph | en |
| dc.subject.other | union-closed | en |
| dc.title | Polyhedral methods applied to extremal combinatorics problems | en |
| dc.title.translated | Polyedrische Methoden für extreme kombinatorische Probleme | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus4 | 5610 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1