In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that
In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results by Karp and Sipser suggest that the first algorithm is superior. In this paper we show that this is indeed the case, at least for random
- PAR ID:
- 10240191
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 58
- Issue:
- 3
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- p. 390-429
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Abstract , where is the maximal degree and m is the number of edges, the algorithm runs in expected timeO (m ). Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected timefor the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power‐law degree sequences in cases where the previous best was O (n 4.081), and (ii)O (nd +d 4) ford ‐regular graphs when, where the previous best was O (nd 3). -
Let Ω
q =Ωq (H ) denote the set of proper [q ]‐colorings of the hypergraphH . Let Γq be the graph with vertex set Ωq where two coloringsσ ,τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that ifH =H n ,m ;k ,k ≥ 2, the randomk ‐uniform hypergraph withV =[n ] andm =dn /k hyperedges then w.h.p. Γq is connected ifd is sufficiently large and. This is optimal up to the first order in d . Furthermore, with a few more colors, we find that the diameter of Γq isO (n ) w.h.p., where the hidden constant depends ond . So, with this choice ofd ,q , the natural Glauber dynamics Markov Chain on Ωq is ergodic w.h.p. -
We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in
( n, p ) for nearly optimalp (up to afactor). In particular, we show that given t = (1 −o (1))np Hamilton cyclesC 1,…,C t , each of which is oriented arbitrarily, a digraph∼ ( n, p ) w.h.p. contains edge disjoint copies ofC 1,…,C t , provided. We also show that given an arbitrarily oriented n ‐vertex cycleC , a random digraph∼ ( n, p ) w.h.p. contains (1 ±o (1))n !p n copies ofC , provided. -
Abstract Consider the upper tail probability that the homomorphism count of a fixed graph
H within a large sparse random graphG n exceeds its expected value by a fixed factor. Going beyond the Erdős–Rényi model, we establish here explicit, sharp upper tail decay rates for sparse random d n ‐regular graphs (providedH has a regular 2‐core), and for sparse uniform random graphs. We further deal with joint upper tail probabilities for homomorphism counts of multiple graphs(extending the known results for ), and for inhomogeneous graph ensembles (such as the stochastic block model), we bound the upper tail probability by a variational problem analogous to the one that determines its decay rate in the case of sparse Erdős–Rényi graphs. -
Abstract Given a
k ‐vertex graphH and an integern , what are then ‐vertex graphs with the maximum number of induced copies ofH ? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction ofk ‐vertex subsets of ann ‐vertex graph that induce a copy ofH . Huang, Lee, and the first author proved that for a randomk ‐vertex graphH , almost surely then ‐vertex graphs maximizing the number of induced copies ofH are the balanced iterated blow‐ups ofH . In this article, we consider the case where the graphH is obtained by deleting a small number of vertices from a random Cayley graphof an abelian group. We prove that in this case, almost surely all n ‐vertex graphs maximizing the number of induced copies ofH are balanced iterated blow‐ups of.