Search

The k-core, defined as the maximal subgraph of minimum degree at least k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [J Combin Theory Ser B 67 (1996), 111–151] determined the threshold dk for the appearance of an extensive k-core. The aim of the present paper is to describe how the k-core is “embedded” into the random graph in the following sense. Let k≥3 and fix d=np>dk. Colour each vertex that belongs to the k-core of G(n,p) in black and all remaining vertices in white. Here we derive a multi-type branching process that describes the local structure of this coloured random object as n tends to infinity. This generalises prior results on, e.g., the internal structure of the k-core. In the physics literature it was suggested to characterize the core by means of a message passing algorithm called Warning Propagation. Ibrahimi, Kanoria, Kraning and Montanari [Ann Appl Probab 25 (2015), 2743–2808] used this characterization to describe the 2-core of random hypergraphs. To derive our main result we use a similar approach. A key observation is that a bounded number of iterations of this algorithm is enough to give a good approximation of the k-core. Based on this the study of the k-core reduces to the analysis of Warning Propagation on a suitable Galton-Watson tree. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 00, 000–000, 2017

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph 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|VG|. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph Gn,p, which improves upon existing results showing that asymptotically almost surely the cop number of Gn,p is Onlogn provided that pni¾?2+elogn for some e>0. We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion-type properties. This will also be used in a separate paper on random d-regular graphs, where we show that the conjecture holds asymptotically almost surely when d=dni¾?3. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396-421, 2016

We consider connectivity properties of certain i.i.d. random environments on i¾?d, where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the random set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two-dimensional models that are non-monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111-137, 2014

The Erdos-Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a 'blocking' set B of at most f(k) vertices such that the graph G - B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor-closed class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763-775), we showed that, amongst all graphs on vertex set [n] = {1,...,n} which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor-closed graph class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} with 2-connected excluded minors, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on [n] which contain at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, all but an exponentially small proportion contain a set B of k vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. (This is not the case when \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} contains all fans.) For a random graph R sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc.

In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + mp ≤ D(Gn) ≤ n + mp + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and mp depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D(Gn) = n + mp (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m - n ≫ n2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly-connected digraphs with parameters m and n among all such digraphs with positive in/out-degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

Szemeredi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory [J. Komlos and M. Simonovits, Szemeredi's Regularity Lemma and its applications in graph theory, Combinatorics 2 (1996), 295-352]. Many of its applications are based on the following technical fact: If G is a k-partite graph with V(G) = ∪ki=1 Vi, |Vi| = n for all i ∈ [k], and all pairs {Vi, Vj}, 1 ≤ i < j ≤ k, are e-regular of density d, then G contains d??nk(1 + f(e)) cliques K(2)k, where f(e) → 0 as e → 0. The aim of this paper is to establish the analogous statement for 3-uniform hypergraphs. Our result, to which we refer as The Counting Lemma, together with Theorem 3.5 of P. Frankl and V. Rodl [Extremal problems on set systems, Random Structures Algorithms 20(2) (2002), 131-164), a Regularity Lemma for Hypergraphs, can be applied in various situations as Szemeredi's Regularity Lemma is for graphs. Some of these applications are discussed in previous papers, as well as in upcoming papers, of the authors and others.

Szemeredi's Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rodl [8] allows some of the Szemeredi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemeredi's Lemma showed the equivalence between the property of e-regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of e-regularity led to an algorithmic version of Szemeredi's lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random "blocks of hyperedges" which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficient conditions for this hypergraph regularity. These conditions enable us to design an algorithmic version of a hypergraph regularity lemma in [8]. This algorithmic version is presented by the authors in [5].

In previous papers the authors showed that almost all d-regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001

The Lovasz local lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovasz local lemma does not supply a polynomial-time algorithm for finding these structures. Beck was the first who gave a method of converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. He applied his technique to the symmetric form of the Lovasz local lemma and, in particular, to the problem of 2-coloring uniform hypergraphs. In this paper we investigate the general form of the Lovasz local lemma. Our main result is a randomized algorithm for 2-coloring nonuniform hypergraphs that runs in expected linear time. Even for uniform hypergraphs no algorithm with such a runtime bound was previously known, and no polynomial-time algorithm was known at all for the class of nonuniform hypergraphs we will consider in this paper. Our algorithm and its analysis provide a novel approach to the general Lovasz local lemma that may be of independent interest. We also show how to extend our result to the c-coloring problem. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 213–237, 2000

Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by Kamath et al. to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253

Let Gn, p denote a random graph on n vertices. It is an interesting problem when small cliques arise and what distributions of the number of small cliques may occur. Matroids are natural generalization of graphs; therefore, we can try to investigate maximal flats of a small rank in random matroids. The most studied and most interesting seem to be “random projective geometries” introduced by Kelly and Oxley. Many of the theorems in our paper are based on the results published in a long paper of Barbour, Janson, Karoski, and Ruciski. However, proofs for projective geometries generally are more complicated. © 1995 Wiley Periodicals, Inc.

In this paper we shall investigate the connection between the SzemerCdi Regularity Lemma and quasirandom graph sequences, defined by Chung, Graham, and Wilson, and also, slightly differently, by Thomason. We prove that a graph sequence (G,) is quasirandom if and only if in the SzemerCdi partitions of G, almost all densities are $ + o(1). Many attempts have been made to clarify when an individual event could be called random and in what sense. Both the fundamental problems of probability theory and some practical application need this clarification very much. For example, in applications of the Monte-Carlo method one needs to know if the random number generator used yields a sequence which can be regarded “pseudorandom” or not. The literature on this question is extremely extensive. Thomason [6-81 and Chung, Graham, and Wilson [2,3], and also Frankl, Rodl, and Wilson [4] started a new line of investigation, where (instead of regarding numerical sequences) they gave some characterizations of “randomlike” graph sequences, matrix sequences, and hypergraph sequences. The aim of this paper is to contribute to this question in case of graphs, continuing the above line of investigation. Let %(n, p) denote the probability space of labelled graphs on n vertices, where the edges are chosen independently and at random, with probability p. We shall say that “a random graph sequence (G,) has property P”

In breakthrough results, Saxton-Thomason and Balogh-Morris-Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simp ...

The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing & Louchard as the block sizes in a parking scheme. In the coalescent forest representation, some edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by adding edges between the roots. This construction induces the same process at the level of cluster sizes, but allows one to make numerous connections with some combinatorial and probabilistic models that were not known to be connected with additive coalescent. The variety of the combinatorial objects involved here – size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees – justifies our interests in this Acknowledgement : The research has been supported by ANR-14-CE25-0014 (ANR GRAAL).

Consider the random graph G(Pn,r) whose vertex set Pn is a Poisson point process of intensity n on (-12,12]d,d2. Any two vertices Xi,XjPn are connected by an edge with probability g(d(Xi,Xj)r), independently of all other edges, and independent of the other points of Pn. d is the toroidal metric, r > 0 and g:0,)0,1] is non-increasing and =dg(|x|)dx ) does not have any isolated nodes satisfies lim?nnMndlog?n=1. Let =inf?{x > 0:xg(x)> 1}, and be the volume of the unit ball in d. Then for all >, G(Pn,(log?nn)1d) is connected with probability approaching one as n. The bound can be seen to be tight for the usual random geometric graph obtained by setting g=10,1]. We also prove some useful results on the asymptotic behavior of the length of the edges and the degree distribution in the connectivity regime. The results in this paper work for connection functions g that are not necessarily compactly supported but satisfy g(r)=o(r-c).

Let $G=G(n)$ be a graph on $n$ vertices with maximum degree $\Delta=\Delta(n)$. Assign to each vertex $v$ of $G$ a list $L(v)$ of colors by choosing each list independently and uniformly at random from all $k$-subsets of a color set $\mathcal{C}$ of size $\sigma= \sigma(n)$. Such a list assignment is called a \emph{random $(k,\mathcal{C})$-list assignment}. In this paper, we are interested in determining the asymptotic probability (as $n \to \infty$) of the existence of a proper coloring $\varphi$ of $G$, such that $\varphi(v) \in L(v)$ for every vertex $v$ of $G$, a so-called $L$-coloring. We give various lower bounds on $\sigma$, in terms of $n$, $k$ and $\Delta$, which ensures that with probability tending to 1 as $n \to \infty$ there is an $L$-coloring of $G$. In particular, we show, for all fixed $k$ and growing $n$, that if $\sigma(n) = \omega(n^{1/k^2} \Delta^{1/k})$ and $\Delta=O\left(n^{\frac{k-1}{k(k^3+ 2k^2 - k +1)}}\right)$, then the probability that $G$ has an $L$-coloring tends to 1 as $n \rightarrow \infty$. If $k\geq 2$ and $\Delta= \Omega(n^{1/2})$, then the same conclusion holds provided that $\sigma=\omega(\Delta)$. We also give related results for other bounds on $\Delta$, when $k$ is constant or a strictly increasing function of $n$.

We continue our study of the full set of translation-invariant splitting Gibbs measures TISGMs, translation-invariant tree-indexed Markov chains for the q-state Potts model on a Cayley tree. In our previous work Kulske et al., J Stat Phys 156 2014, 189-200 we gave a full description of the TISGMs, and showed in particular that at sufficiently low temperatures their number is 2q-1. In this paper we find some regions for the temperature parameter ensuring that a given TISGM is non-extreme in the set of all Gibbs measures. In particular we show the existence of a temperature interval for which there are at least 2q-1+q extremal TISGMs. For the Cayley tree of order two we give explicit formulae and some numerical values. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 636-678, 2017

The classical Corr adi-Hajnal theorem claims that every n-vertex graph G with (G) 2n=3 contains a triangle factor, when 3jn. In this paper we asymptotically determine the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n-vertex graph with (G) = o(n) and (G) (1=2 + o(1))n, then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratic many edges, and (G) (1=2 +o(1))n, then G has a Kr-factor for n suciently large. We also propose many related open problems whose solutions could show a relationship with RamseyTur an theory. Additionally, we also consider a fractional variant of the Corr adi-Hajnal Theorem, settling a conjecture of Balogh-Kemkes-Lee-Young. Let t2 (0; 1) and w : E(Kn)! [0; 1]. We call a triangle in Kn heavy if the sum of the weights on its edges is more than 3t. We prove that if 3jn and w is such that for every vertex v the sum of w(e)

We consider a model for complex networks that was introduced by Krioukov et al. (Phys Rev E 82 (2010) 036106). In this model, N points are chosen randomly inside a disk on the hyperbolic plane according to a distorted version of the uniform distribution and any two of them are joined by an edge if they are within a certain hyperbolic distance. This model exhibits a power-law degree sequence, small distances and high clustering. The model is controlled by two parameters α and ν where, roughly speaking, α controls the exponent of the power-law and ν controls the average degree. In this paper we focus on the probability that the graph is connected. We show the following results. For α > 1/2 and ν arbitrary, the graph is disconnected with high probability. For α < 1/2 and ν arbitrary, the graph is connected with high probability. When α = 1/2 and ν is fixed then the probability of being connected tends to a constant f(ν) that depends only on ν, in a continuous manner. Curiously, f(ν) = 1 for ν ≥ Π while it is strictly increasing, and in particular bounded away from zero and one, for 0 < ν < Π. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 65–94, 2016.

In 2002, Bollobas and Scott posed the following problem: for an integer k≥2 and a graph G of m edges, what is the smallest f(k, m) such that V(G) can be partitioned into V 1,…,Vk in which e(Vi∪Vj)≤f(k,m) for all 1≤i≠j≤k, where e(Vi∪Vj) denotes the number of edges with both ends in Vi∪Vj? In this paper, we solve this problem asymptotically by showing that f(k,m)≤m/(k−1)+o(m). We also show that V(G) can be partitioned into V1,…,Vk such that e(Vi∪Vj)≤4m/k2+4Δ/k+o(m) for 1≤i≠j≤k, where Δ denotes the maximum degree of G. This confirms a conjecture of Bollobas and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017

The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet, we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs and whether asymptotically good linear LTCs with constant query complexity exist. In this paper, we provide a combinatorial characterization of smooth locally testable codes, which are locally testable codes whose associated tester queries every bit of the tested word with equal probability. Our main contribution is a combinatorial property defined on the Tanner graph associated with the code tester (“well-structured tester”). We show that a family of codes is smoothly locally testable if and only if it has a well-structured tester. As a case study we show that the standard tester for the Hadamard code is “well-structured,” giving an alternative proof of the local testability of the Hadamard code, originally proved by (Blum, Luby, Rubinfeld, J. Comput. Syst. Sci. 47 (1993) 549–595) (STOC 1990). Additional connections to the works of (Ben-Sasson, Harsha, Raskhodnikova, SIAM J. Comput 35 (2005) 1–21) (SICOMP 2005) and of (Lachish, Newman and Shapira, Comput Complex 17 (2008) 70–93) are also discussed. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016

In this paper, we prove a local limit theorem for the distribution of the number of triangles in the Erdos-Renyi random graph G(n, p), where is a fixed constant. Our proof is based on bounding the characteristic function of the number of triangles, and uses several different conditioning arguments for handling different ranges of t. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 2016

A classical theorem of Ghouila-Houri from 1960 asserts that every directed graph on $n$ vertices with minimum out-degree and in-degree at least $n/2$ contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph ${\mathcal D}(n,p)$, that is, a directed graph in which every ordered pair $(u,v)$ becomes an arc with probability $p$ independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if $p \gg \log n/\sqrt{n}$, then a.a.s. every subdigraph of ${\mathcal D}(n,p)$ with minimum out-degree and in-degree at least $(1/2 + o(1)) n p$ contains a directed Hamilton cycle. The constant $1/2$ is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs., Comment: 35 pages, 1 figure

Two models of a random digraph on n vertices, D(n; Prob(arc) = p) and D(n; number of arcs = m) are studied. In 1990, Karp for D(n;p) and independently T. Luczak for D(n;m = cn) proved that for c > 1, with probability tending to 1, there is an unique strong component of size of order n. Karp showed, in fact, that the giant component has likely size asymptotic to n 2 , where = (c) is the unique positive root of 1 = e c . In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector n (c), (c) := ( 2 ;c 2 ) and two distinct 2 2 covariance matrices, nB(c) and n B(c) +c( 0 (c)) T ( 0 (c))) . To this end, we introduce and analyze a randomized deletion process which determines the directed (1; 1)-core, the maximal digraph with minimum in-degree and out-degree at least 1. This (1; 1)-core contains all nontrivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the (1; 1)-core, those outside the largest strong component, are of polylog order, thus dwarfed by anticipated uctuations, on the scale of n 1=2 , of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier-based techniques.

We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erd\H{o}s-R\'{e}nyi graph on $n$ nodes and $\lfloor cn \rfloor$ edges. It is shown in Coppersmith et al. ~\cite{Coppersmith2004} that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region $[c/2+0.37613\sqrt{c},c/2+0.58870\sqrt{c}]$ with high probability (w.h.p.) as $n$ increases, for all sufficiently large $c$. In this paper we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval $[c/2+0.47523\sqrt{c},c/2+0.55909\sqrt{c}]$ w.h.p. as $n$ increases, for all sufficiently large $c$. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as $c$ increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value $c/2+0.47523\sqrt{c}$. It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of $1.36000n$ on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of $1.33773n$., Comment: To appear in Random Structures & Algorithms

Long Code testing is a fundamental problem in the area of property testing and hardness of approximation. In this paper, we study how small the soundness s of the Long Code test with perfect completeness can be by using non-adaptive q queries. We show that s = 2q + 3/2q is possible, where q is of the form 2k-1 for any integer k > 2. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 386-406, 2015

Let f be an edge ordering of Kn: a bijection . For an edge , we call f(e) the label of e. An increasing path in Kn is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S(f) be the number of edges in the longest increasing path. Chvatal and Komlos raised the question of estimating m(n): the minimum value of S(f) over all orderings f of Kn. The best known bounds on m(n) are , due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades. In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S(f) often takes its maximum possible value of n – 1 (visiting all of the vertices with an increasing Hamiltonian path). We prove that this occurs with probability at least about 1/ e. We also prove that with probability 1- o(1), there is an increasing path of length at least 0.85 n, suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015

In this paper we determine the threshold for d-collapsibility in the probabilistic model Xdn,p of d-dimensional simplicial complexes. A lower bound for this threshold p=i¾?dn was established in Aronshtam and Linial, Random Struct. Algorithms 46 2015 26-35, and here we show that this is indeed the correct threshold. Namely, for every c>i¾?d, a complex drawn from Xdn,cn is asymptotically almost surely not d-collapsible. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 260-269, 2016

Let denote the complete k-uniform k-partite hypergraph with classes of size t and the complete k-uniform hypergraph of order s. One can show that the Ramsey number for and satisfies when t = so(1) as s ∞. The main part of this paper gives an analogous result for induced Ramsey numbers: Let be an arbitrary k-partite k-uniform hypergraph with classes of size t and an arbitrary k-graph of order s. We use the probabilistic method to show that the induced Ramsey number (i.e. the smallest n for which there exists a hypergraph such that any red/blue coloring of yields either an induced red copy of or an induced blue copy of ) satisfies . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 5–20, 2016

In this paper we analyze the expected time complexity of the auction algorithm for the matching problem on random bipartite graphs. We first prove that if for every non-maximum matching on graph G there exist an augmenting path with a length of at most 2l + 1 then the auction algorithm converges after N i¾? l iterations at most. Then, we prove that the expected time complexity of the auction algorithm for bipartite matching on random graphs with edge probability p=clogNN and c > 1 is ONlog2NlogNp w.h.p. This time complexity is equal to other augmenting path algorithms such as the HK algorithm. Furthermore, we show that the algorithm can be implemented on parallel machines with OlogN processors and shared memory with an expected time complexity of ONlogN. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 384-395, 2016

The paper bounds the number of tessellations with T-shaped vertices on a fixed set of $k$ lines: tessellations are efficiently encoded, and algorithms retrieve them, proving injectivity. This yields existence of a completely random T-tessellation, as defined by Ki\^en Ki\^eu et al., and of its Gibbsian modifications. The combinatorial bound is sharp, but likely pessimistic in typical cases., Comment: 34 pages, third revised version. Introduction sections 2 and 3 have been reorganised. No change in results or method of proof

We consider a random walk Zn1,',ZnK+1∈i¾?K+1 with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor i¾?K2=2K+2 with respect to the case of the classical simple random walk without constraint. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 267-283, 2015

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

The rotor-router model, also known as the Propp machine, is a deterministic process analogous to a random walk on a graph. Instead of distributing tokens to randomly chosen neighbors, the Propp machine deterministically serves the neighbors in a fixed order by associating to each vertex a “rotor-router” pointing to one of its neighbors. This paper investigates the discrepancy at a single vertex between the number of tokens in the rotor-router model and the expected number of tokens in a random walk, for finite graphs in general. We show that the discrepancy is bounded by O (mn) at any time for any initial configuration if the corresponding random walk is lazy and reversible, where n and m denote the numbers of nodes and edges, respectively. For a lower bound, we show examples of graphs and initial configurations for which the discrepancy at a single vertex is Ω(m) at any time (> 0). For some special graphs, namely hypercube skeletons and Johnson graphs, we give a polylogarithmic upper bound, in terms of the number of nodes, for the discrepancy. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,739–761, 2015

A probability measure Pn on the symmetric group S n is said to be record-dependent if P n ( σ ) depends only on the set of records of a permutation σ ∈ S n . A sequence P = ( P n ) n ∈ ℕ of consistent record-dependent measures determines a random order on ℕ. In this paper we describe the extreme elements of the convex set of such P. This problem turns out to be related to the study of asymptotic behavior of permutation-valued growth processes, to random extensions of partial orders, and to the measures on the Young-Fibonacci lattice. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 2014 © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,688–706, 2015

Beautiful formulas are known for the expected cost of random two-dimensional assignment problems, but in higher dimensions even the scaling is not known. In three dimensions and above, the problem has natural “Axial” and “Planar” versions, both of which are NP-hard. For 3-dimensional Axial random assignment instances of size n, the cost scales as Ω(1/ n), and a main result of the present paper is a linear-time algorithm that, with high probability, finds a solution of cost O(n–1+o(1)). For 3-dimensional Planar assignment, the lower bound is Ω(n), and we give a new efficient matching-based algorithm that with high probability returns a solution with cost O(n log n)

Answering in a strong form a question posed by Bollobas and Scott, in this paper we determine the discrepancy between two random k-uniform hypergraphs, up to a constant factor depending solely on k. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 47, 147-162, 2015

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as a black box) to present a combinatorial construction of locally testable codes that match best known parameters. As a consequence, this construction was obtained over sufficiently large fields. In this paper we improve the result of Ben-Sasson and Sudan and show that for \emph{any} linear codes the associated tensor products are locally testable. Consequently, the construction of Meir can be taken over any field, including the binary field. Moreover, a combination of our result with the result of Spielman (IEEE IT, 1996) implies a construction of linear codes (over any field) that combine the following properties: have constant rate and constant relative distance; have blocklength $n$ and testable with $n^{\epsilon}$ queries, for any constant $\epsilon > 0$; linear time encodable and linear-time decodable from a constant fraction of errors. Furthermore, a combination of our result with the result of Guruswami et al. (STOC 2009) implies a similar corollary regarding the list-decodable codes.

We describe and analyse a simple greedy algorithm \2G\ that finds a good 2-matching $M$ in the random graph $G=G_{n,cn}^{\d\geq 3}$ when $c\geq 15$. A 2-matching is a spanning subgraph of maximum degree two and $G$ is drawn uniformly from graphs with vertex set $[n]$, $cn$ edges and minimum degree at least three. By good we mean that $M$ has $O(\log n)$ components. We then use this 2-matching to build a Hamilton cycle in $O(n^{1.5+o(1)})$ time \whp., Companion paper to "On a sparse random graph with minimum degree {three}: Likely Posa's sets are large"

In this paper we extend the loop-erased random walk LERW to the directed hypergraph setting. We then generalize Wilson's algorithm for uniform sampling of spanning trees to directed hypergraphs. In several special cases, this algorithm perfectly samples spanning hypertrees in expected polynomial time. Our main application is to the reachability problem, also known as the directed all-terminal network reliability problem. This classical problem is known to be # P-complete, hence is most likely intractable Ball and Provan, SIAM J Comput 12 1983 777-788. We show that in the case of bi-directed graphs, a conjectured polynomial bound for the expected running time of the generalized Wilson algorithm implies a FPRAS for approximating reachability. Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 201-223, 2014

The classical result of Erdo˝s and R´enyi shows that the random graph G(n,p) experiencessharp phase transition around p = 1n – for any ǫ > 0 and p = 1−ǫn , all connected componentsof G(n,p) are typically of size O ǫ (logn), while for p = 1+ǫn , with high probability there existsa connected component of size linear in n. We provide a very simple proof of this fundamentalresult; in fact, we prove that in the supercritical regime p = 1+ǫn , the random graph G(n,p)contains typically a path of linear length. We also discuss applications of our technique to otherrandom graph models and to positional games. 1 Introduction In their groundbreaking paper [5] from 1960, Paul Erd˝os and Alfr´ed R´enyi made the followingfundamental discovery: the random graph G(n,p) has a remarkable phase transition around theedge probability p(n) = 1n . For any constant ǫ > 0, if p = 1−ǫn , then the random graph G(n,p)has whp 1 all connected components of size at most logarithmic in n, while for p =

Let (C1,C′(*)),(C2,C′(*)),…,(C m,C′(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on-line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on-line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)1/4. This contrasts with the well-known fact that a random m -clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on-line setting above, we also consider an off-line version in which all m clause-pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off-line setting, we show that the two-choice satisfiability threshold for k -SAT for any fixed k coincides with the standard satisfiability threshold for random 2k -SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Delta. Assign to each vertex v of G a list L(v) of colors by choosing each list uniformly at random from all k-subsets of a color set C of size sigma(n). Such a list assignment is called a random (k,C)-list assignment. In this paper, we are interested in determining the asymptotic probability (as n -greater thaninfinity) of the existence of a proper coloring phi of G, such that phi(v)is an element of L(v) for every vertex v of G. We show, for all fixed k and growing n, that if sigma(n)=omega(n1/k2), then the probability that G has such a proper coloring tends to 1 as n -greater thaninfinity. A similar result for complete graphs is also obtained: if sigma(n)greater than= 1. 223n and L is a random (3,C)-list assignment for the complete graph K-n on n vertices, then the probability that K-n has a proper coloring with colors from the random lists tends to 1 as n -greater than infinity

Let $t$ be a rooted tree and $n_i(t)$ the number of nodes in $t$ having $i$ children. The degree sequence $(n_i(t),i\geq 0)$ of $t$ satisfies $\sum_{i\ge 0} n_i(t)=1+\sum_{i\ge 0} in_i(t)=|t|$, where $|t|$ denotes the number of nodes in $t$. In this paper, we consider trees sampled uniformly among all trees having the same degree sequence $\ds$; we write $`P_\ds$ for the corresponding distribution. Let $\ds(\kappa)=(n_i(\kappa),i\geq 0)$ be a list of degree sequences indexed by $\kappa$ corresponding to trees with size $\nk\to+\infty$. We show that under some simple and natural hypotheses on $(\ds(\kappa),\kappa>0)$ the trees sampled under $`P_{\ds(\kappa)}$ converge to the Brownian continuum random tree after normalisation by $\nk^{1/2}$. Some applications concerning Galton--Watson trees and coalescence processes are provided.

Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well-studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all d -regular graphs with n vertices. We show that with probability 1 - o(1) the push model broadcasts the message to all nodes within (1 + o(1))Cd lnn rounds, where Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo-random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + o(1))Clnn with probability 1 - o(1), where . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

We consider the simple random walk on a random d -regular graph with n vertices, and investigate percolative properties of the set of vertices not visited by the walk until time , where u > 0 is a fixed positive parameter. It was shown in Cerný et al., (Ann Inst Henri Poincare Probab Stat 47 (2011) 929–968) that this so-called vacant set exhibits a phase transition at u = u⋆: there is a giant component if u u⋆. In this paper we show the existence of a critical window of size n-1/3 around u⋆. In this window the size of the largest cluster is of order n2/3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

We study resilient functions and exposure-resilient functions in the low-entropy regime. A resilient function (a.k.a. deterministic extractor for oblivious bit-xing sources) maps any distribution on n-bit strings in which k bits are uniformly random and the rest are xed into an output distribution that is close to uniform. With exposure-resilient functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of resilient functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(logk) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random function is a resilient function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random function is a static (resp. adaptive) exposure-resilient function with high probability even if k is as small as a constant (resp. log logn). No explicit exposure-resilient functions achieving these parameters are known.

We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the notion of convergence of dense graph sequences, defined by Lovasz and Szegedy (J. Combin. Theory Ser B 96 (2006) 933–957). We investigate how the limit object evolves under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limit object from its initial state up to the stationary state, which is described in the companion paper (Rath and Szakacs, in press). In our proofs we use the theory of exchangeable arrays, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits subaging. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.

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