O strukturze grafów Kroneckera
Loading...
Date
2019
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
On the structure of Kronecker graphs
Abstract
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.
In the thesis we study the asymptotic structure of Kronecker graphs. Kronecker graph is a graph, where vertex set is the set of all binary vectors of length n, where the probability that two vertices are connected depends on the number of positions in their labels on which they have common zeros, common ones, and different values. In the thesis we study the behaviour of these graphs as n tends to infinity. In the first part of the work we examine several properties of Kronecker graphs such as k-connectivity and the existence of a perfect matching. In particular, we show that the thresholds for connectivity and for the existence of perfect matching basically coincide. These results are partially based on my paper published in Electronic Journal of Combinatorics. In the last chapter of the thesis we study the diameter of Kronecker graphs and prove that just above the connectivity threshold, the diameter of Kronecker graphs, with probability tending to 1 as n tends to infinity, is bounded from above by a constant. The article containing this result, by Tomasz Łuczak and myself, was published in Discrete Mathematics.
In the thesis we study the asymptotic structure of Kronecker graphs. Kronecker graph is a graph, where vertex set is the set of all binary vectors of length n, where the probability that two vertices are connected depends on the number of positions in their labels on which they have common zeros, common ones, and different values. In the thesis we study the behaviour of these graphs as n tends to infinity. In the first part of the work we examine several properties of Kronecker graphs such as k-connectivity and the existence of a perfect matching. In particular, we show that the thresholds for connectivity and for the existence of perfect matching basically coincide. These results are partially based on my paper published in Electronic Journal of Combinatorics. In the last chapter of the thesis we study the diameter of Kronecker graphs and prove that just above the connectivity threshold, the diameter of Kronecker graphs, with probability tending to 1 as n tends to infinity, is bounded from above by a constant. The article containing this result, by Tomasz Łuczak and myself, was published in Discrete Mathematics.
Description
Wydział Matematyki i Informatyki
Sponsor
Keywords
graphs, grafy, combinatorics, kombinatoryka, random structures, struktury losowe, Kronecker graphs, grafy Kroneckera