A partition property of order k asks if a graph can be partitioned into k vertex sets of prescribed sizes so that the densities between any pair of sets falls within a prescribed range. This family of properties has been extensively studied in various areas of research ranging from theoretical computer science to statistical physics. Our main result is that every partition property of order k is testable with query complexity poly(k/ɛ). We thus obtain an exponential improvement (in k) over the (1/ɛ)O(k) bound obtained by Goldreich, Goldwasser and Ron in their seminal FOCS 1996 paper. We further prove that our bound is tight in the sense that it cannot be made sub-polynomial in either k or ɛ.

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 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}$.

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.

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.