Browsing by Author "Mieczkowska, Katarzyna"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
Item Skojarzenia w hipergrafach(2014-06-17) Mieczkowska, Katarzyna; Łuczak, Tomasz. PromotorW 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.