Threshold graphs were first introduced by Chvatal and Hammer to distinguish cliques of a graph in a polydedral representation. A threshold graph is a graph G, for which there exist non-negative real weights w_v for each vertex v and a threshold number t, such that for distinct vertices x and y, xy is an edge in G if and only if w_x + w_y > t. They are important partly because they are “perfect”, but also for other reasons.

I will provide and prove several different characterizations of these graphs, as well as discuss properties of randomly generated threshold graphs, which arise very naturally. I will finish up by discussing a new generalization, now under investigation by Vaidy Sivaraman and me.