# Random Structures & Algorithms

Random Structures & Algorithms > 55 > 3 > 584 - 614

*n*‐vertex

*d*‐dimensional cube of the integer lattice graph ${Z}^{d}$. We study the effects that the strong spatial mixing condition (SSM) has on the rate of convergence to equilibrium of

*nonlocal*Markov chains. We prove that when SSM holds, the relaxation time (i.e., the inverse spectral gap) of general

*block dynamics*is

*O*(

*r*), where

*r*is the...

Random Structures & Algorithms > 55 > 3 > 696 - 718

*m*edges is added, exhibit any symmetry...

Random Structures & Algorithms > 55 > 3 > 560 - 583

*r*get connected by an edge with probability proportional to

*r*

^{−s}, for

*s*∈ (

*d*,2

*d*), and study the asymptotic of the graph‐theoretical (a.k.a. chemical) distance

*D*(

*x*,

*y*) between

*x*and

*y*in the limit as |

*x*−

*y*|→

*∞*. For the model on ${Z}^{d}$ we show that, in probability as |

*x*|→

*∞*, the distance

*D*(0,

*x*) is squeezed between two positive...

Random Structures & Algorithms > 55 > 3 > 677 - 695

*d*‐dimensional analog of Cayley's formula for the number of

*n*‐vertex trees. He enumerated

*d*‐dimensional hypertrees weighted by the squared size of their (

*d*− 1)‐dimensional homology group. This, however, does not answer the more basic problem of unweighted enumeration of

*d*‐hypertrees, which is our concern here. Our main result, Theorem 1.4, significantly...

Random Structures & Algorithms > 55 > 3 > 649 - 676

Random Structures & Algorithms > 55 > 3 > 742 - 771

*α*‐stable...

Random Structures & Algorithms > 55 > 3 > 719 - 741

*G*is called the cop number of

*G*. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant

*C*, the cop number of every connected graph

*G*is at most $C\sqrt{\left|V\right(G\left)\right|}$. In a separate paper, we showed...

Random Structures & Algorithms > 55 > 3 > 545 - 559

*λ*

_{1}(

*λ*

_{2}) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree...

Random Structures & Algorithms > 55 > 3 > 531 - 544

*G*

_{n,1/2}typically admits a covering of a constant fraction of its edges by edge‐disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: for $k\ll \sqrt{n}$ and

*A*

_{1},…,

*A*

_{t}chosen uniformly and independently from the

*k*‐subsets of {1,…,

*n*}, what...

Random Structures & Algorithms > 55 > 3 > 615 - 648

*D*+ 1)‐edge‐colored, bipartite graphs with a fixed number of vertices 2

*p*. These graphs encode

*D*‐dimensional orientable colored complexes. We investigate the behavior of those graphs as

*p*→

*∞*. The techniques involved in this study also yield a Central Limit Theorem for the genus of a uniform map of order

*p*, as

*p*→

*∞*.