Category Random Graphs

Expected number of triangles in G(n,m)

Consider picking a graph with m edges on n vertices uniformly at random from the set of all graphs with n vertices and m edges. What is the expected number of triangles? Before we give an exact formula, consider the following heuristic. We can approximate this graph with a random binomial graph (each edge appears […]

An observation on edge densities of the union of isomorphic copies of a fixed graph

Consider a fixed graph with vertices and edges respectively. Assume that is balanced which means that the maximum edge density among all possible subgraphs of is achieved from $H$. Take two copies of , call them and create a new graph . In case the two copies are edge disjoint then the edge density of […]

Giant component with Depth First Search

I just finished reading a short paper of Michael Krivelevich and Benny Sudakov, two leading experts in probabilistic combinatorics, which appeared in Arxiv about a month ago [1]. It is a simple proof of the classical result that the random binomial graph exhibits a phase transition around . When then the largest component has size […]

Visualizing the Configuration model

A way to generate a random -regular graph is via the configuration model. Here is a short description of the model. Imagine that each vertex has k tokens. This suggests that we have in total kn tokens, where is the number of vertices and you can freely think of . Also, let me mention that […]