A note on the existence of fractional f-factors in random graphs

Let G=Gn,p be a binomial random graph with n vertices and edge probability p=p(n),and f be a nonnegative integer-valued function defined on V(G) such that 0a≤f(x)≤bnp-2np ㏒n for every x ∈V(G). An fractional f-indicator function is an function h that assigns to each edge of a graph G a number h(e) in [0,1] so that for each vertex x,we have dh G(x)=f(x),where dh G(x) = x∈e h(e) is the fractional degree of x in G. Set Eh = {e:e ∈E(G) and h(e)=0}.If Gh is a spanning subgraph of G such that E(Gh)=Eh,then Gh is called an fractional f-factor of G. In this paper,we prove that for any binomial random graph Gn,p with p≥n-23,almost surely Gn,p contains an fractional f-factor.     

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     

Psi‐series method for equality of random trees and quadratic convolution recurrences

An unusual and surprising expansion of the form as , is derived for the probability p_n that two randomly chosen binary search trees are identical (in shape, hence in labels of all corresponding nodes). A quantity arising in the analysis of phylogenetic trees is also proved to have a similar asymptotic expansion. Our method of proof is new in the literature of discrete probability and the analysis of algorithms, and it is based on the logarithmic psi‐series expansions for nonlinear differential equations. Such an approach is very general and applicable to many other problems involving nonlinear differential equations; many examples are discussed in this article and several attractive phenomena are discovered.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 67–108, 2014     

Stability results for random discrete structures

Two years ago, Conlon and Gowers, and Schacht proved general theorems that allow one to transfer a large class of extremal combinatorial results from the deterministic to the probabilistic setting. Even though the two papers solve the same set of long‐standing open problems in probabilistic combinatorics, the methods used in them vary significantly and therefore yield results that are not comparable in certain aspects. In particular, the theorem of Schacht yields stronger probability estimates, whereas the one of Conlon and Gowers also implies random versions of some structural statements such as the famous stability theorem of Erd?s and Simonovits. In this paper, we bridge the gap between these two transference theorems. Building on the approach of Schacht, we prove a general theorem that allows one to transfer deterministic stability results to the probabilistic setting. We then use this theorem to derive several new results, among them a random version of the Erd?s‐Simonovits stability theorem for arbitrary graphs, extending the result of Conlon and Gowers, who proved such a statement for so‐called strictly 2‐balanced graphs. The main new idea, a refined approach to multiple exposure when considering subsets of binomial random sets, may be of independent interest.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 269‐289, 2014     

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     

Large deviations for hitting times of a random walk in random environment on a strip

We consider a random walk in random environment on a strip, which is transient to the right. The random environment is stationary and ergodic. By the constructed enlarged random environment which was first introduced by Goldsheid （2008）, we obtain the large deviations conditioned on the environment （in the quenched case） for the hitting times of the random walk.