## The first unknown case of polynomial DHJ

In this post I want to discuss a combinatorial problem that is very appealing in its own right, but also important as a potential first step towards solving a central open problem in Ramsey theory. It is the second in a series of three posts (I may add to this number later, but three is what I have written or semi-written so far) that give further details about possible Polymath projects. This one was number 2 in the post in which I first discussed these projects. In that post, I said nothing beyond the fact that the project had close connections with the density Hales-Jewett theorem. Unlike the origin-of-life suggestion, this project is a straightforward mathematical one.

Let me very briefly indicate what the central open problem in Ramsey theory is. The density Hales-Jewett theorem, which has been discussed at great length on this blog, is the assertion that every dense subset of $[k]^n$ contains a combinatorial line (provided that $n$ is large enough in terms of $k$ and the density). This implies Szemerédi’s theorem.

Now there is an amazing generalization of Szemerédi’s theorem, due to Bergelson and Leibman, known as the polynomial Szemerédi’s theorem. This is the following assertion. For any $\delta>0$ and any choice of $k$ polynomials $P_1,\dots,P_k$ with integer coefficients and constant terms equal to zero, there exists $N=N(\delta,P_1,\dots,P_k)$ such that every subset $A\subset\{1,2,\dots,N\}$ of size at least $\delta N$ contains a subset of the form $\{a+P_1(d),a+P_2(d),\dots,a+P_k(d)\}$ with $d\ne 0$. To see that this generalizes Szemerédi’s theorem, just let $P_i(d)=id$ (unless you feel that $(i-1)d$ is more natural).

Another special case of this theorem is when $P_1(d)\equiv 0$ and $P_2(d)=d^2$. Then one is trying to find a subset of the form $\{a,a+d^2\}$, or in other words a pair of elements of $A$ that differ by a perfect square. This was proved independently by Sarkozy and Furstenberg, though my favourite proof is a more recent argument due to Ben Green that follows more closely the general structure of Roth’s proof of Roth’s theorem.

An obvious question now arises: is there a generalization of DHJ that implies both DHJ and the polynomial Szemerédi’s theorem? So far, the answer is no, and that is the central problem I was referring to earlier. However, we do at least know the colouring version: that is, there is a colouring statement that simultaneously generalizes the Hales-Jewett theorem and van der Waerden’s theorem. This is a result of Bergelson and McCutcheon — alternative proofs have been given by Mark Walters (who has the shortest and simplest argument) and Saharon Shelah (who has produced a primitive recursive bound).

A result of this work is that we know what the correct statement of polynomial DHJ ought to be. It is slightly complicated, so first let me give one special case that is already enough to convey the flavour of it.

Conjecture 1. For every $\delta>0$ and every positive integer $k$ there exists $n$ such that if $A$ is any subset of $[k]^{[n]^2}$ of density at least $\delta$, then $A$ contains a combinatorial line such that the wildcard set is of the form $X\times X$ for some subset $X\subset[n]$.

By considering the map $\phi:[k]^{[n]^2}\rightarrow\mathbb{N}$ that takes each element of $[k]^{[n]^2}$ to the sum of all its values, we find that the conjecture above implies the following special case of the polynomial Szemerédi theorem.

Theorem 2. For every $\delta>0$ and every $k$ there exists $N$ such that every subset of $\{1,2,\dots,N\}$ of density at least $\delta$ contains an arithmetic progression of length $k$ whose common difference is a perfect square.

The deduction is not quite trivial, but it is not too hard either. The main reason it holds is that the cardinality of $X\times X$ is a perfect square.

Here is (one version of) the full polynomial density Hales-Jewett conjecture. It is a bit like a set-theoretic equivalent of trying to find $a$ and $x$ such that $a+c_1x+c_2x^2+\dots+c_dx^d$ belongs to a given set whenever $0\leq c_i\leq k$ for every $i$, just as Conjecture 1 resembles Theorem 2.

Conjecture 3. For every $\delta>0$ and every pair of positive integers $k$ and $d$ there exists $n$ such that if $A$ is any subset of $[k]^{[n]}\times[k]^{[n]^2}\times\dots\times[k]^{[n]^d}$ of density at least $\delta$, then $A$ contains a $d$-dimensional combinatorial subspace such that the wildcard sets are of the form $X, X\times X,\dots,X^d$ for some subset $X\subset[n]$ (where $X^j$ is understood to be a subset of the $[k]^{[n]^j}$ that appears in the product).

As far as I am aware, the polynomial version of DHJ is the only interesting statement of the form “Does every dense subset of such and such a structure contain a substructure of such and such a type?” where the answer is not known, even if one asks nothing at all about bounds. (I’m not saying that there are definitely no other interesting purely qualitative unsolved density conjectures, but I can’t think of any. I’d be interested to hear of others.)

One might expect Conjecture 1 to become hard when $k=3$, but it is in fact not known even when $k=2$. On reflection, this is not quite so surprising, since it implies the theorem of Sarkozy and Furstenberg, which is far from trivial. On the other hand, the theorem of Sarkozy and Furstenberg is significantly easier than the full polynomial Szemerédi theorem, so perhaps there is some hope of tackling the $k=2$ case of Conjecture 1.

A small variant of this case is particularly appealing combinatorially, and is what I would actually suggest as a good Polymath project.

Conjecture 4. For every $\delta>0$ there exists $n$ such that if $A$ is any collection of at least $\delta 2^{\binom n2}$ graphs with vertex set $\{1,2,\dots,n\}$, then $A$ contains two distinct graphs $G$ and $H$ such that $G\subset H$ and $H\setminus G$ is a clique.

From this conjecture one can deduce the special case of the polynomial Szemerédi theorem where one is looking for a pair of numbers of the form $\{a,a+\binom d2\}$. (The polynomial $P(d)=\binom d2$ does not have integer coefficients, but that is a minor technicality.) Bergelson and Leibman proved their theorem by first proving the colouring version (the polynomial van der Waerden theorem) and then using general ergodic machinery to deduce the density version. The colouring version followed by a sophisticated induction scheme (which they called PET induction), and in that scheme the polynomial $d(d-1)$ was “easier” than the polynomial $d^2$. Thus, there are two reasons for looking at this question about dense sets of graphs: it has a nice combinatorial formulation that does not require one to understand the terminology connected with the Hales-Jewett theorem, and it ought to be (trivially equivalent to) the easiest unsolved case of polynomial DHJ.

Here is a looser way of stating the conjecture: a dense set of graphs must contain two that differ by a clique. How might one go about proving this?

Here is an approach that doesn’t work, but it is still worth thinking about it in order to get a reasonable understanding of the difficulties of the problem. We can think of Conjecture 4 as a strengthening of Sperner’s theorem: we can reformulate Sperner’s theorem as the assertion that if you have a dense set of graphs, then you can find distinct graphs $G$ and $H$ in your set such that $G\subset H$, and Conjecture 3 adds the requirement that $H\setminus G$ should be a clique. (Of course, if we do not add some such requirement then the resulting statement is not really a statement about graphs at all.)

The “correct” proof of Sperner’s theorem, if we pretend that it is a statement about graphs, proceeds by considering a random ordering of all the edges of the complete graph on $n$ vertices. If $A$ is a dense set of graphs, and if we start with the empty graph and build up to the complete graph by adding random edges one at a time, then the expected number of times we produce a graph in $A$ is equal to $n+1$ times the equal-slices density of $A$ (which can be defined as the probability that a graph $G$ belongs $A$ if you first choose an integer $k$ uniformly at random from the set $\{0,1,\dots,\binom n2\}$ and then choose $G$ with $k$ edges uniformly at random from all such graphs). It is easy to show that if $A$ is dense, then it has equal-slices density greater than $1/(n+1)$, and this completes the proof of Sperner’s theorem.

Can we adapt this idea to prove a properly graph-theoretic version of Sperner’s theorem? If we could find a way of randomly building up a sequence of graphs that started with the empty graph and ended with the complete graph and had the property that any two graphs in the sequence differed by a clique, then we would be in business. However, a moment’s thought shows that that is not even close to being possible: indeed, a union of two cliques cannot be a clique, so even a very short sequence of such graphs does not exist.

But it is not necessary to construct a sequence with such a ridiculously strong property. For example, suppose that one could build a sequence of graphs $G_0\subset G_1\subset\dots\subset G_m$ (where $m=\binom n2$) such that $G_r$ has $r$ edges, and $G_i\setminus G_j$ is a clique whenever $i-j=\binom d2$ for some $d$ (which is clearly a necessary condition). That wouldn’t immediately lead to a proof, but it would be quite encouraging, because if $A$ ever intersected such a sequence densely, then by the polynomial Szemerédi theorem (in fact, this case follows also from the work of Sarkozy and Furstenberg) it would have to contain two graphs that differed by a clique.

Even this property is far too strong, however. For instance, it would require $G_{i+3}\setminus G_i$ to be a triangle for every $i$, and it doesn’t take long to convince oneself that that is impossible.

Nevertheless, these discouraging observations do not completely rule out covering almost all graphs by sequences that are sufficiently rich in clique differences for it to be possible to reduce the problem to a problem about sets of integers. One possible line of enquiry would be to see whether all such proofs can be ruled out. For example, perhaps it is the case that for every chain of graphs $G_1\subset\dots\subset G_r$ one can find a set of at least $r/100$ graphs in the chain such that no two differ by a clique. That would completely kill off all hopes of a Sperner-type proof, and it is also quite a nice problem in itself (though it may turn out to be easy).

Let me state that formally as a problem. It strikes me as an almost compulsory question to try to answer if one wishes to prove Conjecture 4.

Problem 5. Is it true that for every $\delta>0$ there exists a sequence of distinct graphs $G_1\subset G_2\subset\dots\subset G_r$ such that for every subset $A\subset\{1,2,\dots,r\}$ of size at least $\delta r$ there exist $i such that $i,j\in A$ and $G_j\setminus G_i$ is a clique?

I suspect that this question is not too hard. In fact, I think Mark Walters probably already knows the answer. (No logical relationship is intended between those two sentences.) If the answer is yes, then one could set about trying to decompose the set of all graphs on $n$ vertices into a union of such sequences (or do something more general like approximating the uniform measure on the set of all graphs by a weighted sum of such sequences). However, I think it will be more interesting if the answer is no. Then one would be faced with the following question: what could a proof of Conjecture 4 conceivably look like?

One difficulty we would face with this problem if we adopted it as a Polymath project is that we do not have as wide a variety of model proofs to work with as we had with DHJ. The obvious theorem to try to generalize is the theorem of Sarkozy and Furstenberg, but the only two proof techniques that have so far given proofs of that theorem are Fourier analytic techniques (used by Sarkozy, and also in subsequent proofs such as that of Green) and ergodic techniques. It seems to be hard to develop an analogue of Fourier analysis in a Hales-Jewett setting—we had a try at that with DHJ(3), and although we did have some ideas we did not manage to use them to prove DHJ(3) itself. Having said that, we did find a Fourier-ish proof of Sperner’s theorem, so perhaps it would be worth revisiting those ideas.

An alternative approach might be to try to find a more combinatorial proof of the theorem of Sarkozy and Furstenberg. Given the way that the PET induction scheme works, it might be sensible to assume Szemerédi’s theorem. If we could find a density increment argument that made use of Szemerédi’s theorem, then we might be able to generalize it in a way that was similar to the way the modified version of Ajtai and Szemerédi’s proof of the corners theorem was generalized to yield DHJ(3). That is quite a long shot, but it still seems worth asking the following question.

Problem 6. Is there a combinatorial proof, using Szemerédi’s theorem as a black box, that shows that if $A$ is a dense subset of $\{1,2,\dots,N\}$ that contains no pair $(a,a+\binom d2)$, then there is an arithmetic progression $P\subset\{1,2,\dots,N\}$ with length tending to infinity such that the density of $A$ inside $P$ is at least $\delta+c(\delta)$?

How might Szemerédi’s theorem be useful, even in principle? I’m not sure, but the kind of thing I vaguely imagine is, say, a clever trick that associates a two-dimensional set with $A$, finds a density increment in some set $P\times Q$, where $P$ is an arithmetic progression and $Q$ is a translate of $P$, and does something clever with the diagonals.

That’s probably so vague as to be useless. One might get something better by examining the colour-focusing argument of Walters. It is admittedly a colouring argument, but it would at least give some ideas if we wanted a proof of the following kind (which is the basic form of the DHJ proof).

Step 1: Find a configuration of a certain kind in which $A$ is dense.

Step 2: Argue that many numbers cannot be in $A$ as a result, and that these numbers form a set with a certain structure to it. (This is where a close examination of Walters’s argument might give us some clues.)

Step 3: By averaging, show that $A$ has a density increment on a structured set.

Step 4: Show that a structured set can be almost entirely partitioned into arithmetic progressions with square common difference. (It’s plausible that Szemerédi’s theorem might be useful for this step.)

Step 5: By averaging, obtain a density increment on an arithmetic progression of square common difference.

Step 6: Iterate.

***********************

I am writing this section of the post after having been in contact with Mark Walters. It seems that part of what I wrote above may be wrong (in as far as a matter of judgment can be wrong). It turns out that he does not know the answer to Problem 5 above, and despite what I said above that is good evidence that the problem is after all hard. His instinct is that such a sequence of graphs does exist, and that if it didn’t exist then the entire theorem would be false.

That suggests another question one could think about.

Problem 7. Suppose that for every $n$ there is a dense set of graphs with vertex set $\{1,2,\dots,n\}$ such that no two differ by a clique. Does it follow that for every nested sequence $G_1\subset\dots\subset G_r$ there is a dense subset $A\subset\{1,2,\dots,r\}$ such that if $i,j\in A$ then $G_j\setminus G_i$ is not a clique?

In case that sounds a bit far fetched, let me indicate how one might go about proving it (not that I have any particular reason to suppose that this proof idea works). Given a nested sequence of graphs $G_1\subset\dots\subset G_r$ one would choose some $n$ that is much much bigger than $r$ and then cover the set of all graphs with vertex set $\{1,2,\dots,n\}$ as evenly as possible with “copies” of this sequence. Then one would take a dense set of graphs with vertex set $\{1,2,\dots,n\}$ and no clique difference, and by averaging one would find a copy of $(G_1,\dots,G_r)$ that contained at least $\delta r/2$ elements of this dense set. This would show that the copy of $(G_1,\dots,G_r)$ had a dense subset with no clique difference, and hence that $(G_1,\dots,G_r)$ itself had a dense subset with no clique difference.

Since almost all graphs contain almost all small graphs as induced subgraphs, and do so with roughly the same frequency, it could be that the above sketch is basically correct, but I’d need to check. If it is, then Problem 5 is, as Mark thought, equivalent to the whole problem. In that case, attention would focus on the following question: how does one produce a nested sequence of graphs that is “rich” in clique differences?

To make that question very slightly more precise, let us define a class of graphs as follows. Given a nested sequence of $G_1\subset\dots\subset G_r$, let $H$ be the graph with vertex set $\{1,2,\dots,r\}$ where $i$ is joined to $j$ if and only if $G_j\setminus G_i$ is a clique. Let us call a graph $H$ constructed in this way a clique-difference graph. Problem 5 can be reformulated as follows.

Problem 5A. Is it true that for every $\delta>0$ there exists a clique-difference graph with $r$ vertices and independence number at most $\delta r$?

(The independence number of a graph is the largest possible number of vertices you can find such that no two are joined, so this is equivalent to saying that you cannot find $\delta r$ graphs in the corresponding nested sequence without two of them differing by a clique.)

Having reformulated Problem 5 in this way, we are in a position to ask weaker questions, and therefore to give ourselves some hope of getting started. For instance, one could ask the following general question.

Problem 8. What properties do clique-difference graphs have?

To give some idea of the kind of result one might hope for here, let me make the simple observation that clique-difference graphs are all triangle free, since a disjoint union of two cliques is never a clique. So we are searching for a triangle-free graph with small independence number (and hence large chromatic number). This might sound a bit worrying, but the difficulty already arises in the number-theoretic case. For instance, if you join two integers when they differ by a cube, you get a triangle-free graph (by a special case of Fermat’s last theorem, proved by Euler), but all dense sets of integers contain a difference equal to a cube (so there’s yet another solution to the nice problem of finding triangle-free graphs with arbitrarily large chromatic number).

Of course, the fact that clique-difference graphs are triangle free is working against us, but it may be that if we could understand the restrictions that clique-difference graphs have to satisfy, we would then be in a better position to work out whether clique-difference graphs with small independence number exist.

If constructing good clique-difference graphs seems to be too difficult, then another line of attack might be a probabilistic one. The following question encapsulates what I mean.

Problem 9. Let $r=\binom s2$ and define a nested sequence of graphs $G_0\subset\dots\subset G_r$ with vertex set $\{1,2,\dots,s\}$ by taking $G_0$ to have no edges and letting $G_{i+1}$ be the union of $G_i$ with a random edge not contained in $G_i$. What can we say about the resulting clique-difference graph?

Looking at that after having written it, I’m not sure it’s such a great question. It looks to me as though if you add edges completely randomly, then there will be almost no clique differences in the resulting sequence. But perhaps one can do something more ingenious, such as adding edges in a way that favours vertices of high degree. (Such processes have been studied in detail as a way of modelling how the internet grows.) So let us interpret “random edge” above to mean “edge chosen according to some clever procedure that involves at least some randomization”. Even then, it is by no means clear that randomization will work better than a careful deterministic choice of graph sequence that creates many clique differences.

### 48 Responses to “The first unknown case of polynomial DHJ”

1. Polynomial DHJ « Euclidean Ramsey Theory Says:
2. Kristal Cantwell Says:

I think the following is the paper by Bergelson and Leibman you referred to:
Polynomial extensions of van der Waerden’s and Szemeredi’s theorems (jointly with A. Leibman), Journal of AMS 9 (1996), no.3, 725-753. It is available at:
at http://www.math.ohio-state.edu/~vitaly/PolSz.pdf

here is the Walters paper:

http://www.cs.umd.edu/~gasarch/vdw/walters.pdf

3. Gil Kalai Says:

These are interesting problems! Looking naively at it, Conjecture 4 is very appealing (especially since we know that the coloring statement is correct). Maybe I miss something obvious but I cannot imagine a sequence that will work for Conjecture 5, even for delta =1/2 and even for the coloring version. Namely, a chain of graphs so that whenever you color them with 2 colors one color contain a clique-gap.

• Klas Markström Says:

Gil, won’t the following work? Construct a sequence by adding one edge to the last graph in every step, that means that two consecutive graphs differ by a K_2, and make sure that G_0 and G_6 differ by a K_4. Then there is a unique two-colouring which avoids a K_2 difference, but then G_0 and G_6 get the same colour and we get a K_4 instead.

• Gil Says:

Dear Klas, yes two colors is certainly pushing it. I am curious if a bounded number of colors is not anough for any chain of graphs. (Maybe this somehow follows from the coloring results but I do not see it.) A chain of graphs where I see some hope for many clique gaps and where I dont know if many colors are needed is this: you start by putting all edges of a complete bipartite graph, then add edges to make it complete 3-partite graph, then add edges to make it complete 4 partite graph, and so on (I dont know what sizes these parts should be).

• gowers Says:

With reference to Question 8 (what properties to clique-difference graphs have?) it is interesting to note, as comes out of your remarks, that one can get short cycles, and even short odd cycles, but it seems hard to do this except by using very small cliques as the differences. So if, for instance, one began by restricting to the set of graphs where the number of edges is 1 mod 100 (or for colouring problems by insisting that any two graphs of the same colour have to have the same number of edges mod 100) then it starts to look very hard indeed to find a chain such that the induced clique-difference graph has low independence number or high chromatic number.

So a possible line of attack, if one thinks the answer to Problem 5 is no, is to take an arbitrary sequence of nested graphs, to pass to a dense subset where all graphs have the same number of edges mod 100, and then to argue that there are so few clique differences (or at least that the induced clique-difference graph is so sparse in some useful sense) that we can get rid of all the remaining ones quite easily. I’m not sure I believe that that will work though: I do not have a strong view about whether Problem 5 is or is not equivalent to Conjecture 4. In fact, one thing I like about this project is that the problem of deciding whether those two questions are equivalent seems easier than either of the questions themselves. So there would be something promising to think about straight away.

Going back to Gil’s question, I think it becomes interesting even with three colours, since finding an odd cycle is unlikely to be challenging, but it doesn’t seem to be easy to find a small graph that is not 3-colourable. (For instance, one can’t find a K_4.) If I’m wrong about that, then one could just look at graphs where the number of edges is a multiple of 100. Then I don’t think it would be easy.

Here is a more philosophical (but still potentially important) question: what is the level of difficulty of the problem? Let me be more specific. The level of difficulty of the Furstenberg/Sarkozy theorem is roughly comparable to the level of difficulty of Roth’s theorem. Basically, the reason is that in both cases one ends up looking at an expectation over a product of three functions: in Roth’s case one looks at $\mathbb{E}_{x,d}f(x)f(x+d)f(x+2d)$, where $f$ is the characterstic function of your set $A$, whereas in the Furstenberg/Sarkozy theorem one looks at $\mathbb{E}_{x,d}f(x)f(x+d)g(d)$, where $f$ is the characteristic function of your set and $g$ is the characteristic function of the set of perfect squares. In both cases, the fact that there are only three functions means that one can use Fourier analysis (as comes out particularly clearly in Ben Green’s proof).

This suggests, by analogy, that Conjecture 4 ought to be of roughly comparable difficulty to DHJ_3, and use methods of a broadly similar type. But is the analogy correct? For instance, one could argue that DHJ_3 itself involves differences of a special kind (they have to be vectors that consist just of 0s and 1s) and that it is therefore of difficulty comparable to Szemerédi for progressions of length 4. But going against that is that the set that the differences have to belong to is a particularly simple one, and is therefore not enough to lift the problem “up a level”.

Having written that, I now feel that the analogy is correct, which could explain why the problem is hard. If this is right, then another vague but potentially important question is the following: what would it mean to use methods for this problem that are “of the same broad type as those used for DHJ_3”?

4. Randall McCutcheon Says:

I will have some more detailed comments but, very quickly, the coloristic version is due to Bergelson and Leibman…I did publish a proof in my springer lecture notes but it’s not even independent…it is in fact their proof precisely, but with the ergodic facade removed (their proof is not actually dynamical…they set it up as a recurrence theorem for continuous maps of compact metric spaces, but nowhere in the proof did they use continuity of the maps or completeness of the space…all I did was remove the nonsense and make the proof read as a purely combinatorial one).

A second point I would like to make is that there is one joint extension of the Sarkozy-Furstenberg theorem and the density Hales-Jewett theorem that is known to obtain…and that is that in DHJ_2, you can choose your wildcard set to have cardinality n^2. I have two proofs of this fact. The first is one paragraph, completely elementary but uses SF as a lemma; it is unlikely to generalize. (I’ll try to dig it up and post it later.) The second is rather long (quite a few pages), uses ergodic theory and contains a lot of ideas that might prove useful in attacking more general problems of this type (like, for example, that one can choose a wildcard set of cardinality n^2 in DHJ_3).

In fact, this seems to be a good problem to make explicit…it might be more accessible than the problem you discuss here and people might already have some good ideas about it, since we so recently were heavily into DHJ.

Question: In DHJ_3, can one always find a combinatorial line with wildcard set of cardinality n^2?

5. Randall McCutcheon Says:

In this post I will suggest a couple of (ostensibly easier) problems.
Perhaps they should be taken with a grain of salt in that I was also
keen on going for easier cases than DHJ$_3$ on the polymath1 blog. In
that case it seems I was unduly pessimistic, however here there may
be a better case for pessimism. Here are some progressively more
general statements.

1. Sarkozy’s theorem: every set of natural numbers having positive
upper density contains a configuration $\{a,a+n^2\}$.

2. IP Sarkozy (Bergelson-Furstenberg): If $E$ is a
set of natural numbers having positive upper density and $R$
is an IP set (that is, the set of finite sums without repeats of
some infinite sequence) then $E$ contains a configuration of
the form $\{a, a+r^2\}$ with $r\in R$.

3a. FVIP Sarkozy (M): If $\Omega$ is an infinite commutative
semigroup, $(y_i)$ a sequence in $\Omega$, $(n_i)$
a sequence of integers, and $E\subset \Omega$ has positive
density, then $E$ contains a configuration $\{a, a+ \sum_{i,j\in \alpha, ij} n_{ij} \}$.

4. VIP Sarkozy in ${\bf N}$ (open). If $E$ is a set of
natural numbers having positive upper density and $(n_{ij})$
is an infinite upper triangular matrix whose entries are natural
numbers then $E$ contains a configuration of the form $\{a, a+\sum_{i,j\in \alpha, i>j} n_{ij} \}$.

5. VIP Sarkozy (open). If $\Omega$ is an infinite commutative
semigroup, $E\subset \Omega$ is a set of positive upper
density and $(n_{ij})$ is an infinite upper triangular matrix
whose entries come from $\Omega$ then $E$ contains a
configuration of the form $\{a, a+\sum_{i,j\in \alpha, i>j} n_{ij} \}$. (It’s fully general here to take $\Omega ={\bf N}^{{\bf N}\times {\bf N}}$ and let $n_{ij}$ be the
coordinate-wise basis, i.e. $n_{ij}(i,j)=1$ and $n_{ij}=0$
elsewhere.)

6. QDHJ$_2$ (Conjecture 1 above).

In the ergodic theory setting, we have worked on 6 virtually not at
all…some attention has been given the less ambitious 5 (2, 3a and
3b constituting some miniscule progress), where one has a very
natural ergodic formulation that everyone believes should be true and
looks like it might be amenable to attack. It’s not really even
ergodic theory, but straight functional analysis, so even Tim might
like this angle…I can explain it more fully in a separate reply.

For 6, we don’t even have a decent ergodic theory formulation I think
one can use Tao’s ideas from Polymath1 to give a lousy one, but my
somewhat strong (and slightly principled) hunch is that ergodic theory
will prove useless in attacking 6. This is one respect in which the
problem appeals to me polymathically…since I don’t have any idea
how to do it using methods familiar to me, I am very interested in
what people would come up with from different angles. On the other
hand, there are often (perhaps even always) strong parallels in the
methods, which is some cause for pessimism. Another strong plus is
that the problem has what I see as at least two weak formulations
that are themselves very good problems; a solution to either would
amount to a great success, I think…they are 5 above and
DHJ$_3$ with $n^2$ wildcards, which I mentioned in my
previous reply. From the ergodic theory perspective, 5 is almost
surely cleaner to think about and already exhibits the crucial
source of all the pessimism, though the graph/clique formulation
may be nicer from a strictly combinatorial perspective.

• Randall McCutcheon Says:

Somehow this got eaten….I mention it only because it’s the one instance in which the principle difficulty has been overcome, though unfortunately in a way that cannot possibly generalize too far:

3b. DVIP Sarkozy (Balister-Bergelson-M): If $E$ is a set of natural numbers having positive upper density and $(n_{ij})$ is an infinite upper triangular matrix whose entries are natural numbers with (various conditions here having a rather complicated and not easy to formulate common theme, including $n_{ij}=j^i$ and $n_{ij}= o (\sqrt{i\over \log i})$ as notable special cases) then $E$ contains a configuration of the form $\{a, a+\sum_{i,j\in \alpha, i>j} n_{ij} \}$.

6. gowers Says:

Randall, Many thanks for this interesting collection of further problems (not all of which I yet understand — e.g. is alpha an infinite set in 3-5 or is it just large and finite?). I haven’t yet managed to guess what V and FV stand for …

One small remark is that the problem about getting a wildcard set of perfect-square size in DHJ3 looks to me unlikely to be easier than quadratic DHJ, since it implies that you can find (x,x+y^2,x+2y^2) in a dense set of integers, which is strictly harder than finding (x,x+y^2), which seems to be all you can get out of QDHJ. But perhaps you see things differently because you know more about the currently available proof techniques: I would be interested to hear your thoughts on this.

7. Randall McCutcheon Says:

Some corrections.

(Principal, of course, not principle.) I am finding it difficult to handle the incorporation of latex without encountering baffling anomalies. V is officially for “variant” cf. BFM96 though Hillel chose the name wth “Vitaly” in mind (maybe…I wasn’t consulted). The F is for officially for “finitely generated” (the problem with VIP systems is that when you do PET you can possibly get down to infinitely different many IPs, which is the source of all the trouble…if you just stipulate that this is not to happen you can prove things and there are a few natural applications along these lines, such as generalized polynomials and other things), though it is entirely plausible, if unlikely, that I chose it with “Furstenberg” in mind.

Here is an attempt to repair 3a. above (in answer to Tim’s question $\alpha$ is any large finite set):

3a. FVIP Sarkozy (M): If $\Omega$ is an infinite commutative semigroup, $(y_i)$ a sequence in $\Omega$, $(n_i)$ is a sequence of integers, and $E\subset \Omega$ has positive density, then $E$ contains a configuration $\{a, a+ \sum_{i,j\in \alpha, j>i} n_iy_j\}$. There exists $M=M(\delta,k)$ having the property that if $E\subset \{0,1,\ldots ,k-1\}^M$ with $|E|\geq \delta k^M$ then there exist $n\in {\bf N}$ and a variable word $w(x)$ having $n^2$ wildcards such that $\big\{w(t):t\in \{0,1,\ldots ,k-1\} \big\}\subset E$.

Proof for $k=2$: Let $\delta_0$ be the infimum of the set of $\delta$ for which the conclusion holds and assume for contradiction that $\delta_0>0$. Choose by Sarkozy-Furstenberg an $m$ such that for any $A\subset \{1,2,\ldots ,m\}$ with $|A|\geq {\delta_0\over 3} m$, $A$ contains a configuration $\{a, a+n^2\}$, with $n>0$. Let $\delta=\delta_0-{\delta_0\over 4\cdot 2^m}$ and put $M'=M\big(\delta_0+{\delta_0\over 3\cdot 2^m},2\big)$. Finally put $M=m+M'$. We claim $M$ works as $M(\delta,2)$. Suppose then that $E\subset \{0,1\}^M$ with $|E|\geq \delta 2^M$.

Now, for each $v\in \{0,1\}^m$, let $E_v=\big\{w\in \{0,1\}^{M'}:vw\in E\big\}$.If $|E_v|> \big( \delta_0+{\delta_0\over 3\cdot 2^r}\big) 2^{M'}$ for some $v$ we are done; $E_v$ will by hypothesis contain $\{ w(0),w(1)\}$ for some variable word $w$ having $n^2$ wildcards for some $n$, so that $\{ vw(0), vw(1) \}\subset E$. (Notice that $vw(x)$ is again a variable word having $n^2$ wildcards.)

We may therefore assume that $|E_v|\leq \big( \delta_0+{\delta_0\over 3\cdot 2^m}\big) 2^{M'}$ for every $v$. A simple calculation now shows that $|E_v|\geq {\delta_0\over 3}2^{M'}$ for all $v$ (otherwise, $E$ would be too small.)

Now for $1\leq i\leq m$, let $v_i$ be the word consisting of $i$ 0s followed by $(m-i)$ 1s. Since $\sum_{i=1}^m |E_{v_i}|\geq {m \delta_0\over 3}2^{M'}$, there must be some $u\in \{0,1\}^{M'}$ with $\big\vert \big\{i: u\in E_{v_i} \big\} \big\vert \geq {\delta_0\over 3}m$. By choice of $m$, there are $a$ and $n>0$ such that $u\in E_{v_a}\cap E_{v_{a+n^2}}$. It follows that $\{ v_{a}u, v_{a+n^2}u\} \subset E$. This set has the form $\{ w(0), w(1)\}$ for a variable word $w(x)$ having $n^2$ wildcards.

• Randall McCutcheon Says:

Hmmm…is the issue that you can’t use less than in math mode? Another try:

3a. FVIP Sarkozy (M): If $\Omega$ is an infinite commutative semigroup, $(y_i)$ a sequence in $\Omega$, $(n_i)$ is a sequence of integers, and $E\subset \Omega$ has positive density, then $E$ contains a configuration $\{a, a+ \sum_{i,j\in \alpha, j>i} n_i y_j \}$.

Next is the first alluded-to proof in the $k=2$ case of getting a wildcard set of cardinality $n^2$ (hoping for less than 3 latex perplexities). Yes, I do have reason to believe that the $k=3$ case of this is easier than ${\rm QDHJ}_2$. I can elaborate at some point. (The second, longer proof provides the basis for the optimism.)

Conjecture: Let $\delta>0, k\in \mathbf{N}$. There exists $M=M(\delta,k)$ having the property that if $E\subset \{0,1,\ldots ,k-1\}^M$ with $|E|\geq \delta k^M$ then there exist $n\in {\bf N}$ and a variable word $w(x)$ having $n^2$ wildcards such that $\big\{w(t):t\in \{0,1,\ldots ,k-1\} \big\}\subset E$.

Proof for $k=2$: Let $\delta_0$ be the infimum of the set of $\delta$ for which the conclusion holds and assume for contradiction that $\delta_0>0$. Choose by Sarkozy-Furstenberg an $m$ such that for any $A\subset \{1,2,\ldots ,m\}$ with $|A|\geq {\delta_0\over 3} m$, $A$ contains a configuration $\{a, a+n^2\}$, with $n>0$. Let $\delta=\delta_0-{\delta_0\over 4\cdot 2^m}$ and put $M'=M\big(\delta_0+{\delta_0\over 3\cdot 2^m},2\big)$. Finally put $M=m+M'$. We claim $M$ works as $M(\delta,2)$. Suppose then that $E\subset \{0,1\}^M$ with $|E|\geq \delta 2^M$.

Now, for each $v\in \{0,1\}^m$, let $E_v=\big\{w\in \{0,1\}^{M'}:vw\in E\big\}$.If $|E_v|> \big( \delta_0+{\delta_0\over 3\cdot 2^r}\big) 2^{M'}$ for some $v$ we are done; $E_v$ will by hypothesis contain $\{ w(0),w(1)\}$ for some variable word $w$ having $n^2$ wildcards for some $n$, so that $\{ vw(0), vw(1) \}\subset E$. (Notice that $vw(x)$ is again a variable word having $n^2$ wildcards.)

We may therefore assume that $|E_v|\leq \big( \delta_0+{\delta_0\over 3\cdot 2^m}\big) 2^{M'}$ for every $v$. A simple calculation now shows that $|E_v|\geq {\delta_0\over 3}2^{M'}$ for all $v$ (otherwise, $E$ would be too small.)

Now for $1\leq i\leq m$, let $v_i$ be the word consisting of $i$ 0s followed by $(m-i)$ 1s. Since $\sum_{i=1}^m |E_{v_i}|\geq {m \delta_0\over 3}2^{M'}$, there must be some $u\in \{0,1\}^{M'}$ with $\big\vert \big\{i: u\in E_{v_i} \big\} \big\vert \geq {\delta_0\over 3}m$. By choice of $m$, there are $a$ and $n>0$ such that $u\in E_{v_a}\cap E_{v_{a+n^2}}$. It follows that $\{ v_{a}u, v_{a+n^2}u\} \subset E$. This set has the form $\{ w(0), w(1)\}$ for a variable word $w(x)$ having $n^2$ wildcards.

• Randall McCutcheon Says:

Almost right…. It might be useful (to me, if to no one else) to set up a garbage thread for people (maybe just me) to use as a previewer.

Conjecture: Let $\delta>0, k\in {\bf N}$. There exists $M=M(\delta,k)$ having the property that if $E\subset \{0,1,\ldots ,k-1\}^M$ with $|E|\geq \delta k^M$ then there exist $n\in {\bf N}$ and a variable word $w(x)$ having $n^2$ wildcards such that $\big\{w(t):t\in \{0,1,\ldots ,k-1\} \big\}\subset E$.

8. Gil Says:

Is there a regularity lemma for graphs whose vertices are labelled by pairs {i,j}?

• gowers Says:

What other properties are you assuming? For instance, is there some sense in which the graph is “dense”? (E.g. the graph might have n vertices and every vertex might have a distinct label with i and j both at most $C\sqrt n$.) Is it possible to say in slightly more detail what kind of statement you are looking for?

• Gil Says:

Yes, I would ask it for dense graphs; I am not sure about the statement but it would be of a kind that will allow you to conclude the existence (or even count) “subgraphs” where the “type” of a subgraph depends also on the labelling of the vertex. (So 2 graphs are “isomorphic” if there is a permutation of the square root distibct labels then send one to the other.)

9. Randall McCutcheon Says:

Sources of optimism, sources of pessimism.

I’m going to try to explain why I think DHJ3 with $n^2$ wildcards might be easier than QDHJ2. In order to do this, I need to explain a bit about the ergodic theory (actually more functional analysis) formulation of 5 above (albeit with squares instead of upper triangles). I apologize in advance if I skirt too many details to be clear to ergodic theory outsiders…I’ll elaborate on any given points if asked.

Let $(U_{ij})$ be commuting unitary operators on a Hilbert space and let $f$ be a vector in the Hilbert space. If $\alpha$ is a finite subset of naturals, put $V_\alpha = \prod_{i,j\in \alpha} U_{ij}$. Then for any $\epsilon>0$ there is an $\alpha$ with $\langle f, V_\alpha f\rangle > -\epsilon$.

A proof of the above would establish 5 from my previous post. Now, the first thing one would try is to take a weak limit of the $V_\alpha$ along an “IP ring”. (An IP ring is the set of finite unions of a countable family of disjoint finite sets, and the limit is taken as the minimal element of your set tends to infinity.) You can always do this, by Hindman’s theorem. Denoting the limit by $P$, one has $\langle f, V_\alpha f\rangle \rightarrow \langle f, Pf\rangle$. In order to get that this is non-negative you need to know that $P$ is positive. We think in fact it is positive but can’t prove it (still, this is a very promising avenue), and vexingly there is a counterexample (BFM96) showing that it need not be an orthogonal projection, which is the only way we know how to show that $P$ is positive in more benign cases. A further downside is that even if one could show that $P$ is positive in the general case, that would be the end of the story…one would have a nice result about two element configurations but no Furstenberg-style “structure theory” to handle more general cases (cases that would generalize Szemeredi’s theorem, or even Roth’s theorem).

Now consider what happens when in DHJ2 you want your wildcard set to have cardinality $n^2$, and don’t care about the structure of the wildcard set. It suffices to prove the following.

Let $(U_{i})$ be unitary operators (not necessarily commuting) on a Hilbert space and let $f$ be a vector in the Hilbert space. If $\alpha$ is a finite subset of naturals, put $U_\alpha = \prod_{i\in \alpha} U_{i}$ where the product is in decreasing order of indices. Then for any $\epsilon>0$ there is an $\alpha$ with $|\alpha| =n^2$ and $\langle f, U_\alpha f\rangle > -\epsilon$.

It turns out (I think…I have it all written down but no one, me included, has checked it carefully) that this can be proved and in a way that promises a (possible…I haven’t thought about it too much) full-blown structure theory. It goes like this: first choose a subsequence such that for every $k$, the weak operator limit of $U_\alpha$ restricted to those $\alpha$ with $|\alpha|=k$ exists. Call the limit $P_k$. Now take any function $n$ from subsets of ${\bf N}$ to the naturals of the form $n(\alpha)=\sum_{i\in \alpha} x_i$ and choose an IP ring such that the weak operator limit of $P_{n(\alpha)^2}$ exists. Call it $Q$. Now (assuming I didn’t cheat) $Q$ is an orthogonal projection and everything works. (That orthogonal projections yield structure theories is a meta-theorem, so by “everything” I include that, though I have literally thought about it for less than one minute, in which I surmised that it would be “very very complicated”. Also a suitable PET-style induction scheme would have to be found…haven’t thought about that either, beyond noting that it might not be completely obvious.)

• Randall McCutcheon Says:

Having thought briefly now about a structure theory and an induction scheme, I’m pretty confident everything works so long as one can assume commutativity, which means if you use the FK machinery you are dealing not with DHJ but with IP Szemeredi. In particular I am pretty confident of the following, so I will just state it (somewhat prematurely) as a

Theorem. Let $k,d\in {\bf N}$ and let $\Omega$ be the free abelian semigroup on generators $\{ e_{i,j}: i\in {\bf N}, 1\leq j\leq k\}$. Every subset of $\Omega$ having positive density contains a configuration of the form $\{ a, a+\sum_{i\in \alpha} e_{i,1}, a+\sum_{i\in \alpha} e_{i,2},\ldots ,a+\sum_{i\in \alpha} e_{i,k} \}$ for a finite set $\alpha$ with $|\alpha|=n^d$ for some $n$.

10. Jason Dyer Says:

I think I’m getting confused on the definition of a clique-difference graph; are we excluding the trivial clique?

11. Proposals (Tim Gowers): Polynomial DHJ, and Littlewood’s problem « The polymath blog Says:

[…] Gowers described two additional proposed polymath projects. One about the first unknown cases of the polynomial Density Hales Jewett problem. Another about the Littelwood’s […]

12. Colin Reid Says:

This looks like a very interesting set of problems, but I got confused by some of your terminology. When I saw $H \setminus G$, I initially though ‘induced subgraph’, but then I noticed the vertex sets of $G$ and $H$ are the same, so it must instead mean a graph with edge set $E(H) \setminus E(G)$. It would seem natural enough to assume we keep the same vertex set throughout, ie $\{1, \dots, n\}$. But what does it mean to say ‘$H \setminus G$ is a clique’, if it is not an induced subgraph of something? It can’t mean $H \setminus G$ is complete on $n$ vertices. So I assume it must mean that the subgraph of $H \setminus G$ induced by non-isolated vertices is complete.

These definitions are not unreasonable, but I don’t think they are completely universal either, so it might help to elaborate.

One thought: the more non-isolated vertices in $H \setminus G$, the less likely it is a clique. When building up the chain of graphs by adding one edge at a time, we probably want to avoid touching too many vertices in quick succession.

13. Klas Markström Says:

In problem 9 I believe the random clique-difference graph will actually have bounded degree, and hence bounded chromatic number and large independent sets.

How many edges can a graph G_i to G_j:s with j>i ? If G_i has edges to some set graphs with larger indices it follows that all edges added to G_i must form a sequence of nested cliques for those values of j. This means that G_0 will typically only have G_1 and the final complete graphs as neighbours.

For a G_i with i close to half the total number of edges all cliques for higher j will come from picking the edges of a sequence of nested cliques in the complement of G_i. This puts an upper bound of about log(n) on the degree, but again it is more likely to be constant.

Yet another bound comes from the fact that since all added edges have to be included in the cliques the size of the clique is controlled by the number of vertices included in the edges. For a uniform random graph this means hat as soon as the graph becomes connected the only possible clique is the whole K_n.

This means that for preferential attachment models where vertices of very high degree are created quickly the sizes of the cliques adding to the degree of G_i will have to grow quickly and we are again forced towards lower, or even bounded, degree for the clique-difference graph.

This is of course only informal reasoning but I don’t think it would be too hard to turn it into a proper result saying that for nested sequences of random graphs the chromatic number will be bounded.

14. Kristal Cantwell Says:

It looks to me that in problem 9 the only cliques in the clique graph of the most random graph are edges and triangles. That would mean that in that case the number of edges of the graph is bounded by 4. Furthermore I think in that case we can decompose into two bipartite graph and color the graph with four colors. So I think most of the random clique graphs would have chromatic number four. Most is 1-c/s^6 where c is a constant

15. Gil Kalai Says:

Here is a weaker question than Conjecture 4: For a set of positive density of graphs on n vertices there are two graphs in the set whose *symmetric difference* is a clique.

Is this known?

While at it when we consider families of graphs we can replace various notions of error-correcting codes by refine notions. E.g. families of graphs that the symmetric difference between any two has cromatic number larger than k, is connected, etc. Where these graph codes studied?

• gowers Says:

My former research student Mark Walters worked on the first question you ask during his PhD. He didn’t solve it (but did prove some theorems for other families of graphs, such as cycles), and as far as I know it is still not known. Of course, the obvious thing to try for this variant is Fourier analysis, and Mark did. I can’t remember what the difficulty was. It might be interesting to have another go.

• Gil Kalai Says:

Interesting… Is the special case where the collection of graphs itself is a subspace (namely closed under taking symmetric differences) known? Are Mark’s results in this area published?

• gowers Says:

To judge from his web page, I think they are not published, so you’d have to ask him directly and hope that he still has his thesis in electronic form.

• Gil Kalai Says:

Tim, just to be sure: Conjecture 4 and the others are completely open, right? it is not that they have known but extremely complex ergodic theoretic proof like was the case for DHJ?

On the code side, here is a nice question: Is there a family of graphs on n vertices of size 2**(alpha n^2) so that the symmetric difference between every two can be covered by ten (say) cliques.

• Mark Walters Says:

I don’t think I ever had anything non-trivial for this question but I will list a few of the things I remember.

I thought briefly about the symmetric difference being a clique and then wondered whether forbidding a single fixed size clique (eg $K_4$) was sufficient to rule out a positive density set $A$. I was unable to solve this and did not return to the case of forbidding all clique symmetric differences. I have some recollection that I thought $K_5$ was more likely to rule out a positive proportion as it has an even number of edges (obviously necessary) and each vertex has even degree. I do not know whether the latter has any relevance.

I think it is also easy to show that forbidding $C_4$ as a symmetric difference is sufficient to rule out a positive proportion. It essentially follows from an averaging argument followed by an application of the fact that a positive proportion of the cube $\{0,1\}^n$ contains 2 points with symmetric difference of size 2.

Indeed suppose $A$ is an $\varepsilon$ proportion of all graphs on $n$ vertices. Fix two vertices $u, w$ and let $H$ be the union of all the paths $P_1,P_2,\dots,P_{n-2}$ of length 2 between them. With an easy (but slightly tedious to write out) argument we can find $P_i$ and $P_j$ and two graphs $G_1,G_2 \in A$ with symmetric difference $P_i\cup P_j$.

• gowers Says:

Ah, that’s interesting. My first reaction to the fixed-graph suggestion was that it must surely be false, but then I realized that I was confusing what happens in the integers (where there are only two numbers at distance $d$ from $x$) with what happens here (where there are many graphs at “distance” $K_4$ from $G$).

That suggests two nice problems. One is to see what can be said about a set of graphs that doesn’t have any $K_4$ symmetric differences. Another is perhaps to ask for more with general cliques: for example, can we say that a set of graphs with no clique differences has exponentially small density? (I’d be happy with an exponential bound in the number of vertices, but probably this is a very hard problem — or false.)

• gowers Says:

@Gil: Yes, I’m pretty sure Conjecture 4 is completely open.

• Gil Kalai Says:

It looks that the easiest question we mentioned but did not unswer is this: Is there a vector space of graphs with n vertices of bounded codimension which does not contain any clique.

• Mark Walters Says:

Doesn’t this last question (vector space of bounded codimension) follow from the colouring PHJ: colour the space of all graphs by which coset of the vector space it lies in? Or am I missing something?

• Mark Walters Says:

For the symmetric difference K_4 case I can’t even see if the colouring case is true (and I don’t remember thinking about it). Just to be explicit: suppose you r colour all graphs on n vertices. Must there be two graphs G and H with the same colour and symmetric difference a K_4?

• Gil Kalai Says:

Right, Mark, for subspaces the density and coloring questions are the same…good point.

16. gowers Says:

Here’s a question that probably has a very easy answer, but I don’t instantly see it. If you have a collection of subsets of $\{1,2,\dots,n\}$ of size $c2^n$, then must there be two sets $A$ and $B$ in the collection such that $|A\Delta B|=2$? It seems obvious that the answer is going to be yes. By averaging one can of course assume that all the sets have the same size.

• Mark Walters Says:

I think this one is easy. Split the cube into 2 bits: one of even parity and one of odd parity. Working just inside one we are asking for a set with no 2 points at distance at most 2: therefore the 1 balls miust be disjoint. These each contain n points o you cant have more than 2^n/n points in total.(and 2^n/n in the other part).

• gowers Says:

Oops. I know that argument well, and now can’t see why I didn’t see that it worked here.

• gowers Says:

I asked the question because I was thinking about the $K_4$ problem. Here’s an idea that doesn’t work but that might conceivably be a model for a cleverer idea that does.

I’ll give a false proof for the $K_4$ problem. Define the $P_3$ball of a graph $G$ to be the set of all $H$ such that $G\Delta H$ is a path of length 3. If the $P_3$-balls of $G$ and $G'$ intersect, then we have a graph $H$ that differs from each of $G$ and $G'$ in a $P_3$. If those two $P_3$s are $abcd$ and $bdac$, then putting them together we get the clique with vertex set $\{a,b,c,d\}$.

Of course, that’s rubbish because there is no reason for the two $P_3$s to be related in such a helpful way. So we have to make do with a much weaker condition: that the $P_3$-ball of $G$ does not intersect the $P_3$-ball of $G'$ via two $P_3$s of the form $abcd$ and $bdac$. That’s probably too weak to be of use.

Did you at some point try to work out the Fourier transform of the set of $K_4$s? I’m curious to know whether one can get anywhere with a density-increment argument.

• Mark Walters Says:

I did do something with Fourier things but I never really had a feel for the Fourier techniques so I could have easily overlooked something obvious. In other words it is very definitely worth trying them again.

17. gowers Says:

OK, let me see whether I can work out the Fourier coefficients of the (characteristic function of) the set $\mathcal{K}$ of all cliques of size 4. Except that I think it will look slightly nicer if I normalize by setting $m=\binom n2$ and taking the function $f=2^m\binom n4^{-1}\mathcal{K}$. Then
$\hat{f}(\emptyset)=2^{-m}\sum_Hf(H)=1$.

What is $\hat{f}(G)$ for an arbitrary graph on $n$ vertices? It is
$\binom n4^{-1}\sum_{K\in\mathcal{K}}(-1)^{|K\cap G|}$.

We can interpret this as follows: we define a random variable $X_G$ by picking a random clique $K$ of size 4 and letting $X_G$ take the value 1 if $|K\cap G|$ is even and 0 otherwise. Then $\hat{f}(G)$ is the expectation of $X_G$.

For example, if $G$ is a single edge, then $X_G=-1$ with probability $6/m$, so $\hat{f}(G)=1-12/m$. If $G$ is a complete bipartite graph with vertex sets of density $\alpha$ and $\beta$ (so $\alpha+\beta=1$), then we get that $\hat{f}(G)=\alpha^4-4\alpha^3\beta+6\alpha^2\beta^2-4\alpha\beta^3+\beta^4$ (since the number of edges in the $K_4$ joining the two vertex sets is even if the vertices of the $K_4$ are split into two even-sized sets and odd otherwise), which equals $(\alpha-\beta)^4$. If $G$ is a random graph, then the probability that $|K\cap G|$ is even looks close to 1/2, so $\hat{f}(G)$ will be small.

It looks hard to give some useful expression for $\hat{f}(G)$, so the next step would probably be to try to work out what one hopes to extract from the Fourier information, just so we have a target to aim at.

18. Gil Kalai Says:

If you forbid the complete bypartite $K_{n,n}$ as the symmetric difference then I think that there is a simple argument based on known result that the density greater than $c^{n}$ for $c<1$ guarantees such a symmetric difference. This is known if you consider to start with just characteristic vectors of complete bipartite graphs; and by an averaging argument you get it for the full discrete cube. (I dont know if $c^{n}$ can be replaced by something better even $c^{-n^2}$.) I also dont know a Sperner version. (The symmetric difference feels more like the cup-set problem and the Sperner one feels like DHJ.)

I don't see how to extend it to complete graphs (but perhaps complete bipartite graphs $K_{n,n}$ can be regarded as the first case of PHJ as well). We can try an application of the polynomial method a la Frankl Wilson or the remarkable argument for Frankl-Rodl theorem.

• Mark Walters Says:

I think the Sperner version for forbidding $K_{t,t}$ differences (for all t) is like a variant of conjecture 1 where rather than requiring the wildcard set to be of the form $X\times X$ we just require it to be of the form $X\times Y$ where $X$ and $Y$ have the same size. I think (from experience with the colouring case) that this is a significantly weaker statement (and is less applicable). However, that weakness might make it an excellent first step.

In the symmetric difference version then even if we only forbid a $K_{s,2t}$ for a single fixed $s,t$ then we cannot have a positive proportion of the graphs on $n$ vertices. (Forbidding symmetric differences of odd size is trivial: hence the constraint that one part has even size in the above.)

Let us prove this. Suppose $A$ is a collection of an $\varepsilon$ proportion of the graphs on $n$ vertices. Fix a set $S$ of $s$ vertices and let $T_1,T_2,\dots T_m$ be disjoint sets (from $S$ and each other) of $t$ vertices. For any graph $G$ on $n$ vertices we can map $Q=\{0,1\}^m$ into the space of graphs on $n$ vertices by mapping a point in $Q$ viewed as a subset $I$ of $[m]$ to the graph
$\displaystyle{G \bigtriangleup \bigtriangleup_{i\in I} K(S,T_i)}$.

By an averaging argument there must be some graph $G$ for which this image contains at least $\varepsilon 2^m$ points and thus, for this $G$, if we take the preimage of $A$ we have an $\varepsilon$ proportion of $\{0,1\}^m$ and so, as in an earlier comment, we must have two points with symmetric difference of size 2, say $\{i,j\}$. But this corresponds under our mapping to two graphs with symmetric difference $K(S,T_i)\cup K(S,T_j)=K(S,T_i\cup T_j)$: a $K_{s,2t}$ as required.

• Gil Kalai Says:

Dear Mark, But the $K_{t,t}$ Sperner version should suffice to imply Sarkozy -Furstenberg’s theorem, right? Can we try the Cauchy-Swartz argument from http://terrytao.wordpress.com/2013/02/28/a-fourier-free-proof-of-the-furstenberg-sarkozy-theorem/ ?

• Gil Kalai Says:

Any more thoughts?