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].     

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.     

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).     

A scaling limit for the length of the longest cycle in a sparse random digraph

We discuss the length of the longest directed cycle in the sparse random digraph , constant. We show that for large there exists a function such that a.s. The function where is a polynomial in . We are only able to explicitly give the values , although we could in principle compute any .     

The height of depth‐weighted random recursive trees

In this paper, we introduce a model of depth‐weighted random recursive trees, created by recursively joining a new leaf to an existing vertex . In this model, the probability of choosing depends on its depth in the tree. In particular, we assume that there is a function such that if has depth then its probability of being chosen is proportional to . We consider the expected value of the diameter of this model as determined by , and for various increasing we find expectations that range from polylogarithmic to linear.     

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.     

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.     

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.     

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.     

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.     

Asymptotics in percolation on high‐girth expanders

We consider supercritical bond percolation on a family of high‐girth ‐regular expanders. The previous study of Alon, Benjamini and Stacey established that its critical probability for the appearance of a linear‐sized (“giant”) component is . Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant and its 2‐core at any . It was further shown in the previous study that the second largest component, at any , has size at most for some . We show that, unlike the situation in the classical Erd?s‐Rényi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size for arbitrarily close to 1. Moreover, as a by‐product of that construction, we answer negatively a question of Benjamini on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, for example, the existence of a linear path.     

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.     

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 .     

Filling the complexity gaps for colouring planar and bounded degree graphs

A colouring of a graph is a function such that for every . A -regular list assignment of is a function with domain such that for every , is a subset of of size . A colouring of respects a -regular list assignment of if for every . A graph is -choosable if for every -regular list assignment of , there exists a colouring of that respects . We may also ask if for a given -regular list assignment of a given graph , there exists a colouring of that respects . This yields the -Regular List Colouring problem. For , we determine a family of classes of planar graphs, such that either -Regular List Colouring is -complete for instances with , or every is -choosable. By using known examples of non--choosable and non--choosable graphs, this enables us to classify the complexity of -Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs, and planar graphs with no -cycles and no -cycles. We also classify the complexity of -Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.     

On Turán problems for Cartesian products of graphs

Let be disjoint sets of sizes and . Let be a family of quadruples, having elements from and from , such that any subset with and contains one of the quadruples. We prove that the smallest size of is as . We also solve asymptotically a more general two‐partite Turán problem for quadruples.     

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 .     

On the discrepancy of random low degree set systems

Motivated by the celebrated Beck‐Fiala conjecture, we consider the random setting where there are n elements and m sets and each element lies in t randomly chosen sets. In this setting, Ezra and Lovett showed an discrepancy bound when n ≤ m and an O(1) bound when n ? m^t. In this paper, we give a tight bound for the entire range of n and m, under a mild assumption that . The result is based on two steps. First, applying the partial coloring method to the case when and using the properties of the random set system we show that the overall discrepancy incurred is at most . Second, we reduce the general case to that of using LP duality and a careful counting argument.     

Polynomial relations between matrices of graphs

We derive a correspondence between the eigenvalues of the adjacency matrix and the signless Laplacian matrix of a graph when is -biregular by using the relation . This motivates asking when it is possible to have for a polynomial, , and matrices associated to a graph . It turns out that, essentially, this can only happen if is either regular or biregular.