On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

On percolation and ‐hardness

The edge‐percolation and vertex‐percolation random graph models start with an arbitrary graph G, and randomly delete edges or vertices of G with some fixed probability. We study the computational complexity of problems whose inputs are obtained by applying percolation to worst‐case instances. Specifically, we show that a number of classical ‐hard problems on graphs remain essentially as hard on percolated instances as they are in the worst‐case (assuming ). We also prove hardness results for other ‐hard problems such as Constraint Satisfaction Problems and Subset‐Sum, with suitable definitions of random deletions. Along the way, we establish that for any given graph G the independence number and the chromatic number are robust to percolation in the following sense. Given a graph G, let be the graph obtained by randomly deleting edges of G with some probability . We show that if is small, then remains small with probability at least 0.99. Similarly, we show that if is large, then remains large with probability at least 0.99. We believe these results are of independent interest.     

On polynomial approximations to AC

Classical approximation results show that any circuit of size and depth has an ‐error probabilistic polynomial over the reals of degree . We improve this upper bound to , which is much better for small values of . We then use this result to show that ‐wise independence fools circuits of size and depth up to error at most , improving on Tal's strengthening of Braverman's result that ‐wise independence suffices. To our knowledge, this is the first PRG construction for that achieves optimal dependence on the error . We also prove lower bounds on the best polynomial approximations to . We show that any polynomial approximating the function on bits to a small constant error must have degree at least . This result improves exponentially on a result of Meka, Nguyen, and Vu (Theory Comput. 2016).     

Phase transitions in graphs on orientable surfaces

Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd?s‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.     

Swendsen‐Wang algorithm on the mean‐field Potts model

We study the q‐state ferromagnetic Potts model on the n‐vertex complete graph known as the mean‐field (Curie‐Weiss) model. We analyze the Swendsen‐Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single‐site Glauber dynamics. Long et al. studied the case q = 2, the Swendsen‐Wang algorithm for the mean‐field ferromagnetic Ising model, and showed that the mixing time satisfies: (i) for , (ii) for , (iii) for , where β_c is the critical temperature for the ordered/disordered phase transition. In contrast, for there are two critical temperatures that are relevant. We prove that the mixing time of the Swendsen‐Wang algorithm for the ferromagnetic Potts model on the n‐vertex complete graph satisfies: (i) for , (ii) for , (iii) for , and (iv) for . These results complement refined results of Cuff et al. on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.     

Random perfect graphs

We investigate the asymptotic structure of a random perfect graph P_n sampled uniformly from the set of perfect graphs on vertex set . Our approach is based on the result of Prömel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly. We show that the distribution of the maximum of the stability number and clique number is close to a concentrated distribution L(n) which plays an important role in our generation method. We also prove that the probability that P_n contains any given graph H as an induced subgraph is asymptotically 0 or or 1. Further we show that almost all perfect graphs are 2‐clique‐colorable, improving a result of Bacsó et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity equal to their minimum degree; they are almost all in class one (edge‐colorable using Δ colors, where Δ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphon .     

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.     

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.     

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.     

Counting restricted orientations of random graphs

We count orientations of avoiding certain classes of oriented graphs. In particular, we study , the number of orientations of the binomial random graph in which every copy of is transitive, and , the number of orientations of containing no strongly connected copy of . We give the correct order of growth of and up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota, and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.     

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.     

Diameter in ultra‐small scale‐free random graphs

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^{?(τ ? 1)} 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_fwd 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.     

Finding cliques using few probes

Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random from (and hence is likely to have a clique of size roughly ), then for every δ<2 and constant ?, there is an α<2 (that may depend on δ and ?) such that no algorithm that makes n^δ probes in ? rounds is likely (over the choice of the random graph) to output a clique of size larger than .     

Chromatic thresholds in sparse random graphs

The chromatic threshold of a graph H with respect to the random graph G (n, p ) is the infimum over d > 0 such that the following holds with high probability: the family of H‐free graphs with minimum degree has bounded chromatic number. The study of was initiated in 1973 by Erd?s and Simonovits. Recently was determined for all graphs H . It is known that for all fixed , but that typically if Here we study the problem for sparse random graphs. We determine for most functions when , and also for all graphs H with © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 215–236, 2017     

Packing and counting arbitrary Hamilton cycles in random digraphs

We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in (n, p) for nearly optimal p (up to a factor). In particular, we show that given t = (1 ? o(1))np Hamilton cycles C₁,…,C_t, each of which is oriented arbitrarily, a digraph ～(n, p) w.h.p. contains edge disjoint copies of C₁,…,C_t, provided . We also show that given an arbitrarily oriented n‐vertex cycle C, a random digraph ～(n, p) w.h.p. contains (1 ± o(1))n!pⁿ copies of C, provided .     

Packing perfect matchings in random hypergraphs

We introduce a new procedure for generating the binomial random graph/hypergraph models, referred to as online sprinkling. As an illustrative application of this method, we show that for any fixed integer , the binomial ‐uniform random hypergraph contains edge‐disjoint perfect matchings, provided , where is an integer depending only on . Our result for is asymptotically optimal and for is optimal up to the factor. This significantly improves a result of Frieze and Krivelevich.     

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.     

Arboricity and spanning‐tree packing in random graphs

We study the arboricity and the maximum number of edge‐disjoint spanning trees of the classical random graph . For all , we show that, with high probability, is precisely the minimum of and , where is the minimum degree of the graph and denotes the number of edges. Moreover, we explicitly determine a sharp threshold value for such that the following holds. Above this threshold, equals and equals . Below this threshold, equals , and we give a two‐value concentration result for the arboricity in that range. Finally, we include a stronger version of these results in the context of the random graph process where the edges are randomly added one by one. A direct application of our result gives a sharp threshold for the maximum load being at most in the two‐choice load balancing problem, where .