Skojarzenia w hipergrafach
Loading...
Date
2014-06-17
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Matchings in hypergraphs
Abstract
W 1965 roku Erdős zapytał jaką maksymalną liczbę krawędzi może posiadać k-jednostajny hipergraf na n wierzchołkach o największym skojarzeniu mocy s. Postawił jednocześnie hipotezę, że hipergrafami maksymalizującymi tę liczbę są hipergraf zawierający klikę o ks+k-1 wierzchołkach, albo hipergraf składający się ze wszystkich krawędzi przecinających ustalony zbiór s wierzchołków. Gdy s jest małe drugi z tych hipergrafów ma więcej krawędzi, gdy s jest bliskie n/k zachodzi sytuacja odwrotna. W głównej części rozprawy pokazujemy, że hipoteza Erdősa jest prawdziwa dla hipergrafów k-jednostajnych jeśli tylko i, co ważniejsze, dowodzimy jej dla hipergrafów 3-jednostajnych dla . Prócz tego podajemy również szereg wyników dotyczących struktury grafów o największym skojarzeniu mocy s. Pokazują one w szczególności, że aby zweryfikować hipotezę Erdősa wystarczy pokazać prawdziwość jej słabszej, asymptotycznej wersji. W ostatnim rozdziale omawiamy nowe hipotezy i wyniki związane z hipotezą Erdősa. Między innymi stawiamy hipotezę strukturalną, która może być postrzegana jako asymptotyczne uogólnienie Twierdzenia Tutte’a na hipergrafy, oraz formułujemy hipotezę dotyczącą rozkładu sumy pewnych niezależnych zmiennych losowych, podobną do hipotezy Samuelsa z roku 1965, pokazując, że jest ona asymptotycznie równoważna ułamkowej wersji hipotezy Erdősa.
In 1965 Erdős asked what is the maximum number of edges in k-uniform hypergraphs on n vertices in which the largest matching has s edges. He conjectured that it is maximized either for cliques, or for graphs which consist of all edges intersecting a set of s vertices. Neither construction is uniformly better than the other in the whole range of parameter s ( ) so the conjectured bound is the maximum of these two possibilities. In this thesis we present results obtained while working on this problem. In particular, we confirm Erdős’ conjecture in a general k-uniform case for and, more importantly, settle it in the affirmative for k=3 and n large enough. We also derive a stability result which shows that in order to verify Erdős’ conjecture it is enough to prove it in an asymptotic form. In the last chapter, we discuss new conjectures and results obtained while working on Erdős’ problem. In particular, we formulate a structural conjecture that might be considered as an asymptotic generalization of Tutte's Theorem for hypergraphs. Moreover, we state a new probabilistic conjecture on small deviation inequalities, of a similar flavour as Samuels' conjecture stated in 1965. We confirm it in a few instances, by proving that it is asymptotically equivalent to the fractional version of Erdős’ matching problem.
In 1965 Erdős asked what is the maximum number of edges in k-uniform hypergraphs on n vertices in which the largest matching has s edges. He conjectured that it is maximized either for cliques, or for graphs which consist of all edges intersecting a set of s vertices. Neither construction is uniformly better than the other in the whole range of parameter s ( ) so the conjectured bound is the maximum of these two possibilities. In this thesis we present results obtained while working on this problem. In particular, we confirm Erdős’ conjecture in a general k-uniform case for and, more importantly, settle it in the affirmative for k=3 and n large enough. We also derive a stability result which shows that in order to verify Erdős’ conjecture it is enough to prove it in an asymptotic form. In the last chapter, we discuss new conjectures and results obtained while working on Erdős’ problem. In particular, we formulate a structural conjecture that might be considered as an asymptotic generalization of Tutte's Theorem for hypergraphs. Moreover, we state a new probabilistic conjecture on small deviation inequalities, of a similar flavour as Samuels' conjecture stated in 1965. We confirm it in a few instances, by proving that it is asymptotically equivalent to the fractional version of Erdős’ matching problem.
Description
Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej
Sponsor
Keywords
ekstremalne teoria grafów, extremal graph theory, skojarzenia, matching, hipergrafy, hypergraphs, nierówności probabilistyczne, probabilistic inequalities