In a previous post I wrote about hypergraph complexity, which I encountered in the paper by Conlon, Fox and Zhao . In that same paper, the hypergraph techniques were used to prove a theorem on the existence of arithmetic progressions. In this post, I want to discuss what arithmetic progressions have to do with graphs, which will perhaps give an indication of why the hypergraph approach is useful. To recap, here is the definition of a hypergraph:
Definition 1. Let be a finite set and a positive integer. Define to be the set of all -element subsets of . An –uniform hypergraph on is defined to be any subset .
Note that the usual definition of a graph corresponds to the case in the above definition. One could picture an -uniform hypergraph as a normal graph, if we require that an edge between exists if and only if there is an edge (in the usual sense of a graph) between and for , plus an edge between and .
Using graphs in the context of arithmetic progressions goes back (at least) to the paper of Ruzsa and Szemeredi . In this, they show that the triangle removal lemma implies Roth’s theorem. For this, I am going to follow the discussion in the book . Consider the following theorem of Ajtai and Szemeredi [3, p23]:
Theorem 2. Let . For there exists an such that if and , then there exist , , for some integer .
Getting from Theorem 2 to Roth’s theorem is not hard. Define by letting if , where we assume is some set of integers with density. We assume that is large enough so that has a density of in . We can see this as a graph with the vertices given by , or we can consider as a grid. In the latter case, the “lower left” (under the diagonal) part of the grid contains all possible differences a subset of could generate, and hence each element of must be represented. We will now try to minimise the occurrences of elements of , in order to be able to apply Theorem 2. Looking at one half of the grid (the easiest thing is to draw a small one of your own), we see that 1 occurs times, 2 occurs times, and so on. Clearly then, if we want to minimise the elements of , they must occur as the largest numbers available in the grid. The number of occurrences is then at least (approximately), which means we have occurrences of in the worst-case scenario. This means that we can apply the Ajtai-Szemeredi theorem.
Another way of using graphs for 3-arithmetic progressions is to consider tripartite graphs. For that, we will need the following:
Theorem 3.  (Triangle removal lemma for tripartite graphs) Let be finite non-empty sets of vertices, and let be a tripartite graph on these sets of vertices, thus for . Suppose that the number of triangles in this graph does not exceed for some . Then there exists a graph which contains no triangle whatsoever, and such that for .
In this case, denotes a quantity that is bounded in magnitude by , where as . The following discussion is similar to that in https://yufeizhao.wordpress.com/2012/09/07/graph-regularity/.
Now, suppose that is a subset of so that . Suppose we have three elements of . Is there a way of describing these elements that will only be possible if they are in arithmetic progression, in terms of general integers? Of course, one way to do so would be to say that if are all in , we have a 3AP. However, if we want to use the Triangle Removal Lemma and specifically tripartite graphs, we should use 3 quantities to describe a progressions. It is quick to check that if we have integers such that
are all in , we have a 3AP. Suppose now we pick sets
Consider three disjoint vertex sets , each of cardinality , with the vertices of each labelled as . The important thing about these sets is that the difference (as follows) will let us recover all elements of . Let us connect a vertex and if , and if , and and if . (Check that this representation captures all three APs, and no more.)
We now show how the triangle lemma implies Roth’s theorem. We let our graph be constructed from for some , and assume that . Also assume that contains no non-trivial arithmetic progressions. What does this mean for the tripartite graph? Especially, how many triangles does our graph contain? Since there are no non-trivial arithmetic progressions, we must have
From this, we can easily see that if we pick , such that , we can set to satisfy the above equations and obtain a triangle. How many ways are there to do this? Given some , we can pick , and . We therefore look at all triples of the form for , . Given that , we should get at least triangles. But how do we apply the triangle removal lemma here? The form it is in does not immediately lend itself to our problem. Let us rephrase it as follows.
Triangle Removal Lemma (2). For each there exists some such that if removing edges does not make the graph triangle-free, then the graph must have more than triangles.
This gives us enough for Roth’s theorem. We have constructed our triangles in a very specific way, so that we know they are the only triangles in the graph, and they do not share any edges. Given the lower bound on the number of triangles in the graph from above, this means that we will need to remove at least edges to make the graph triangle-free. Therefore, removing edges will not make the graph triangle-free, where is slightly smaller than . We must then have some such that the graph contains at least triangles. This is impossible however, since it is easily shown that the upper bound on the number of triangles is also . For large enough, we have a contradiction.
What is the real essence of this proof? It lies in the fact that to have a lot of triangles in such a graph, we would expect many of them to share edgea. This is why we can remove fewer edges than there are triangles in order to make the graph triangle-free. Since the set has density, we know that there will be a significant number of triangles, but not too many, since they have to be disjoint.
- David Conlon, Jacob Fox and Yufei Zhao: A relative Szemeredi theorem, GAFA Vol.25 (2015)
- Ruzsa and Szemeredi: Triple systems with no six points carrying three triangles, Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18 (1978): 939-945.
- Terence Tao: A variant of the hypergraph removal lemma, Journal of combinatorial theory, Series A 113.7 (2006): 1257-1280.
- Fan Chung Graham: The Combinatorics of Patterns in Subsets and Graphs, 2004. https://www.math.ucsd.edu/~fan/teach/262/notes/steve/262_book.pdf