The thresholds for diameter 2 in random Cayley graphs

Given a group G, the model denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any and any family of groups G_k of order n_k for which , a graph with high probability has diameter at most 2 if and with high probability has diameter greater than 2 if . We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erd?s‐Renyi random graphs. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 218–235, 2014     

Rainbow hamilton cycles in random graphs

One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erd?s‐Rényi random graph G_n,p is around . Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of G_n,p are randomly colored from a set of (1 + o(1))n colors, with , we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014     

On MAXCUT in strictly supercritical random graphs,and coloring of random graphs and random tournaments

We use a theorem by Ding, Lubetzky, and Peres describing the structure of the giant component of random graphs in the strictly supercritical regime, in order to determine the typical size of MAXCUT of in terms of ɛ. We then apply this result to prove the following conjecture by Frieze and Pegden. For every , there exists such that w.h.p. is not homomorphic to the cycle on vertices. We also consider the coloring properties of biased random tournaments. A p‐random tournament on n vertices is obtained from the transitive tournament by reversing each edge independently with probability p. We show that for the chromatic number of a p‐random tournament behaves similarly to that of a random graph with the same edge probability. To treat the case we use the aforementioned result on MAXCUT and show that in fact w.h.p. one needs to reverse edges to make it 2‐colorable.     

On random k‐out subgraphs of large graphs

We consider random subgraphs of a fixed graph with large minimum degree. We fix a positive integer k and let G_k be the random subgraph where each independently chooses k random neighbors, making kn edges in all. When the minimum degree then G_k is k‐connected w.h.p. for ; Hamiltonian for k sufficiently large. When , then G_k has a cycle of length for . By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function (or ) where . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017     

The diamond‐free process

Let denote the diamond graph, formed by removing an edge from the complete graph K₄. We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of . We show that, with probability tending to 1 as , the final size of the graph produced is . Our analysis also suggests that the graph produced after i edges are added resembles the uniform random graph, with the additional condition that the edges which do not lie on triangles form a random‐looking subgraph. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 513–551, 2014     

Minimum spanning acycle and lifetime of persistent homology in the Linial–Meshulam process

This paper studies a higher dimensional generalization of Frieze's ‐limit theorem on the d‐Linial–Meshulam process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in . © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 315–340, 2017     

And/or trees: A local limit point of view

We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say , and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees , the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).     

The size of the giant high‐order component in random hypergraphs

The phase transition in the size of the giant component in random graphs is one of the most well‐studied phenomena in random graph theory. For hypergraphs, there are many possible generalizations of the notion of a connected component. We consider the following: two j‐sets (sets of j vertices) are j‐connected if there is a walk of edges between them such that two consecutive edges intersect in at least j vertices. A hypergraph is j‐connected if all j‐sets are pairwise j‐connected. In this paper, we determine the asymptotic size of the unique giant j‐connected component in random k‐uniform hypergraphs for any and .     

Coloring graphs from random lists of fixed size

Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Δ. 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 of size . Such a list assignment is called a random ‐list assignment. In this paper, we are interested in determining the asymptotic probability (as ) of the existence of a proper coloring ? of G, such that for every vertex v of G. We show, for all fixed k and growing n, that if , then the probability that G has such a proper coloring tends to 1 as . A similar result for complete graphs is also obtained: if and L is a random ‐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 .Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 317‐327, 2014     

Hypergraph limits: A regularity approach

A sequence of k‐uniform hypergraphs is convergent if the sequence of homomorphism densities converges for every k‐uniform hypergraph F. For graphs, Lovász and Szegedy showed that every convergent sequence has a limit in the form of a symmetric measurable function . For hypergraphs, analogous limits were constructed by Elek and Szegedy using ultraproducts. These limits had also been studied earlier by Hoover, Aldous, and Kallenberg in the setting of exchangeable random arrays. In this paper, we give a new proof and construction of hypergraph limits. Our approach is inspired by the original approach of Lovász and Szegedy, with the key ingredient being a weak Frieze‐Kannan type regularity lemma. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 205–226, 2015     

Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs

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 ? 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 and c > 1 is 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 processors and shared memory with an expected time complexity of . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 384–395, 2016     

Eigenvalue confinement and spectral gap for random simplicial complexes

We consider the adjacency operator of the Linial‐Meshulam model for random simplicial complexes on n vertices, where each d‐cell is added independently with probability p to the complete ‐skeleton. Under the assumption , we prove that the spectral gap between the smallest eigenvalues and the remaining eigenvalues is with high probability. This estimate follows from a more general result on eigenvalue confinement. In addition, we prove that the global distribution of the eigenvalues is asymptotically given by the semicircle law. The main ingredient of the proof is a Füredi‐Komlós‐type argument for random simplicial complexes, which may be regarded as sparse random matrix models with dependent entries. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 506–537, 2017     

Inside the critical window for cohomology of random k‐complexes

We prove sharper versions of theorems of Linial–Meshulam and Meshulam–Wallach which describe the behavior for ‐cohomology of a random k‐dimensional simplicial complex within a narrow transition window. In particular, we show that if Y is a random k‐dimensional simplicial complex with each k‐simplex appearing i.i.d. with probability with and fixed, then the dimension of cohomology is asymptotically Poisson distributed with mean . In the k = 2 case we also prove that in an accompanying growth process, with high probability, vanishes exactly at the moment when the last ‐simplex gets covered by a k‐simplex, a higher‐dimensional analogue of a “stopping time” theorem about connectivity of random graphs due to Bollobás and Thomason. Random Struct. Alg., 2015 © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 102–124, 2016     

Structure of random 312‐avoiding permutations

We evaluate the probabilities of various events under the uniform distribution on the set of 312‐avoiding permutations of . We derive exact formulas for the probability that the i^th element of a random permutation is a specific value less than i, and for joint probabilities of two such events. In addition, we obtain asymptotic approximations to these probabilities for large N when the elements are not close to the boundaries or to each other. We also evaluate the probability that the graph of a random 312‐avoiding permutation has k specified decreasing points, and we show that for large N the points below the diagonal look like trajectories of a random walk. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 49, 599–631, 2016     

Tight Hamilton cycles in random hypergraphs

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r‐uniform hypergraph with edge probability for every . This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374–385), who used a second moment method to show that tight Hamilton cycles exist even for where arbitrary slowly, and for . The method we develop for proving our result applies to related problems as well. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446–465, 2015     

Group representations that resist random sampling

We show that there exists a family of groups G_n and nontrivial irreducible representations ρ_n such that, for any constant t, the average of ρ_n over t uniformly random elements has operator norm 1 with probability approaching 1 as . More quantitatively, we show that there exist families of finite groups for which random elements are required to bound the norm of a typical representation below 1. This settles a conjecture of A. Wigderson. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 605–614, 2015     

Finding Adam in random growing trees

We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least , the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in , and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in . We conclude the paper with several open problems. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 158–172, 2017     

First passage percolation and escape strategies

Consider first passage percolation on with passage times given by i.i.d. random variables with common distribution F. Let be the time from u to v for a path π and the minimal time among all paths from u to v. We ask whether or not there exist points and a semi‐infinite path such that for all n. Necessary and sufficient conditions on F are given for this to occur. When the support of F is unbounded, we also obtain results on the number of edges with large passage time used by geodesics. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 414–423, 2015     

Maximum‐size antichains in random set‐systems

We show that, for , the largest set in a p‐random sub‐family of the power set of containing no k‐chain has size with high probability. This confirms a conjecture of Osthus. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 308–321, 2016     

The diameter of inhomogeneous random graphs

In this paper, we study the diameter of inhomogeneous random graphs that are induced by irreducible kernels . The kernels we consider act on separable metric spaces and are almost everywhere continuous. We generalize results known for the Erdős–Rényi model G(n, p) for several ranges of p. We find upper and lower bounds for the diameter of in terms of the expansion factor and two explicit constants that depend on the behavior of the kernel over partitions of the metric space.