اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMarkov degree of configurations defined by fibers of a configuration
218
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider a series of configurations defined by fibers of a given base configuration. We prove that Markov degree of the configurations is bounded from above by the Markov complexity of the base configuration. As important examples of base configurations we consider incidence matrices of graphs and study the maximum Markov degree of configurations defined by fibers of the incidence matrices. In particular we give a proof that the Markov degree for two-way transportation polytopes is three.
قيم البحث
اقرأ أيضاً
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
ry JDM, realizations in which the links between any two degree groups are placed as uniformly as possible. We prove that a swap Markov Chain Monte Carlo (MCMC) algorithm in the space of all balanced realizations of an {em 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).
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.
In this paper, we determine periodicity of quantum walks defined by mixed paths and mixed cycles. By the spectral mapping theorem of quantum walks, consideration of periodicity is reduced to eigenvalue analysis of $eta$-Hermitian adjacency matrices.
First, we investigate coefficients of the characteristic polynomials of $eta$-Hermitian adjacency matrices. We show that the characteristic polynomials of mixed trees and their underlying graphs are same. We also define $n+1$ types of mixed cycles and show that every mixed cycle is switching equivalent to one of them. We use these results to discuss periodicity. We show that the mixed paths are periodic for any $eta$. In addition, we provide a necessary and sufficient condition for a mixed cycle to be periodic and determine their periods.
We prove the conjecture by Diaconis and Eriksson (2006) that the Markov degree of the Birkhoff model is three. In fact, we prove the conjecture in a generalization of the Birkhoff model, where each voter is asked to rank a fixed number, say r, of can
didates among all candidates. We also give an exhaustive characterization of Markov bases for small r.
A Cartesian decomposition of a coherent configuration $cal X$ is defined as a special set of its parabolics that form a Cartesian decomposition of the underlying set. It turns out that every tensor decomposition of $cal X$ comes from a certain Cartes
ian decomposition. It is proved that if the coherent configuration $cal X$ is thick, then there is a unique maximal Cartesian decomposition of $cal X$, i.e., there is exactly one internal tensor decomposition of $cal X$ into indecomposable components. In particular, this implies an analog of the Krull--Schmidt theorem for the thick coherent configurations. A polynomial-time algorithm for finding the maximal Cartesian decomposition of a thick coherent configuration is constructed.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
