This is a bit of a niche post, since its target audience is people who are familiar with quasirandom graphs and like proofs of an analytic flavour. Very roughly, a quasirandom graph is one that behaves like a random graph of the same density. It turns out that there are many ways that one can interpret the phrase “behaves like a random graph” and, less obviously, that they are all in a certain sense equivalent. This realization dates back to seminal papers of Thomason, and of Chung, Graham and Wilson.

I was lecturing on the topic recently, and proving that certain of the quasirandomness properties all implied each other. In some cases, the proofs are quite a bit easier if you assume that the graph is regular, and in the past I have sometimes made my life easier by dealing just with that case. But that had the unfortunate consequence that when I lectured on Szemerédi’s regularity lemma, I couldn’t just say “Note that the condition on the regular pairs is just saying that they have quasirandomness property ” and have as a consequence all the other quasirandomness properties. So this year I was determined to deal with the general case, and determined to find clean proofs of all the implications. There is one that took me quite a bit of time, but I got there in the end. It is very likely to be out there in the literature somewhere, but I haven’t found it, so it seems suitable for a blog post. I can be sure of at least one interested reader, which is the future me when I find that I’ve forgotten the argument (except that actually I have now found quite a conceptual way of expressing it, so it’s just conceivable that it will stick around in the more accessible part of my long-term memory).

The implication in question, which I’ll state for bipartite graphs, concerns the following two properties. I’ll state them qualitatively first, and then give more precise versions. Let be a bipartite graph of density with (finite) vertex sets and .

**Property 1.** If and , then the number of edges between and is roughly .

**Property 2.** The number of 4-cycles (or more precisely ordered quadruples such that is an edge for all four choices of ) is roughly .

A common way of expressing property 1 is to say that the density of the subgraph induced by and is approximately as long as the sets and are not too small. However, the following formulation leads to considerably tidier proofs if one wants to use analytic arguments. I think of as a function, so if is an edge of the graph and 0 otherwise. Then the condition is that if has density in and has density in , then

This condition is interesting when is small. It might seem more natural to write on the right-hand side, but then one has to add some condition such as that in order to obtain a condition that follows from the other conditions. If one simply leaves the right-hand side as (which may depend on ), then one obtains a condition that automatically gives a non-trivial statement when and are large and a trivial one when they are small.

As for Property 2, the most natural analytic way of expressing it is the inequality

An easy Cauchy-Schwarz argument proves a lower bound of , so this does indeed imply that the number of labelled 4-cycles is approximately .

The equivalence between the two statements is that if one holds for a sufficiently small , then the other holds for a that is as small as you want.

In fact, both implications are significantly easier in the regular case, but I found a satisfactory way of deducing the first from the second a few years ago and won’t repeat it here, as it requires a few lemmas and some calculation. But it is given as Theorem 5.3 in these notes, and the proof in question can be found by working backwards. (The particular point that is easier in the regular case is Corollary 5.2, because then the function mentioned there and in Lemma 5.1 is identically zero.)

What I want to concentrate on is deducing the second property from the first. Let me first give the proof in the regular case, which is very short and sweet. We do it by proving the contrapositive. So let’s assume that every vertex in has degree , that every vertex in has degree , and that

Since for each fixed , the expectation over on the left-hand side is zero if , it follows that there exists some choice of such that

We now set and . Then and both have density (by the regularity assumption), and the above inequality tells us that

,

so we obtain the desired conclusion with . Or to put it another way, if we assume Property 1 with constant , then we obtain Property 2 with (which in practice means that should be small compared with in order to obtain a useful inequality from Property 2).

The difficulty when is not regular is that and may have densities larger than , and then the inequality

,

no longer gives us what we need. The way I used to get round this was what I think of as the “disgusting” approach, which goes roughly as follows. Suppose that many vertices in have degree substantially larger than , and let be the set of all such vertices. Then the number of edges between and is too large, and we get the inequality we are looking for (with ). We can say something similar about vertices in , so either we are done or is at least *approximately* regular, and in particular *almost* all neighbourhoods are of density not much greater than . Then one runs an approximate version of the simple averaging argument above, arguing in an ugly way that the contribution to the average from “bad” choices is small enough that there must be at least one “good” choice.

To obtain a cleaner proof, I’ll begin with a non-essential step, but one that I think clarifies what is going on and shows that it’s not just some calculation that magically gives the desired answer. It is to interpret the quantity

as the probability that the four pairs are all edges of if are chosen independently at random from and are chosen independently at random from . Then our hypothesis is that

all are edges

Let us now split up the left-hand side as follows. It is the sum of

all are edges

are edges

and

are edges

are edges,

where I have used the fact that the probability that and are both edges is exactly .

One or other of these two terms must be at least . If it is the first, then averaging gives us such that

and now we can define and just as in the regular case, obtaining the same result apart from an extra factor of 1/2.

If it is the second, then averaging over this time and dividing by gives us some such that the inequality

.

So again we are done, this time with the roles of 1 and 2 reversed.

I haven’t checked the details, but it is clear that one could run this argument for any subgraph that occurs the “wrong” number of times. The extra factor one would need to divide by would be the number of edges you need to remove from to obtain a matching.

Of course, the fact that Property 1 implies that all small subgraphs occur with roughly the right frequency is a very well known fact about quasirandom graphs, but it is usually proved using an almost regularity assumption, which I wanted to avoid.

November 10, 2018 at 5:54 pm |

Presumably for Property 2 to imply Property 1 (or even to be particularly meaningful) must just not hold for X and Y but for subset A and B of X and Y.

But clearly if you are trying to prove Property 2 you only need to prove it for X and Y.

November 13, 2018 at 4:36 pm |

It’s now occurred to me that there’s a simpler way of explaining the proof above. As commented at the end of the post, one can run the argument for any small subgraph . But it’s nicer to say that the other way round, assuming the regularity property 1 and proving that you get the right number of . And the regularity property is nicely expressed by saying that

is within of

for any pair of 01-valued functions .

If we now take the expression

and apply that assumption to the inner expectation for each fixed , we find that we can approximate the whole expression to within by

The is because we get equality when and equality to within otherwise.

And now we can replace the by at the cost of another contribution of to the error and we get what we want.

So what I should have said is that this particular formulation of the regularity property lends itself quite conveniently to proving a counting lemma — you just repeatedly replace edges by s, so to speak, and you don’t have to say anything about most vertices having roughly the expected degree.