Sách Random Threshold Graphs

Threshold graphs were introduced by Chv´atal and Hammer in [4, 5]; see also [6, 13]. There are
several, logically equivalent ways to define this family of graphs, but the one we choose works
well for developing a model of random graphs. A simple graph G is a threshold graph if we can
assign weights to the vertices such that a pair of distinct vertices is adjacent exactly when the
sum of their assigned weights is or exceeds a specified threshold. Without loss of generality, the
threshold can be taken to be 1 and the weights can be restricted to lie in the interval [0,1]; see
Definition 2.1. References [2, 9, 16] provide an extensive introduction to this class of graphs.
If we choose the weights for the vertices at random, we induce a probability measure on
the set of threshold graphs and thereby create a notion of a random threshold graph. Given
that we may assume the weights lie in [0,1] it is natural to take the weights independently
and uniformly in that interval; a careful definition is given in §3.1. The idea of choosing a
random representation has been explored in other contexts such as random geometric graphs
[18] (choose points in a metric space at random to represent vertices that are adjacent if their
points are within a specified distance) and random interval graphs [19] (choose real intervals at
random to represent vertices that are adjacent if their intervals intersect).
A different approach to random threshold graphs that is based on a recursive description of
their structure (see Theorem 2.7) was presented in [11] whose goal was to use threshold graphs