Własności losowych nakryć grafów

Abstract

Przedmiotem rozprawy doktorskiej są asymptotyczne własności losowych nakryć grafów zdefiniowanych przez Amita i Liniala w 2002 roku, jako nowy model grafu losowego. Dla zadanego grafu bazowego G losowe nakrycie stopnia n, oznaczane jako Ḡ, otrzymujemy poprzez zastąpienie każdego wierzchołka v przez n-elementowy zbiór Ḡ_v oraz wybór, dla każdej krawędzi e={x,y} \in E(G), z jednostajnym prawdopodobieństwem, losowego skojarzenia pomiędzy zbiorami Ḡ_x i Ḡ_y. Pierwszym zagadnieniem poruszanym w pracy jest oszacowanie wielkości największej topologicznej kliki zawartej (jako podgraf) w losowym nakryciu danego grafu G. Udało się pokazać, że asymptotycznie prawie na pewno losowe nakrycie grafu G zawiera największą z możliwych topologiczną klikę. Drugim badanym zagadnieniem jest pytanie o istnienie w podniesieniu grafu cyklu Hamiltona. W pracy pokazujemy, że jeżeli graf G zawiera dwa krawędziowo rozłączne cykle Hamiltona, których suma nie jest grafem dwudzielnym i ma minimalny stopień co najmniej 5, to asymptotycznie prawie na pewno nakrycie Ḡ jest grafem hamiltonowskim.

In the thesis we study selected properties of random coverings of graphs introduced by Amit and Linial in 2002. A random n-covering of a graph G, denoted by Ḡ, is obtained by replacing each vertex v of G by an n-element set Ḡ_v and then choosing, independently for every edge e = {x,y}\in E(G), uniformly at random a perfect matching between Ḡ_x and Ḡ_y. The first problem we consider is the typical size of the largest topological clique in random covering of given graph G. We show that asymptotically almost surely a random n-covering of a graph G contains the largest possible topological clique. The second property we examine is the existence of a Hamilton cycle in Ḡ. We show that if G contains two edge disjoint Hamilton cycles, which sum is not a bipartite graph and has minimum degree at least 5, then asymptotically almost surely Ḡ is Hamiltonian.