Nichts gefunden?

Teilen Sie uns mit, welche Inhalte Sie auf unseren Seiten vermissen.

Motif-free Graph Generation
Speaker: Dominik Schweisgut

Abstract: 'The theory of random graphs and in particular random graph processes proved to provide powerful methods for various problems in graph theory. In particular, Erdös in 1947 connected the theory of random graphs with the field of Ramsey theory. In this thesis, we study two types of random graph processes. For certain strictly 2-balanced graphs H we study the H-free process and the H-removal process. Especially the triangle-free process has gained much attention for giving a new lower bound on the Ramsey number R(3, k). In this process, random edges of Kn are successively added to an empty graph as long as they do not close a triangle. The triangle-removal process works the other way round, starting from a Kn and removing the edges of a random copy of a triangle until there is no such copy left. In both cases, our main interest is in the number of edges the random graph contains after the process has finished. However, the results for the H-removal processes are not as strong as for the H-free processes and for H ∈ {C4, K4} only little is known so far. In fact, the triangle-free process is the only process where the final number of edges is known up to an error in the constant factor with high probability. In this work we provide an experimental approach to this topic by simulating the above mentioned graph processes. After giving an extensive introduction into the theory, we develop algorithms for the simulation of these processes and fit models to the obtained data. In doing so, we are able to reproduce known results for the triangle-free process and thus provide profound indications for equivalent results for other random graph processes that could not be treated by theory so far.'

Date : Thu, Jul 11

Time: 16:15

Place: SR 7