The celebrated canonical Ramsey theorem of Erdős and Rado implies that for a given graph H, if n is sufficiently large then any colouring of the edges of Kn gives rise to copies of H that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. We are interested in sparse random versions of this result and the threshold at which the random graph G(n,p) inherits the canonical Ramsey properties of Kn. Our main result here pins down this threshold when we focus on colourings that are constrained by some prefixed lists. This result is applied in an accompanying work of the authors on the threshold for the canonical Ramsey property (with no list constraints) in the case that H is an even cycle.

We study the emergence of loose Hamilton cycles in subgraphs of random hypergraphs. Our main result states that the minimum d-degree threshold for loose Hamiltonicity relative to the random k-uniform hypergraph Hk(n, p) coincides with its dense analogue whenever p ≥ n−(k-1)/2+o(1). The value of p is approximately tight for d > (k + 1)/2. This is particularly interesting because the dense threshold itself is not known beyond the cases when d ≥ k - 2.

Given graphs G, H1 and H2, let G→mr(H1, H2) denote the property that in every edge-colouring of G there is a monochromatic copy of H1 or a rainbow copy of H2. The constrained Ramsey number, defined as the minimum n such that Kn→mr(H1, H2), exists if and only if H1 is a star or H2 is a forest. We determine the threshold for the property G(n,p) →mr(H1, H2) when H2 is a forest.

In this work, we study hitting times for the appearance of a spanning structure in the Erdős-Rényi random directed graph processes. Namely, we are concerned with the appearance of an arborescence, a spanning digraph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v. Let D(n, 0), D(n, 1),..., D(n, n(n - 1)) be the random digraph process where for every m ∈ {0,..., n(n - 1)}, D(n, m) is a digraph with vertex set {1,...,n}; D(n, 0) has no arcs and, for 1 ≤ m ≤ n(n - 1), the digraph D(n,m) is obtained by adding an arc to D(n,m - 1), chosen uniformly at random among the not present arcs. In this paper we determine the hitting time for the existence of k arc-disjoint arborescences when k = k(n) ⩽ log n.

If $G$ is a graph and $\vec H$ is an oriented graph, we write $G\to \vec H$ to say that every orientation of the edges of $G$ contains $\vec H$ as a subdigraph. We consider the case in which $G$ is the binomial random graph $G(n,p)$, establishing the threshold $p_{\vec H}=p_{\vec H}(n)$ for the property $G(n,p)\to \vec H$ for the cases in which $\vec H$ is an acyclic orientation of a complete graph or of a cycle.

Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given graph $\Gamma$ to being induced $\mathcal{F}$-free is estimable with a query complexity that depends only on the bounds of the Frieze--Kannan regularity lemma and on a removal lemma for $\mathcal{F}$.

We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices of an edge-colored random graph. More precisely, we show that for $p\gg n^{-1/6}{(\ln n)}^{1/6}$, in any $3$-edge coloring of the random graph $G(n,p)$ we can find three monochromatic trees such that their union covers all vertices. This improves, for three colors, a result of Bucić, Korándi, and Sudakov.

A configuration is a finite set of points in the plane. Two configurations A and B have the same order type if there exists a bijection between them preserving the orientation of every ordered triple. We investigate extremal and probabilistic problems related to configurations in general position. We focus on problems involving forbidden configurations or monotone/hereditary properties. Thus, we typically have a given configuration B and we consider the property of being “B-free”: a configuration A is B-free if no subset of points of A has the same order type as B. We prove a significant bound on the number of B-free N-point configurations contained in the m × m grid [m]2 for arbitrary configurations B. We consider random N-point configurations UN in the unit square, in which each of the N points is chosen uniformly at random and independently of all other points. The above-mentioned enumeration result for B-free configurations in the grid is then used to prove strong bounds for the probability that the random set UN should be B-free for any given B. We also investigate the threshold function N0 = N0(n) for the property that UN should be n-universal, that is, should contain all n-point configurations in general position. As it turns out, N0 = N0(n) is doubly exponential in n; we prove that log log N0 = Θ(n). Our arguments are mostly geometric and combinatorial, with the recent container method playing an important role. Also important for us is how large a grid one needs to consider when representing n-point configurations in general position.

A set $S$ of natural numbers is a Sidon set if all the sums $s_1+s_2$ with $s_1$, $s_2\in S$ and $s_1\leq s_2$ are distinct. Let constants $\alpha>0$ and $0<\delta<1$ be fixed, and let $p_m=\min\{1,\alpha m^{-1+\delta}\}$ for all positive integers $m$. Generate a random set $R\subset {\mathbb N}$ by adding $m$ to $R$ with probability $p_m$, independently for each $m$. We investigate how dense a Sidon set $S$ contained in $R$ can be. Our results show that the answer is qualitatively very different in at least three ranges of $\delta$. We prove quite accurate results for the range $0<\delta\leq2/3$, but only obtain partial results for the range $2/3<\delta\leq1$.

There has been substantial interest in estimating the value of a graph parameter, i.e., of a real function defined on the set of finite graphs, by sampling a randomly chosen substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity q_z=q_z(epsilon) of an estimable parameter z is the size of the random sample required to ensure that the value of z(G) may be estimated within error epsilon with probability at least 2/3. In this paper, we study the sample complexity of estimating two graph parameters associated with a monotone graph property, improving previously known results. To obtain our results, we prove that the vertex set of any graph that satisfies a monotone property P may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of P}. Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest.

The blow-up lemma established by Komlós, Sárközy, and Szemerédi in 1997 is an important tool for the embedding of spanning subgraphs of bounded maximum degree. Here we prove several generalizations of this result concerning the embedding of $a$-arrangeable graphs, where a graph is called $a$-arrangeable if its vertices can be ordered in such a way that the neighbors to the right of any vertex $v$ have at most $a$ neighbors to the left of $v$ in total. Examples of arrangeable graphs include planar graphs and, more generally, graphs without a $K_s$-subdivision for constant $s$. Our main result shows that $a$-arrangeable graphs with maximum degree at most $\sqrt{n}/\log n$ can be embedded into corresponding systems of superregular pairs. This is optimal up to the logarithmic factor. We also present two applications. We prove that any large enough graph $G$ with minimum degree at least $\big(\frac{r-1}{r}+\gamma\big)n$ contains an $F$-factor of every $a$-arrangeable $r$-chromatic graph $F$ with at most $\xi n$ vertices and maximum degree at most $\sqrt{n}/\log n$, as long as $\xi$ is sufficiently small compared to $\gamma/(ar)$. This extends a result of Alon and Yuster [J. Combin. Theory Ser. B, 66 (1996), pp. 269--282]. Moreover, we show that for constant $p$ the random graph $\mathcal{G}(n,p)$ is universal for the class of $a$-arrangeable $n$-vertex graphs $H$ of maximum degree at most $\xi n/\log n$, as long as $\xi$ is sufficiently small compared to $p/a$.

We prove that asymptotically (as $n\to\infty$) almost all graphs with n vertices and $C_dn^{2-\frac{1}{2d}} \log^{\frac{1}{d}} n$ edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs satisfying certain pseudorandom properties. We also prove a counterpart result for random bipartite graphs, where the threshold number of edges is even smaller but the embedding is randomized.

A set A of non-negative integers is called a Sidon set if all the sums a1 + a2, with a1 ≤ a2 and a1, a2 ∊ A, are distinct. One of the best studied problems on Sidon sets is the determination of the maximum possible size F(n) of a Sidon subset of [n] = {0, 1, …, n − 1}. Thanks to results of Chowla, Erdős and Turán from the 1940s, it is known that F(n) = (1 + o(1))√n. In this paper we study Sidon subsets of sparse random sets of integers, replacing the ‘dense environment’ [n] by a sparse, random subset R of [n], and ask how large a subset S ⊂ R can be, if we require that S should be a Sidon set. Let R = [n]m be a random subset of [n] of cardinality m = m(n), with all the subsets of [n] equiprobable. We investigate the random variable F([n]m) = max |S|, where the maximum is taken over all Sidon subsets S ⊂ [n]m, and obtain quite precise information on F([n]m) for the whole range of m. An abridged version of our results states as follows. Let 0 < a < 1 be a fixed constant and suppose m = m(n) = (1 + o(1))na. We show that there is a constant b = b(a) such that, almost surely, we have F([n]m) = nb+o(1). As it turns out, the function b = b(a) is a continuous, piecewise linear function of a that is non-differentiable at two points: a = 1/3 and a = 2/3. Somewhat surprisingly, between those two points, the function b = b(a) is constant.

There has been great interest in deciding whether a combinatorial structure satisfies some property, or in estimating the value of some numerical function associated with this combinatorial structure, by considering only a randomly chosen substructure of sufficiently large, but constant size. These problems are called property testing and parameter testing, where a property or parameter is said to be testable if it can be estimated accurately in this way. The algorithmic appeal is evident, as, conditional on sampling, this leads to reliable constant-time randomized estimators. Our paper addresses property testing and parameter testing for permutations in a subpermutation perspective; more precisely, we investigate permutation properties and parameters that can be well-approximated based on randomly chosen subpermutations of much smaller size. In this context, we give a permutation counterpart of a famous result by Alon and Shapira [6] stating that every hereditary graph property is testable. Moreover, we develop a theory of convergence of permutation sequences, which is used to characterize testable permutation parameters along the lines of the work of Borgs et al. [12] in the case of graphs. This theory is interesting for its own sake, as it describes the closure of the set of all permutations as a special class of Lebesgue measurable functions in [0, 1]2, which in turn may be used to define a new model of random permutations.

Query optimization that involves expensive predicates has received considerable attention in the database community. Typically, the output to a database query is a set of tuples that satisfy certain conditions, and, with expensive predicates, these conditions may be computationally costly to verify. In the simplest case, when the query looks for the set of tuples that simultaneously satisfy k expensive predicates, the problem reduces to ordering the evaluation of the predicates so as to minimize the time to output the set of tuples comprising the answer to the query. We study different cases of the problem: the sequential case, in which a single processor is available to evaluate the predicates, and the distributed case, in which there are k processors available, each dedicated to a different attribute (column) of the database, and there is no communication cost between the processors.

We present a deterministic algorithm ${\cal A}$ that, in O(m 2 ) time, verifies whether a given m by m bipartite graph G is regular, in the sense of Szemerédi [Regular partitions of graphs, in Problèmes Combinatoires et Théorie des Graphes (Orsay, 1976), Colloques Internationaux CNRS 260, CNRS, Paris, 1978, pp. 399-401]. In the case in which G is not regular enough, our algorithm outputs a witness to this irregularity. Algorithm ${\cal A}$ may be used as a subroutine in an algorithm that finds an $\varepsilon$-regular partition of a given n-vertex graph $\Gamma$ in time O(n 2 ). This time complexity is optimal, up to a constant factor, and improves upon the bound O(M(n)), proved by Alon et al. [The algorithmic aspects of the regularity lemma, J. Algorithms, 16 (1994), pp. 80-109], where M(n)=O(n 2.376 ) is the time required to square a 0--1 matrix over the integers. Our approach is elementary, except that it makes use of linear-sized expanders to accomplish a suitable form of deterministic sampling.

For any positive integers r and n, let H(r,n) denote the family of graphs on n vertices with maximum degree r, and let H(r,n,n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r,n)-universal graph must have /spl Omega/(n/sup 2-2/r/) edges. On the other hand, for any n/spl ges/n/sub 0/(r), we explicitly construct H(r,n)-universal graphs G and /spl Lambda/ on n and 2n vertices, and with O(n/sup 2-/spl Omega//(1/r log r)) and O(n/sup 2-1/r/ log/sup 1/r/ n) edges, respectively, such that we can efficiently find a copy of any H /spl epsiv/ H (r,n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G=G(n,n,p), with p=cn/sup -1/2r/ log/sup 1/2r/ n is fault-tolerant; for a large enough constant c, even after deleting any /spl alpha/-fraction of the edges of G, the resulting graph is still H(r,/spl alpha/(/spl alpha/)n,/spl alpha/(/spl alpha/)n)-universal for some /spl alpha/: [0,1)/spl rarr/(0,1].