Combinatorical and Algebraic Structures Seminar

Session details

Date: 6.3.2012
Speaker: Daniel Dombek, FJFI, České vysoké učení technické v Praze
Title: Random graphs -- Graph theory meeting probability with asymptotics
Abstract: In 1960, Paul Erd\H os and Alfréd Rényi in fact started a new area in mathematics by their paper "On the evolution of random graphs". There they studied how the "typical" (the most probable) structure of the random graph changes, depending on an asymptotical relation between $n$ - the number of vertices and $N(n)$ - the number of edges in the graph, when $n\to\infty$. This talk intends to serve as a brief introduction to the mentioned paper and as a summary of the most interesting results. The most notable result describes the remarkable change in a random graph structure when $N(n)$ passes $\frac{n}{2}$, which is often nicknamed as "phase transition". In order to give some insight into the topic, we will conclude the talk by presenting a proof of a theorem determining when a random graph typically does or does not contain subgraphs coming from certain fixed sets.

Return to index.