Problem of the Week
Hilton Memorial Lecture
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 wv 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 wx + wy > 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.