We show that the switch Markov chain is rapidly mixing on $P$-stable degree sequences of simple, bipartite, and directed graphs. Consequently, we have rapid mixing on power-law distribution-bounded degree sequences with parameter $\gamma2$ and on …
In this paper we give a non-trivial family of degree sequences that are not $P$-stable and the switch Markov chain is still rapidly mixing on them. This family has an intimate connection to Tyshkevich-decompositions and strong stability as well.
We show that the space of rooted tree-based phylogenetic networks is connected under rooted nearest-neighbour interchange (rNNI) moves and distance-1 tail moves.
Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three universality classes, the most studied being the 'critical' one. For this class the scaling of the quantity of …
Since 1997 a considerable effort has been spent on the study of the **swap** (switch) Markov chains on graphic degree sequences. All of these results assume some kind of regularity in the corresponding degree sequences. Recently, Greenhill and …
We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bound on the minimum number of point guards required to cover the gallery …
Various disorders including pseudoxanthoma elasticum (PXE) and generalized arterial calcification of infancy (GACI), which are caused by inactivating mutations in *ABCC6* and *ENPP1*, respectively, present with extensive tissue calcification due to …
We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the …
We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of $\Delta(D)$ which still …
We affirmatively answer and generalize the question of Kubicka, Kubicki and Lehel (1999) concerning the path-pairability of high-dimensional complete grid graphs. As an intriguing by-product of our result we significantly improve the estimate of the …