Random Threshold Graphs

Abstract

We introduce a pair of natural, equivalent models for random threshold graphs and use these models to deduce a variety of properties of random threshold graphs. Specifically, a random threshold graph $G$ is generated by choosing $n$ IID values $x_1,\ldots,x_n$ uniformly in $[0,1]$; distinct vertices $i,j$ of $G$ are adjacent exactly when $x_i + x_j \ge 1$. We examine various properties of random threshold graphs such as chromatic number, algebraic connectivity, and the existence of Hamiltonian cycles and perfect matchings.