Between the Number of Edges and the Adjacency Matrix of a Graph

Thursday, February 5, 2015 - 2:00pm - 3:00pm
Lind 305
Eva Czabarka (University of South Carolina)
Havel and Hakimi provided a characterization of graphical degree sequences, i.e. finite sequences of nonnegative integers that can be realized as degree sequences of simple graphs. Their result led to a simple edge-swap operation that keeps the space of the graphs with a given degree sequence connected and thus gives a natural basis for Markov chain on this space. Given a partition of the vertex set of a graph, the corresponding partition adjacency matrix contains in the ij-th position the number of edges that connect vertices of the i-th and j-th partition class (this would be the number of edges and the adjacency matrix for the two trivial partitions). I will present Havel-Hakimi type results and open problems related to partition adjacency matrices.