Abstract. We give sufficient conditions under which a random graph with a specified degree sequence is symmetric or asymmetric. In the case of bounded degree sequences, our characterization captures the phase transition of the symmetry of the random graphs. This phase transition coincides with that of the graph connectivity. We also show that there are unbounded degree sequences where these two thresholds do not coincide.

The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in $αn$ rounds, where $α< 2.01678$ is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than $βn$ rounds, where $β> 1.26575$. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.

The semirandom graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$ and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a perfect matching in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves a perfect matching in $\beta n$ rounds, where the value of $\beta < 1.206$ is derived from a solution to some system of differential equations. This improves upon the previously best known upper bound of $(1+2/e+o(1)) \, n < 1.736 \, n$ rounds. We also improve the previously best lower bound of $(\ln 2 + o(1)) \, n > 0.693 \, n$ and show that the player cannot achieve the desired property in less than $\alpha n$ rounds, where the value of $\alpha > 0.932$ is derived from a solution to another system of differential equations. As a result, the gap between the upper and lower bounds is decreased roughly four times.

We study the Hamiltonicity of the following model of a random graph. Suppose that we partition $[n]$ into $V_1,V_2,\ldots,V_k$ and add edge $\{x,y\}$ to our graph with probability $p$ if there exists $i$ such that $x,y\in V_i$. Otherwise, we add the edge with probability $q$. We denote this model by ${\mathcal G}({\bf n}, p,q)$ and give tight results for Hamiltonicity, including a critical window analysis, under various conditions.

We determine the rank of a random matrix A over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge [Proc. IEEE Information Theory Workshop 2013]. The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that likely diminishes the number of short linear relations.

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d ≫ log n, then the random d-regular graph (n, d) can asymptotically almost surely be “sandwiched” between (n, p1) and (n, p2) where p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for log n ≪ d ≪ n1/3−o(1), with a defect in the sandwiching: (n, d) contains (n, p1) perfectly, but is not completely contained in (n, p2). Recently, the embedding (n, p1) ⊆ (n, d) was improved by Dudek, Frieze, Ruciński and Šileikis to d = o(n). In this paper, we prove Kim–Vu's sandwich conjecture, with perfect containment on both sides, for all . For , we prove a weaker version of the sandwich conjecture with p2 approximately equal to (d/n) log n, without any defect. In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability that a random factor of a pseudorandom graph contains a given edge, which is of independent interest. As applications, we obtain new results on the properties of random graphs with given near-regular degree sequences, including Hamiltonicity and universality in subgraph containment. We also determine several graph parameters in these random graphs, such as the chromatic number, small subgraph counts, the diameter, and the independence number. We are also able to characterise many phase transitions in edge percolation on these random graphs, such as the threshold for the appearance of a giant component.

We give a linear-time algorithm that approximately uniformly generates a random simple graph with a power-law degree sequence whose exponent is at least 2.8811. While sampling graphs with power-law degree sequence of exponent at least 3 is fairly easy, and many samplers work efficiently in this case, the problem becomes dramatically more difficult when the exponent drops below 3; ours is the first provably practicable sampler for this case. We also show that with an appropriate rejection scheme, our algorithm can be tuned into an exact uniform sampler. The running time of the exact sampler is O(n2.107) with high probability, and O(n4.081) in expectation.

This paper is a continuation of previous results on the stripping number of a random uniform hypergraph, and the maximum depth over all non-$k$-core vertices. The previous results focus on the supercritical case, whereas this work analyzes these parameters in the subcritical regime and inside the critical window.

We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for $d$-regular graphs. REG can be implemented such that each graph is generated in expected time $O(nd^3)$, provided that $d=o(\sqrt{n})$. Our result significantly improves the previously best uniform sampler, which works efficiently only when $d=O(n^{1/3})$, with essentially the same running time for the same $d$. We also give a linear-time approximate sampler REG*, which generates a random $d$-regular graph whose distribution differs from the uniform by $o(1)$ in total variation distance, when $d=o(\sqrt{n})$.

We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler REG for d-regular graphs. REG can be implemented such that each graph is generated in expected time O(nd3), provided that d = o(√n). Our result significantly improves the previously best uniform sampler, which works efficiently only when d = O(n1/3), with essentially the same running time for the same d. We also give a linear-time approximate sampler REG*, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d = o(√n).

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph (n, p). For all p(n) ∊ [0,1], we show that, with high probability T is precisely the minimum between δ and ⌊m/(n – 1)⌋, where δ is the smallest degree of the graph and m denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for p such that: above this threshold, T equals ⌊m/(n – 1)⌋ and A equals ⌈m/(n – 1)⌉; and below this threshold, T equals δ, and we give a two-value concentration result for the arboricity A in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are sequentially added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most k in the two-choice load balancing problem, where k → ∞.

We describe a general approach of determining the distribution of the number of certain types of spanning subgraphs in the random graph ${\mathcal G}(n,p)$. Using this approach, we reprove the distribution of the number of Hamilton cycles with a proof that is much shorter than previously known proofs. We also achieve new results on determining the distribution of the number of spanning triangle-free subgraphs and the number of triangle-factors.

Let h>w>0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative. A (w,k)-orientation of H consists of a w-orientation of all hyperedges of H, such that each vertex receives at most k positive signs from its incident hyperedges. When k is large enough, we determine the threshold of the existence of a (w,k)-orientation of a random hypergraph. The (w,k)-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The graph case, when h=2 and w=1, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran, thereby settling a conjecture made by Karp and Saks. Motivated by a problem of cuckoo hashing, the special hypergraph case with w=k=1, was solved in three separate preprints dating from October 2009, by Frieze and Melsted, by Fountoulakis and Panagiotou, and by Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh and Rink.