The set-coloring Ramsey number is defined to be the minimum such that if each edge of the complete graph is assigned a set of colors from , then one of the colors contains a monochromatic clique of size . The case is the usual -color Ramsey number, and the case was studied by Erdős, Hajnal and Rado in 1965, and by Erdős and Szemerédi in 1972. The first significant results for general were obtained only recently, by Conlon, Fox, He, Mubayi, Suk and Verstraëte, who showed that if is bounded away from 0 and 1. In the range , however, their upper and lower bounds diverge significantly. In this note we introduce a new (random) coloring, and use it to determine up to polylogarithmic factors in the exponent for essentially all , , and .

We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood growth. In particular, in graphs with subexponential neighborhood growth like , our algorithm achieves linear running time as long as Gibbs sampling is rapidly mixing. As concrete applications, we obtain the currently best perfect samplers for colorings and for monomer-dimer models in such graphs.

A probability measure on the subsets of the edge set of a graph is a 1 probability measure (1-ipm) on if events determined by edge sets that are at graph distance at least 1 apart in are independent. Given a 1-ipm , denote by the associated random graph model. Let denote the collection of 1-ipms on for which each edge is included in with probability at least . For , Balister and Bollobás asked for the value of the least such that for all  >  and all , almost surely contains an infinite component. In this paper, we significantly improve previous lower bounds on . We also determine the 1-independent critical probability for the emergence of long paths on the line and ladder lattices. Finally, for finite graphs we study (), the infimum over all of the probability that is connected. We determine () exactly when is a path, a complete graph and a cycle of length at most 5.

We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of color made available to vertices of lower degree to be accordingly lower. One result concerns list coloring and correspondence coloring, while the other concerns fractional coloring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest.

For any set Ω of non-negative integers such that , we consider a random Ω-k-tree G that is uniformly selected from all connected k-trees of (n + k) vertices such that the number of (k + 1)-cliques that contain any fixed k-clique belongs to Ω. We prove that G, scaled by where H is the kth harmonic number and σ  > 0, converges to the continuum random tree . Furthermore, we prove local convergence of the random Ω-k-tree to an infinite but locally finite random Ω-k-tree G.

It is well known that many random graphs with infinite variance degrees are ultra-small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to and , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order precisely when the minimal forward degree d of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.

A wide class of problems in combinatorics, computer science and physics can be described along the following lines. There are a large number of variables ranging over a finite domain that interact through constraints that each bind a few variables and either encourage or discourage certain value combinations. Examples include the -SAT problem or the Ising model. Such models naturally induce a Gibbs measure on the set of assignments, which is characterised by its partition function. The present paper deals with the partition function of problems where the interactions between variables and constraints are induced by a sparse random (hyper)graph. According to physics predictions, a generic recipe called the "replica symmetric cavity method" yields the correct value of the partition function if the underlying model enjoys certain properties [Krzkala et al., PNAS (2007) 10318-10323]. Guided by this conjecture, we prove general sufficient conditions for the success of the cavity method. The proofs are based on a "regularity lemma" for probability measures on sets of the form Ωn for a finite Ω and a large that may be of independent interest. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 694-741, 2016.

In this paper, we introduce a class of random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension , a random walk with an absorbing state is defined which relates to the spectrum of the -dimensional Laplacian for 1 ≤  ≤ . We study an example of random walks on simplicial complexes in the context of a semi-supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 379-405, 2016.