I’ve just uploaded to the arXiv my joint paper with Tim Austin, “On the testability and repair of hereditary hypergraph properties“, which has been submitted to Random Structures and Algorithms. In this paper we prove some positive and negative results for the testability (and the local repairability) of various properties of directed or undirected graphs and hypergraphs, which can be either monochromatic or multicoloured.

The negative results have already been discussed in a previous posting of mine, so today I will focus on the positive results. The property testing results here are finitary results, but it turns out to be rather convenient to use a certain correspondence principle (the hypergraph version of the Furstenberg correspondence principle) to convert the question into one about exchangeable probability measures on spaces of hypergraphs (i.e. on random hypergraphs whose probability distribution is invariant under exchange of vertices). Such objects are also closely related to the”graphons” and “hypergraphons” that emerge as graph limits, as studied by Lovasz-Szegedy, Elek-Szegedy, and others. Somewhat amusingly, once one does so, it then becomes convenient to keep track of objects indexed by vertex sets and how they are exchanged via the language of category theory, and in particular using the concept of a natural transformation to describe such objects as exchangeable measures, graph colourings, and local modification rules. I will try to sketch out some of these connections, after describing the main positive results.

— Statement of results —

Property testing in graph and hypergraph theory has primarily focused on undirected graphs , where is a set of undirected edges of a finite vertex set V. In this paper, we consider some more general objects than undirected graphs, in increasing order of generality:

*Undirected hypergraphs*of some order k, where is a collection of unordered edges on a vertex set V of order k;*Directed hypergraphs*of some order k, where is a collection of injective maps from the k-element set to V (which should be viewed as directed edges of order k, or*k-edges*for short);*Coloured directed hypergraphs*of some order k, in which is a colouring of all k-edges by some finite palette ;*Multiple coloured directed hypergraphs*of order k, in which is a colouring of j-edges by some component of a palette . We’ll call such hypergraphs*K-hypergraphs*for short. [It is natural, in view of the hypergraph regularity lemma, to consider multiple orders of hypergraphs at once, even if initially one is only interested in hypergraphs of a certain fixed order. For instance, one might be interested in graphs (which are hypergraphs of order 2), but the regularity lemma would then require one to partition the vertices into classes (thus creating a coloured hypergraph of order 1).]

(We also consider a continuous analogue of these concepts, in which the vertex set is a probability space rather than a discrete set, and loops are allowed but for simplicity we will not discuss this generalisation here.)

We now fix a palette K. For any vertex set V, let be the collection of all K-hypergraphs on V. Observe that every injective map induces a *pullback map* , which is contravariant in the sense that for any pair of injections and . Thus one can view K as a contravariant functor from a category of vertex sets to a category of spaces (which we will later identify as a category of sub-Cantor spaces).

We’ll be considering various properties of K-hypergraphs, or *K-properties* for short. Formally, a K-property is an assignment of a collection of K-hypergraphs for each vertex set V; one should view as the collection of K-hypergraphs on V which satisfy the property . We will restrict attention to those properties which are *hereditary*, which means that they are preserved under pullbacks; thus any given pullback map restricts to a map . Thus hereditary properties can also be viewed as contravariant functors.

[Traditionally, hereditary properties are defined as those properties of (hyper)graphs which are preserved under (hyper)graph isomorphism as well as (hyper)graph restriction, but it is not hard to see that the above definition is equivalent.]

For graphs, examples of hereditary properties include that of being complete, of being bipartite, of being planar, of being four-colourable, of being triangle-free, etc.

It is convenient to extend a K-property from finite hypergraphs to infinite ones by declaring an infinite hypergraph to obey if and only if all of its finite induced subhypergraphs obey . With this convention, becomes a closed subspace of (which we give the product topology), and in particular is compact.

We say that a K-property is *locally testable with one-sided error* (or *testable* for short) if one can probabilistically test for this property on large (hyper)graphs by verifying the property on a small random portions of the (hyper)graph. More formally, we say that is testable if for every there exists an N and such that if is a K-hypergraph on a large vertex set V (with ) which N-locally obeys to accuracy in the sense that the restriction of G to a randomly chosen N-element subset obeys with probability , then G itself is -close to obeying in the sense that there is a K-hypergraph such that G and G’ agree on a randomly chosen k-element subset of V with probability at least . [This notion of testability has *one-sided *error because there are no false negatives: if a local portion of G disobeys , then G itself certainly disobeys , since is hereditary. See this web page of Goldreich for more discussion of property testing in general.]

Our first main positive result is:

Theorem 1. Every hereditary K-property is testable.

This result was previously shown by Alon and Shapira for undirected monochromatic graph properties, by Rodl and Schacht for undirected monochromatic hypergraph properties, and by Ishigami for partite hypergraph properties. There is also a substantial body of earlier partial results on property testing of graph and hypergraph properties, and properties of other combinatorial objects, which are too numerous to be listed here. Remarkably, this theorem can be used to prove some results in additive combinatorics, most notably Szemerédi’s theorem on arithmetic progressions; see for instance my Montreal notes for further discussion.

Our other positive results go beyond testability to prove a stronger property, which we have dubbed “local repairability”. This notion, analogous to that of local correctability in the theory of error-correcting codes, takes a bit of notation to define properly. Define a *modification rule *to be a pair , where A is a finite set of vertices, and for each vertex set V, is a map which converts K-hypergraphs on the disjoint union to K-hypergraphs on V; one should view the vertex set A as supplying some “test data” in which to determine how to modify the rest of the hypergraph. We say that the modification rule is *local* if the diagram

commutes for all injections . (Apologies for the clunky diagram; I have had some difficulties with doing advanced LaTeX in wordpress.) Informally, a local modification rule will modify each edge based only on the connectivity of the vertices of that edge with A, and will not care about the precise labels assigned to those vertices. We say that a local modification rule entails a K-property if we have for all vertex sets V.

One can view a local modification rule T as defining a natural transformation from the contravariant functor (which assigns the space to each vertex set V) to the contravariant functor K. (We found it convenient to use the concept of a natural transformation in our paper, and in particular the standard fact that the composition of natural transformations is again a natural transformation, as it allowed us to easily localise or permute the vertex sets one was working on.)

Perhaps an example will illustrate what a “local modification rule” is. Suppose one has a graph G which is nearly complete bipartite, in the sense that one can partition the vertex set V into two vertex sets W and W’, such that at least 99% (say) of the edges between W and W’ lie in G, and at most 1% of the edges within W or within W’ lie in G. We would like to locally modify this graph to one which really is complete bipartite. One way to do this is to select a special vertex a inside V at random. One can then create a modified graph on , defined by partitioning into the vertices connected to a, and the vertices not connected to a, and then forming the complete bipartite graph between and . One can view as the action of a modification rule $(\{1\},T)$ on a pullback of G, where is the map that sends 1 to a and is the identity on . The rule T entails the property of being complete bipartite. Also, observe that if a is chosen randomly, then is close to G in the sense that any edge in G has at least a 95% chance (say) of being an edge in (if V is large enough), and similarly any non-edge in G has at least a 95% chance of being a non-edge of .

We say that a K-property is *locally repairable* if for every there exists , an N, and finite set A such that whenever is a sufficiently large K-hypergraph which N-locally obeys to accuracy , then there exists local modification rule such that if is a random injection, then the colour of any given edge in G will match the same edge in with probability at least , where is the bijection that equals on A and the identity on .

The above definition was quite convoluted, but informally, if a property is locally repairable, then it is possible to probabilistically “repair” with high probability any large hypergraph G on V which “almost” obeys by first selecting a bounded number of random test vertices , and modifying the colour of each edge outside of by looking only at how the vertices of that edge connect with .

Local repairability is stronger than testability. Testability asserts that hypergraphs which nearly obey can be modified to actually obey , but do not specify how to locate this modification; local repairability shows that such a modification can be built using a local modification rule. [Another indication of how repairability is stronger than testability is that we can use the repairability of various properties to deduce Ramsey's theorem, which does not seem to be the case for testability.]

With all this notation, we can state our next three theorems:

Theorem 2. Every undirected graph property is locally repairable.

Theorem 3. Every monotone hypergraph property is locally repairable.

Theorem 4. Every partite hypergraph property is locally repairable.

(There are precise definitions of what it means for a property to be undirected, monotone, or partite, which are given in our paper; but I will not give them here as they are not particularly illuminating.) These hypotheses are close to being sharp; we have counterexamples to local repairability for directed graph properties or undirected hypergraph properties once all assumptions of monotonicity or partiteness are dropped, as discussed in my previous post. I should remark that Theorem 4 is also implicitly present in a paper of Ishigami.

— The correspondence principle —

Our proofs of the above theorems use the correspondence principle between statements concerning finite hypergraphs, and statements concerning exchangeable measures on spaces of infinite hypergraphs (or equivalently, concerning infinite exchangeable random hypergraphs).

The basic way the correspondence principle is invoked is via the following “compactness and contradiction” argument, which also appears in many other places in mathematics (e.g. in PDE):

- Suppose we are trying to prove some asymptotic statement about finite hypergraphs. We assume for contradiction that the claim is false, thus obtaining a sequence of hypergraphs which form increasingly strong counterexamples to that statement. (Typically, the size of these graphs will go to infinity as n goes to infinity.)
- We sample randomly from each of the finite graphs to create a sequence of infinite random graphs , by randomly mapping into and pulling back the graph. (There will be some collisions when multiple integers map to the same vertex, but as the original graph gets larger, these collisions get rarer, so it will actually not make much difference what we do in the case of collisions.) One can view each infinite random graph as describing a Borel probability measure on the Cantor space . This measure is
*exchangeable*, in the sense that it is unchanged if we permute the underlying set of vertices . Informally, this measure describes all the “local” or “statistical” information one can observe about a given hypergraph. - We then exploit the fact that the space of Borel probability measures on a given (standard Borel) space is vaguely sequentially compact, so that (after passing to a subsequence) we can extract a vague limit of the . Since the are the laws of exchangeable random hypergraphs which are increasingly strong counterexamples to the initial statement one is trying to prove, the infinite random hypergraph corresponding to should be a “perfect” counterexample to this statement.
- We then work in the setting of infinite exchangeable random hypergraphs to show that no such perfect counterexamples in fact exist.

Actually, in order to use the concept of a natural transformation effectively, it is convenient not to work with a single probability measure on a single space of hypergraphs, but instead to work with a separate probability measure on for each vertex set V, which is consistent with the pullback maps . One can view as a natural transformation from a trivial functor to the functor , in which we allow morphisms to be probability kernels rather than continuous maps. (A *probability kernel* between two standard Borel spaces is a map which assigns a Borel probability measure P(x) on Y to every point in x in a weakly measurable manner, thus the map is measurable for every Borel set E in Y. One can think of a probability kernel as describing a random function from X to Y.)

By using the above correspondence principle, combined with a structural theorem of Austin for exchangeable random hypergraphs (which is the infinitary analogue of the hypergraph regularity lemma, and also generalises a classical theorem of de Finetti on exchangeable measures; it is closely related to similar results of Aldous and of Kallenberg) one can reformulate the concepts of testability and local repairability of a given K-property in terms of natural transformations on sub-Cantor spaces (closed subspaces of Cantor spaces), where we allow morphisms on these spaces to either be deterministic (functions, possibly continuous), or probabilistic (i.e. probability kernels). The precise formulation is technical (requiring even more notation than just presented, in particular the concept of a *regularised exchangeable recipe* , which is the infinitary analogue of a regularised graph or hypergraph), but roughly speaking, a property is locally repairable if every regularised exchangeable recipe which almost surely obeys can be modified by a deterministically continuous natural transformation to surely obey while only modifying a small number of edges on average, whereas a is testable if every regularised exchangeable recipe with almost surely obeys can be modified by a probabilistically continuous natural transformation (i.e. the morphisms are probability kernels which are continuous in the weak topology) whose output almost surely obeys for each input, and which also only modifying a small number of edges on average.

## 4 comments

Comments feed for this article

21 January, 2008 at 9:14 pm

254A, Lecture 5: Other topological recurrence results « What’s new[...] Remark 4. More generally, one can interpret the theory of graphs and hypergraphs on a vertex set V through the lens of dynamics of actions; I learned this perspective from Balazs Szegedy, and it underlies my paper on the hypergraph correspondence principle, as well as my more recent paper with Tim Austin on hypergraph property testing. [...]

30 August, 2008 at 8:44 am

The correspondence principle and finitary ergodic theory « What’s new[...] it actually implies the k=3 case of Szemerédi’s theorem. (See also my previous blog posts on related topics.) It turns out that this result can be deduced from some infinitary versions of [...]

29 November, 2008 at 9:00 am

254A, Lecture 10: The Furstenberg correspondence principle « What’s new[...] and hypergraphs to the measure theory of exchangeable measures: see this paper of myself, and of myself and Austin, for details. There is also a correspondence principle connecting ergodic convergence theorems with [...]

28 March, 2009 at 12:55 pm

RaiulBaztepoHello!

Very Interesting post! Thank you for such interesting resource!

PS: Sorry for my bad english, I’v just started to learn this language ;)

See you!

Your, Raiul Baztepo