The size Ramsey number of short subdivisions of bounded degree graphs

For graphs G and F, write if any coloring of the edges of G with colors yields a monochromatic copy of the graph F. Suppose is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than edges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs.     

Tree decompositions of graphs without large bipartite holes

A recent result of Condon, Kim, Kühn, and Osthus implies that for any , an n‐vertex almost r‐regular graph G has an approximate decomposition into any collections of n‐vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost αn‐regular graph G with any α>0 and a collection of bounded degree trees on at most (1?o(1))n vertices if G does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into n‐vertex trees. Moreover, this implies that for any α>0 and an n‐vertex almost αn‐regular graph G, with high probability, the randomly perturbed graph has an approximate decomposition into all collections of bounded degree trees of size at most (1?o(1))n simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey‐Turán theory and the randomly perturbed graph model.     

Hypergraph coloring up to condensation

Improving a result of Dyer, Frieze and Greenhill [Journal of Combinatorial Theory, Series B, 2015], we determine the q‐colorability threshold in random k‐uniform hypergraphs up to an additive error of , where . The new lower bound on the threshold matches the “condensation phase transition” predicted by statistical physics considerations [Krzakala et al., PNAS 2007].     

Edge‐coloring linear hypergraphs with medium‐sized edges

Motivated by the Erdos?‐Faber‐Lovász (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We show that if the hyper‐edge sizes are bounded between i and inclusive, then there is a list edge coloring using colors. The dependence on n in the upper bound is optimal (up to the value of C_i,?).     

Upper bounds on probability thresholds for asymmetric Ramsey properties

Given two graphs G and H, we investigate for which functions the random graph (the binomial random graph on n vertices with edge probability p) satisfies with probability that every red‐blue‐coloring of its edges contains a red copy of G or a blue copy of H. We prove a general upper bound on the threshold for this property under the assumption that the denser of the two graphs satisfies a certain balancedness condition. Our result partially confirms a conjecture by the first author and Kreuter, and together with earlier lower bound results establishes the exact order of magnitude of the threshold for the case in which G and H are complete graphs of arbitrary size. In our proof we present an alternative to the so‐called deletion method, which was introduced by Rödl and Ruciński in their study of symmetric Ramsey properties of random graphs (i.e. the case G = H), and has been used in many proofs of similar results since then.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 1–28, 2014     

Information percolation and cutoff for the random‐cluster model

We consider the random‐cluster model (RCM) on with parameters p∈(0,1) and q ≥ 1. This is a generalization of the standard bond percolation (with edges open independently with probability p) which is biased by a factor q raised to the number of connected components. We study the well‐known Fortuin‐Kasteleyn (FK)‐dynamics on this model where the update at an edge depends on the global geometry of the system unlike the Glauber heat‐bath dynamics for spin systems, and prove that for all small enough p (depending on the dimension) and any q>1, the FK‐dynamics exhibits the cutoff phenomenon at with a window size , where λ_∞ is the large n limit of the spectral gap of the process. Our proof extends the information percolation framework of Lubetzky and Sly to the RCM and also relies on the arguments of Blanca and Sinclair who proved a sharp mixing time bound for the planar version. A key aspect of our proof is the analysis of the effect of a sequence of dependent (across time) Bernoulli percolations extracted from the graphical construction of the dynamics, on how information propagates.     

On induced Ramsey numbers for k‐uniform hypergraphs

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 = s^o(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     

Powers of tight Hamilton cycles in randomly perturbed hypergraphs

For k ≥ 2 and r ≥ 1 such that k + r ≥ 4, we prove that, for any α > 0, there exists ε > 0 such that the union of an n‐vertex k‐graph with minimum codegree and a binomial random k‐graph with on the same vertex set contains the rth power of a tight Hamilton cycle with high probability. This result for r = 1 was first proved by McDowell and Mycroft.     

Fractional clique decompositions of dense graphs

For each , we show that any graph G with minimum degree at least has a fractional K_r‐decomposition. This improves the best previous bounds on the minimum degree required to guarantee a fractional K_r‐decomposition given by Dukes (for small r) and Barber, Kühn, Lo, Montgomery, and Osthus (for large r), giving the first bound that is tight up to the constant multiple of r (seen, for example, by considering Turán graphs). In combination with work by Glock, Kühn, Lo, Montgomery, and Osthus, this shows that, for any graph F with chromatic number , and any , any sufficiently large graph G with minimum degree at least has, subject to some further simple necessary divisibility conditions, an (exact) F‐decomposition.     

Partial resampling to approximate covering integer programs†

We consider column‐sparse covering integer programs, a generalization of set cover. We develop a new rounding scheme based on the partial resampling variant of the Lovász Local Lemma developed by Harris and Srinivasan. This achieves an approximation ratio of , where a_min is the minimum covering constraint and is the maximum ?₁‐norm of any column of the covering matrix A (whose entries are scaled to lie in [0, 1]). With additional constraints on the variable sizes, we get an approximation ratio of (where is the maximum number of nonzero entries in any column of A). These results improve asymptotically over results of Srinivasan and results of Kolliopoulos and Young. We show nearly‐matching lower bounds. We also show that the rounding process leads to negative correlation among the variables.     

Testing convexity of figures under the uniform distribution

We consider the following basic geometric problem: Given , a 2‐dimensional black‐and‐white figure is ?‐ far from convex if it differs in at least an ? fraction of the area from every figure where the black object is convex. How many uniform and independent samples from a figure that is ?‐ far from convex are needed to detect a violation of convexity with constant probability? This question arises in the context of designing property testers for convexity. We show that uniform samples (and the same running time) are necessary and sufficient for detecting a violation of convexity in an ?‐far figure and, equivalently, for testing convexity of figures with 1‐sided error. Our algorithm beats the lower bound by Schmeltz [32] on the number of samples required for learning convex figures under the uniform distribution. It demonstrates that, with uniform samples, we can check if a set is approximately convex much faster than we can find an approximate representation of a convex set.     

Limiting shape of the depth first search tree in an Erdős‐Rényi graph

We show that the profile of the tree constructed by the depth first search algorithm in the giant component of an Erd?s‐Rényi graph with N vertices and connection probability c/N with c > 1 converges to an explicit deterministic shape. This makes it possible to exhibit a long nonintersecting path of length , where ρ_c is the density of the giant component and Li₂ denotes the dilogarithm function.     

An optimal (ϵ,δ)‐randomized approximation scheme for the mean of random variables with bounded relative variance

Randomized approximation algorithms for many #P‐complete problems (such as the partition function of a Gibbs distribution, the volume of a convex body, the permanent of a {0,1}‐matrix, and many others) reduce to creating random variables X₁,X₂,… with finite mean μ and standard deviation σ such that μ is the solution for the problem input, and the relative standard deviation |σ/μ| ≤ c for known c. Under these circumstances, it is known that the number of samples from the {X_i} needed to form an (?,δ)‐approximation that satisfies is at least . We present here an easy to implement (?,δ)‐approximation that uses samples. This achieves the same optimal running time as other estimators, but without the need for extra conditions such as bounds on third or fourth moments.     

Graph limits of random graphs from a subset of connected k‐trees

For any set Ω of non‐negative integers such that , we consider a random Ω‐k‐tree G_n,k 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_n,k, scaled by where H_k 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_∞,k.     

A characterization of constant‐sample testable properties

We characterize the set of properties of Boolean‐valued functions on a finite domain that are testable with a constant number of samples (x,f(x)) with x drawn uniformly at random from . Specifically, we show that a property is testable with a constant number of samples if and only if it is (essentially) a k‐part symmetric property for some constant k, where a property is k‐part symmetric if there is a partition of such that whether satisfies the property is determined solely by the densities of f on . We use this characterization to show that symmetric properties are essentially the only graph properties and affine‐invariant properties that are testable with a constant number of samples and that for every constant , monotonicity of functions on the d‐dimensional hypergrid is testable with a constant number of samples.     

On the threshold problem for Latin boxes

Let m ≤ n ≤ k. An m × n × k 0‐1 array is a Latin box if it contains exactly m n ones, and has at most one 1 in each line. As a special case, Latin boxes in which m = n = k are equivalent to Latin squares. Let be the distribution on m × n × k 0‐1 arrays where each entry is 1 with probability p, independently of the other entries. The threshold question for Latin squares asks when contains a Latin square with high probability. More generally, when does support a Latin box with high probability? Let ε > 0. We give an asymptotically tight answer to this question in the special cases where n = k and , and where n = m and . In both cases, the threshold probability is . This implies threshold results for Latin rectangles and proper edge‐colorings of K_n,n.     

Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs

We show that for every there exists C > 0 such that if then asymptotically almost surely the random graph contains the k^th power of a Hamilton cycle. This determines the threshold for appearance of the square of a Hamilton cycle up to the logarithmic factor, improving a result of Kühn and Osthus. Moreover, our proof provides a randomized quasi‐polynomial algorithm for finding such powers of cycles. Using similar ideas, we also give a randomized quasi‐polynomial algorithm for finding a tight Hamilton cycle in the random k‐uniform hypergraph for . The proofs are based on the absorbing method and follow the strategy of Kühn and Osthus, and Allen et al. The new ingredient is a general Connecting Lemma which allows us to connect tuples of vertices using arbitrary structures at a nearly optimal value of p. Both the Connecting Lemma and its proof, which is based on Janson's inequality and a greedy embedding strategy, might be of independent interest.     

Rainbow structures in locally bounded colorings of graphs

We study approximate decompositions of edge‐colored quasirandom graphs into rainbow spanning structures: an edge‐coloring of a graph is locally ‐bounded if every vertex is incident to at most edges of each color, and is (globally) ‐bounded if every color appears at most times. Our results imply the existence of: (1) approximate decompositions of properly edge‐colored into rainbow almost‐spanning cycles; (2) approximate decompositions of edge‐colored into rainbow Hamilton cycles, provided that the coloring is ‐bounded and locally ‐bounded; and (3) an approximate decomposition into full transversals of any array, provided each symbol appears times in total and only times in each row or column. Apart from the logarithmic factors, these bounds are essentially best possible. We also prove analogues for rainbow ‐factors, where is any fixed graph. Both (1) and (2) imply approximate versions of the Brualdi‐Hollingsworth conjecture on decompositions into rainbow spanning trees.     

Invertibility via distance for noncentered random matrices with continuous distributions

Let A be an n×n random matrix with independent rows R₁(A),…,R_n(A), and assume that for any i ≤ n and any three‐dimensional linear subspace the orthogonal projection of R_i(A) onto F has distribution density satisfying (x∈F) for some constant C₁>0. We show that for any fixed n×n real matrix M we have (1) where C^′>0 is a universal constant. In particular, the above result holds if the rows of A are independent centered log‐concave random vectors with identity covariance matrices. Our method is free from any use of covering arguments, and is principally different from a standard approach involving a decomposition of the unit sphere and coverings, as well as an approach of Sankar‐Spielman‐Teng for noncentered Gaussian matrices.