Search

We show that the eigenpolytopes of graphs are universal in the sense that every polytope, up to affine equivalence, appears as the eigenpolytope of some positively weighted graph. We next extend the theory of graphical designs, which are quadrature rules for graphs, to positively weighted graphs. Through Gale duality for polytopes, we show a bijection between graphical designs and the faces of eigenpolytopes. This bijection proves the existence of graphical designs with positive quadrature weights and upper bounds the size of a minimal graphical design. Connecting this bijection with the universality of eigenpolytopes, we establish three complexity results: It is strongly NP-complete to determine if there is a graphical design smaller than the mentioned upper bound, it is NP-hard to find a smallest graphical design, and it is \#P-complete to count the number of minimal graphical designs. [ABSTRACT FROM AUTHOR]

The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, joint degree constraints are given. These constraints specify how many edges there should be between two given degree classes (i.e., subsets of nodes that all have the same degree). Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. In the case of one degree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodes have the same degree), but beyond this very little is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. We do this by combining a recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al. [Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings. [ABSTRACT FROM AUTHOR]

A joint degree matrix (JDM) specifies the number of connections between nodes of given degrees in a graph, for all degree pairs, and uniquely determines the degree sequence of the graph. We consider the space of all balanced realizations of an arbitrary JDM, realizations in which the links between any two fixed-degree groups of nodes are placed as uniformly as possible. We prove that a swap Markov chain Monte Carlo algorithm in the space of all balanced realizations of an arbitrary graphical JDM mixes rapidly, i.e., the relaxation time of the chain is bounded from above by a polynomial in the number of nodes n. To prove fast mixing, we first prove a general factorization theorem similar to the Martin-Randall method for disjoint decompositions (partitions). This theorem can be used to bound from below the spectral gap with the help of fast mixing subchains within every partition and a bound on an auxiliary Markov chain between the partitions. Our proof of the general factorization theorem is direct and uses conductance based methods (Cheeger inequality). [ABSTRACT FROM AUTHOR]