You are currently browsing the tag archive for the ‘counterexamples’ tag.

This month I have been at the Institute for Advanced Study, participating in their semester program on additive combinatorics. Today I gave a talk on my forthcoming paper with Tim Austin on the property testing of graphs and hypergraphs (I hope to make a preprint available here soon). There has been an immense amount of progress on these topics recently, based in large part on the graph and hypergraph regularity lemmas; but we have discovered some surprising subtleties regarding these results, namely a distinction between undirected and directed graphs, between graphs and hypergraphs, between partite hypergraphs and non-partite hypergraphs, and between monotone hypergraph properties and hereditary ones.

For simplicity let us first work with (uncoloured, undirected, loop-free) graphs G = (V,E). In the subject of graph property testing, one is given a property ${\mathcal P}$ which any given graph G may or may not have. For example, ${\mathcal P}$ could be one of the following properties:

1. G is planar.
2. G is four-colourable.
3. G has a number of edges equal to a power of two.
4. G contains no triangles.
5. G is bipartite.
6. G is empty.
7. G is a complete bipartite graph.

We assume that the labeling of the graph is irrelevant. More precisely, we assume that whenever two graphs G, G’ are isomorphic, that G satisfies ${\mathcal P}$ if and only if G’ satisfies ${\mathcal P}$. For instance, all seven of the graph properties listed above are invariant under graph isomorphism.

We shall think of G as being very large (so $|V|$ is large) and dense (so $|E| \sim |V|^2$). We are interested in obtaining some sort of test that can answer the question “does G satisfy ${\mathcal P}$?” with reasonable speed and reasonable accuracy. By “reasonable speed”, we mean that we will only make a bounded number of queries about the graph, i.e. we only look at a bounded number k of distinct vertices in V (selected at random) and base our test purely on how these vertices are connected to each other in E. (We will always assume that the number of vertices in V is at least k.) By “reasonable accuracy”, we will mean that we specify in advance some error tolerance $\varepsilon > 0$ and require the following:

1. (No false negatives) If G indeed satisfies ${\mathcal P}$, then our test will always (correctly) accept G.
2. (Few false positives in the $\varepsilon$-far case) If G fails to satisfy ${\mathcal P}$, and is furthermore $\varepsilon$-far from satisfying ${\mathcal P}$ in the sense that one needs to add or remove at least $\varepsilon |V|^2$ edges in G before ${\mathcal P}$ can be satisfied, then our test will (correctly) reject G with probability at least $\varepsilon$.

When a test with the above properties exists for each given $\varepsilon > 0$ (with the number of queried vertices k being allowed to depend on $\varepsilon$), we say that the graph property ${\mathcal P}$ is testable with one-sided error. (The general notion of property testing was introduced by Rubinfeld and Sudan, and first studied for graph properties by Goldreich, Goldwasser, and Ron; see this web page of Goldreich for further references and discussion.) The rejection probability $\varepsilon$ is not very important in this definition, since if one wants to improve the success rate of the algorithm one can simply run independent trials of that algorithm (selecting fresh random vertices each time) in order to increase the chance that G is correctly rejected. However, it is intuitively clear that one must allow some probability of failure, since one is only inspecting a small portion of the graph and so cannot say with complete certainty whether the entire graph has the property ${\mathcal P}$ or not. For similar reasons, one cannot reasonably demand to have a low false positive rate for all graphs that fail to obey ${\mathcal P}$, since if the graph is only one edge modification away from obeying ${\mathcal P}$, this modification is extremely unlikely to be detected by only querying a small portion of the graph. This explains why we need to restrict attention to graphs that are $\varepsilon$-far from obeying ${\mathcal P}$.

An example should illustrate this definition. Consider for instance property 6 above (the property that G is empty). To test whether a graph is empty, one can perform the following obvious algorithm: take k vertices in G at random and check whether they have any edges at all between them. If they do, then the test of course rejects G as being non-empty, while if they don’t, the test accepts G as being empty. Clearly there are no false negatives in this test, and if k is large enough depending on $\varepsilon$ one can easily see (from the law of large numbers) that we will have few false positives if G is $\varepsilon$-far from being empty (i.e. if it has at least $\varepsilon |V|^2$ vertices). So the property of being empty is testable with one-sided error.

On the other hand, it is intuitively obvious that property 3 (having an number of edges equal to a power of 2) is not testable with one-sided error.

So it is reasonable to ask: what types of graph properties are testable with one-sided error, and which ones are not?