Random threshold graphs (Q2380296)

Summary: 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, \dots, x_n\) uniformly in \([0, 1]\); distinct vertices \(i, j\) of \(G\) are adjacent exactly when \(x_i + x_j \geqslant 1\). We examine various properties of random threshold graphs such as chromatic number, algebraic connectivity, and the existence of Hamiltonian cycles and perfect matchings.