ﻻ يوجد ملخص باللغة العربية
In network modeling of complex systems one is often required to sample random realizations of networks that obey a given set of constraints, usually in form of graph measures. A much studied class of problems targets uniform sampling of simple graphs with given degree sequence or also with given degree correlations expressed in the form of a joint degree matrix. One approach is to use Markov chains based on edge switches (swaps) that preserve the constraints, are irreducible (ergodic) and fast mixing. In 1999, Kannan, Tetali and Vempala (KTV) proposed a simple swap Markov chain for sampling graphs with given degree sequence and conjectured that it mixes rapidly (in poly-time) for arbitrary degree sequences. While the conjecture is still open, it was proven for special degree sequences, in particular, for those of undirected and directed regular simple graphs, of half-regular bipartite graphs, and of graphs with certain bounded maximum degrees. Here we prove the fast mixing KTV conjecture for novel, exponentially large classes of irregular degree sequences. Our method is based on a canonical decomposition of degree sequences into split graph degree sequences, a structural theorem for the space of graph realizations and on a factorization theorem for Markov chains. After introducing bipartite splitted degree sequences, we also generalize the canonical split graph decomposition for bipartite and directed graphs.
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 arbitra
We present a Markov chain on the $n$-dimensional hypercube ${0,1}^n$ which satisfies $t_{{rm mix}}(epsilon) = n[1 + o(1)]$. This Markov chain alternates between random and deterministic moves and we prove that the chain has cut-off with a window of s
We explore the notion of degree of asymmetry for integer sequences and related combinatorial objects. The degree of asymmetry is a new combinatorial statistic that measures how far an object is from being symmetric. We define this notion for composit
We consider the three-state toric homogeneous Markov chain model (THMC) without loops and initial parameters. At time $T$, the size of the design matrix is $6 times 3cdot 2^{T-1}$ and the convex hull of its columns is the model polytope. We study the
The weight of a subgraph $H$ in $G$ is the sum of the degrees in $G$ of vertices of $H$. The {em height} of a subgraph $H$ in $G$ is the maximum degree of vertices of $H$ in $G$. A star in a given graph is minor if its center has degree at most five