Wydział Matematyki i Informatyki (WMiI)/Faculty of Mathematics and Computer Science

Permanent URI for this community

Now showing 1 - 1 of 1

O strukturze grafów Kroneckera
(2019) Banaszak, Justyna; Łuczak, Tomasz. Promotor
Przedmiotem pracy jest asymptotyczna struktura grafów Kroneckera. Grafem Kroneckera nazywamy graf, w którym zbiór wierzchołków stanowią wszystkie ciągi binarne o długości n, w którym prawdopodobieństwo, że dwa wierzchołki są połączone krawędzią zależy od liczby pozycji, na których mają one wspólne jedynki, wspólne zera oraz różne wartości. W pracy badam zachowanie grafów Kroneckera przy n dążącym do nieskończoności. W pierwszej części pracy rozważam własności grafów Kroneckera takie jak istnienie skojarzenia doskonałego i δ-krawędziowa spójność, gdzie δ jest minimalnym stopniem grafu. Pokazuję między innymi, że próg dla istnienia skojarzenia doskonałego jest taki sam, jak próg spójności tego grafu. Prezentowane tu wyniki częściowo opierają się na mojej pracy opublikowanej w Electronic Journal of Combinatorics. W ostatnim rozdziale pracy dowodzę, że za progiem spójności grafy Kroneckera mają stałą średnicę z prawdopodobieńśtwem dążącym do 1, gdy n dąży do nieskończoności. Wynik ten pochodzi z mojej wspólnej pracy z Tomaszem Łuczakiem, opublikowanej w Discrete Mathematics.