On a uniformly random chord diagram and its intersection graph

A chord diagram refers to a set of chords with distinct endpoints on a circle. The intersection graph of a chord diagram $\cal C$ is defined by substituting the chords of $\cal C$ with vertices and by adding edges between two vertices whenever the corresponding two chords cross each other. Let $C_n$ and $G_n$ denote the chord diagram chosen uniformly at random from all chord diagrams with $n$ chords and the corresponding intersection graph, respectively. We analyze $C_n$ and $G_n$ as $n$ tends to infinity. In particular, we study the degree of a random vertex in $G_n$, the $k$-core of $G_n$, and the number of strong components of the directed graph obtained from $G_n$ by orienting edges by flipping a fair coin for each edge. We also give two equivalent evolutions of a random chord diagram and show that, with probability approaching $1$, a chord diagram produced after $m$ steps of these evolutions becomes monolithic as $m$ tends to infinity and stays monolithic afterward forever.

No reviews yet.

No comments yet.