Search

The switch chain is a well-studied Markov chain which can be used to sample approximately uniformly from the set $\Omega(\boldsymbol{d})$ of all graphs with a given degree sequence $\boldsymbol{d}$. Polynomial mixing time (rapid mixing) has been established for the switch chain under various conditions on the degree sequences. Amanatidis and Kleer introduced the notion of strongly stable families of degree sequences, and proved that the switch chain is rapidly mixing for any degree sequence from a strongly stable family. Using a different approach, Erd\H{o}s et al. recently extended this result to the (possibly larger) class of P-stable degree sequences, introduced by Jerrum and Sinclair in 1990. We define a new notion of stability for a given degree sequence, namely $k$-\emph{stability}, and prove that if a degree sequence $\boldsymbol{d}$ is 8-stable then the switch chain on $\Omega(\boldsymbol{d})$ is rapidly mixing. We also provide sufficient conditions for P-stability, strong stability and 8-stability. Using these sufficient conditions, we give the first proof of P-stability for various families of heavy-tailed degree sequences, including power-law degree sequences, and show that the switch chain is rapidly mixing for these families. We further extend these notions and results to directed degree sequences., Comment: 32 pages, 6 figures. This version addresses referee comments

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d G log n, then the random d-regular graph G(n, d) can asymptotically almost surely be "sandwiched" between G(n, p1) and G(n, p2) where p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for log n L d L n1/3−o(1), with a defect in the sandwiching: G(n, d) contains G(n, p1) perfectly, but is not completely contained in G(n, p2). Recently, the embedding G(n, p1) ⊆ G(n, d) was improved by Dudek, Frieze, Rucinski and Sileikis to d = o(n). In this paper, we prove Kim-Vu's sandwich conjecture, with perfect containment on both sides, for all [MATH HERE]. For [MATH HERE], 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.

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 u v 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 Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in c ∗ n rounds, where the value of c ∗ is the result of a high dimensional optimization problem. Numerical computations indicate that c ∗ 2 . 61135 . This improves upon the previously best known upper bound of 3 n rounds. We also show that the previously best lower bound of ( ln 2 + ln ( 1 + ln 2 ) + o ( 1 ) ) n is not tight.

Given an integer k, we consider the parallel k-stripping process applied to a hypergraph H: removing all vertices with degree less than k in each iteration until reaching the k-core of H. Take H as H_r(n,m): a random r-uniform hypergraph on n vertices and m hyperedges with the uniform distribution. Fixing k,r\ge 2 with (k,r)\neq (2,2), it has previously been proved that there is a constant c_{r,k} such that for all m=cn with constant c\neq c_{r,k}, with high probability, the parallel k-stripping process takes O(\log n) iterations. In this paper we investigate the critical case when c=c_{r,k}+o(1). We show that the number of iterations that the process takes can go up to some power of n, as long as c approaches c_{r,k} sufficiently fast. A second result we show involves the depth of a non-k-core vertex v: the minimum number of steps required to delete v from H_r(n,m) where in each step one vertex with degree less than k is removed. We will prove lower and upper bounds on the maximum depth over all non-k-core vertices.

We study the arboricity A and the maximum number T of edge-disjoint spanning trees of the classical random graph G (n, p). For all p(n) ∈ [0, 1], we show that, with high probability, T is precisely the minimum between δ and bm/(n − 1)c, 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 bm/(n−1)c and A equals dm/(n−1)e; 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 →∞.

Let $H_n$ be a graph on $n$ vertices and let $\overline{H_n}$ denote the complement of $H_n$. Suppose that $\Delta = \Delta(n)$ is the maximum degree of $\overline{H_n}$. We analyse three algorithms for sampling $d$-regular subgraphs ($d$-factors) of $H_n$. This is equivalent to uniformly sampling $d$-regular graphs which avoid a set $E(\overline{H_n})$ of forbidden edges. Here $d=d(n)$ is a positive integer which may depend on $n$. Two of these algorithms produce a uniformly random $d$-factor of $H_n$ in expected runtime which is linear in $n$ and low-degree polynomial in $d$ and $\Delta$. The first algorithm applies when $(d+\Delta)d\Delta = o(n)$. This improves on an earlier algorithm by the first author, which required constant $d$ and at most a linear number of edges in $\overline{H_n}$. The second algorithm applies when $H_n$ is regular and $d^2+\Delta^2 = o(n)$, adapting an approach developed by the first author together with Wormald. The third algorithm is a simplification of the second, and produces an approximately uniform $d$-factor of $H_n$ in time $O(dn)$. Here the output distribution differs from uniform by $o(1)$ in total variation distance, provided that $d^2+\Delta^2 = o(n)$.

This paper focuses on the balancedness of symmetric Boolean functions. We prove a conjecture presented by Canteaut and Videau, which states that the balanced symmetric Boolean functions of fixed algebraic degree are trivially balanced when the number of variables is large enough. Denoted by $\sigma _{n,d}$ , the $n$ -variable elementary symmetric Boolean function of degree $d$ . As an application of this result to elementary symmetric Boolean functions, we show that all the trivially balanced elementary symmetric Boolean functions are of the form $\sigma _{2^{t+1}l-1,2^{t}}$ , where $t$ and $l$ are any positive integers. It implies that Cusick et al. ’s conjecture, which claims that $ \sigma _{2^{t+1}l-1,2^{t}}$ is the only nonlinear balanced elementary symmetric Boolean functions, is equivalent to the conjecture that all the balanced elementary symmetric Boolean functions are trivially balanced.

We count the asymptotic number of triangles in uniform random graphs where the degree distribution follows a power law with degree exponent $\tau\in(2,3)$. We also analyze the local clustering coefficient $c(k)$, the probability that two random neighbors of a vertex of degree $k$ are connected. We find that the number of triangles, as well as the local clustering coefficient, scale similarly as in the erased configuration model, where all self-loops and multiple edges of the configuration model are removed. Interestingly, uniform random graphs contain more triangles than erased configuration models with the same degree sequence. The number of triangles in uniform random graphs is closely related to that in a version of the rank-1 inhomogeneous random graph, where all vertices are equipped with weights, and the probabilities that edges are present are moderated by asymptotically linear functions of the products of these vertex weights.

Let $h>w>0$ be two fixed integers. Let $\orH$ be a random hypergraph whose hyperedges are all of cardinality $h$. To {\em $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 $\orH$ consists of a $w$-orientation of all hyperedges of $\orH$, 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, which settled a conjecture of Karp and Saks., 47 pages, 1 figures, the journal version of [16]

Let $A$ be a random $m\times n$ matrix over the finite field $F_q$ with precisely $k$ non-zero entries per row and let $y\in F_q^m$ be a random vector chosen independently of $A$. We identify the threshold $m/n$ up to which the linear system $A x=y$ has a solution with high probability and analyse the geometry of the set of solutions. In the special case $q=2$, known as the random $k$-XORSAT problem, the threshold was determined by [Dubois and Mandler 2002, Dietzfelbinger et al. 2010, Pittel and Sorkin 2016], and the proof technique was subsequently extended to the cases $q=3,4$ [Falke and Goerdt 2012]. But the argument depends on technically demanding second moment calculations that do not generalise to $q>3$. Here we approach the problem from the viewpoint of a decoding task, which leads to a transparent combinatorial proof.

Let $G$ be a simple graph that is properly edge coloured with $m$ colours and let $\M=\{M_1,\ldots, M_m\}$ be the set of $m$ matchings induced by the colours in $G$. Suppose that $m\le n-n^{c}$, where $c>9/10$, and every matching in $\M$ has size $n$. Then $G$ contains a full rainbow matching, i.e.\ a matching that contains exactly one edge from $M_i$ for each $1\le i\le m$. This answers an open problem of Pokrovskiy and gives an affirmative answer to a generalisation of a special case of a conjecture of Aharoni and Berger. Related results are also found for multigraphs with edges of bounded multiplicity, and for hypergraphs. Finally, we provide counterexamples to several conjectures on full rainbow matchings made by Aharoni and Berger., This updated version combines another arxiv document:1710.04807

We consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After n – 3 steps, we obtain a random triangulated plane graph with n vertices, which is called a Random Apollonian Network (RAN). We show that asymptotically almost surely (a.a.s.) a longest path in a RAN has length o(n), refuting a conjecture of Frieze and Tsourakakis. We also show that a RAN always has a cycle (and thus a path) of length , and that the expected length of its longest cycles (and paths) is . Finally, we prove that a.a.s. the diameter of a RAN is asymptotic to , where is the solution of an explicit equation. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 703–725, 2014

In this paper, we show that in the random graph Gn,c/n, with high probability, there exists an integer ki¾? such that a subgraph of Gn,c/n, whose vertex set differs from a densest subgraph of Gn,c/n by Olog2n vertices, is sandwiched by the ki¾? and the ki¾?+1-core, for almost all sufficiently large c. We determine the value of ki¾?. We also prove that a, the threshold of the k-core being balanced coincides with the threshold that the average degree of the k-core is at most 2k-1, for all sufficiently large k; b with high probability, there is a subgraph of Gn,c/n whose density is significantly denser than any of its nonempty cores, for almost all sufficiently large c > 0. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 341-360, 2015

Let$(G_m)_{0\le m\le \binom{n}{2}}$be the random graph process starting from the empty graph on vertex set [n] and with a random edge added in each step. Letmkdenote the minimum integer such thatGmkcontains ak-regular subgraph. We prove that for all sufficiently largek, there exist two constants εk≥ σk> 0, with εk→ 0 ask→ ∞, such that asymptotically almost surely anyk-regular subgraph ofGmkhas size between (1 − εk)|${\mathcal C}_k$| and (1 − σk)|${\mathcal C}_k$|, where${\mathcal C}_k$denotes thek-core ofGmk.

We consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After n − 3 steps, we obtain a random triangulated plane graph with n vertices, which is called a Random Apollonian Network (RAN). We show that asymptotically almost surely (a.a.s.) every path in a RAN has length o ( n ) , refuting a conjecture of Frieze and Tsourakakis. We also show that a RAN always has a path of length ( 2 n − 5 ) log 2 / log 3 , and that the expected length of its longest path is Ω ( n 0.88 ) . Finally, we prove that a.a.s. the diameter of a RAN is asymptotic to c log n , where c ≈ 1.668 is the solution of an explicit equation.

Given a constant integer d ? 1 and a host graph H that is sufficiently dense, we lower bound the number of d-factors H contains. When the complement of H is sufficiently sparse, we provide an algorithm that uniformly generates the d-factors of H and we justify the efficiency of the algorithm.

In this paper, we examine the moments of the number of d -factors in for all p and d satisfying d3 = o(p2n). We also determine the limiting distribution of the number of d -factors inside this range with further restriction that as n ∞.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

We study the connectivity of random d-regular graphs which are recursively generated by an algorithm motivated by a peer-to-peer network. We show that these graphs are asymptotically almost surely d-connected for any even constant d⩾4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 185–197, 2010 © 2010 Wiley Periodicals, Inc.

We study a random system of cn linear equations over n variables in GF(2), where each equation contains exactly r variables; this is equivalent to r-XORSAT. Previous work has established a clustering threshold, c^*_r for this model: if c=c_r^*-\epsilon for any constant \epsilon>0 then with high probability all solutions form a well-connected cluster; whereas if c=c^*_r+\epsilon, then with high probability the solutions partition into well-connected, well-separated clusters (with probability tending to 1 as n goes to infinity). This is part of a general clustering phenomenon which is hypothesized to arise in most of the commonly studied models of random constraint satisfaction problems, via sophisticated but mostly non-rigorous techniques from statistical physics. We extend that study to the range c=c^*_r+o(1), and prove that the connectivity parameters of the r-XORSAT clusters undergo a smooth transition around the clustering threshold., Comment: 25 pages. A major part of this paper has appeared in the preprint arXiv:1309.6651

We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on $2n$ vertices are bounded by $O(n^{3})$ and $O(n^{10})$, in the convex and general case, respectively. We then apply similar methods to prove an $n^{O(\log(n))}$ upper bound on the Ramsey number of a path with $n$ ordered vertices., Comment: 15 pages, 7 figures

We study the asymptotic distribution of the number of matchings of size $\ell=\ell(n)$ in $G(n,p)$ for a wide range of $p=p(n)\in (0,1)$ and for every $1\le \ell\le \lfloor n/2\rfloor$. We prove that this distribution changes from normal to log-normal as $\ell$ increases, and we determine the critical value of $\ell$, as a function of $n$ and $p$, at which the transition of the limiting distribution occurs.

In this paper, we estimate the geometric Ramsey numbers of trees. Given a tree T n on n vertices and an outerplanar graph H m on m vertices, we estimate the minimum number M = M ( T n , H m ) such that, for any set of M points in the plane such that no three of them are collinear, and for any 2-colouring of the segments determined by the M points, either the first colour class contains a non-crossing copy of T n , or the second colour class contains a non-crossing copy of H m . We prove that M ( T n , H m ) = ( n - 1 ) ( m - 1 ) + 1 if (i) the points are in convex position, T n is a caterpillar and H m is Hamiltonian, or if (ii) the points are in general position, T n has at most two non-leaf vertices, and H m is Hamiltonian. We also prove several polynomial bounds for M ( T n , H m ) for other classes of T n and H m .

We prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n 3) and O(n 10), in the convex and general case, respectively. We also prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases.

We describe a general approach of determining the distribution of spanning subgraphs in the random graph $\G(n,p)$. In particular, we determine the distribution of spanning subgraphs of certain given degree sequences, which is a generalisation of the $d$-factors, of spanning triangle-free subgraphs, of (directed) Hamilton cycles and of spanning subgraphs that are isomorphic to a collection of vertex disjoint (directed) triangles., 17 pages, 2 figures

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.

The pegging algorithm is a method of generating large random regular graphs beginning with small ones. The $\epsilon$-mixing time of the distribution of short cycle counts of these random regular graphs is the time at which the distribution reaches and maintains total variation distance at most $\epsilon$ from its limiting distribution. We show that this $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound $O(\epsilon^{-1})$ proved recently by the authors is essentially tight.

Let G"n","d denote the uniformly random d-regular graph on n vertices. For any S@?[n], we obtain estimates of the probability that the subgraph of G"n","d induced by S is a given graph H. The estimate gives an asymptotic formula for any d=o(n^1^/^3), provided that H does not contain almost all the edges of the random graph. The result is further extended to the probability space of random graphs with a given degree sequence.