10
$\begingroup$

Ramsey Theory says that every sufficently large (but finite) complete graph having $d-$coloured edges contains a monochromatic complete subgraph with $k$ vertices.

One could ask for asymptotics: Let $A(n,d,k)$ be the minimal number of monochromatic complete subgraphs with $k$ vertices contained in any complete graph with $n$ vertices whose edges are coloured with $d$ colours.

One has the obvious bounds: $n+1-N\leq A(n,d,k)\leq {n\choose k}\sim \frac{n^k}{k!}$ where $N$ is the corresponding Ramsey number.

There exists thus a critical exponent $\alpha$ such that $\lim_{n\rightarrow\infty}\frac{A(n,d,k)}{n^{\beta}}=\infty$ for all $\beta<\alpha$ and $\liminf_{n\rightarrow\infty}\frac{A(n,d,k)}{n^{\beta}}=0$ for all $\beta>\alpha$.

What is $\alpha$? Perhaps the function $\frac{A(n,d,k)}{n^{\alpha}}$ has a nice behaviour?

Are there any instance where one can say anything interesting? (One has obviously $\alpha\geq 1$ a strict inequality would probably already be interesting.)

The same type of question can be asked for Erd\"os-Szekeres, for van der Waerden (with a different, much smaller but still affine lower bound) etc.

Added after Gowers solution: Gowers gave the following easy proof that $\alpha=k$. Denote by $m=\inf\lbrace n\ \vert\ A(n,d,k)>0\rbrace$ the Ramsey number corresponding to our problem. Since a fixed monochromatic $k-$clique is contained in exactly ${n-k\choose m-k}$ subsets of size $m$ we have $$A(n,d,k)\geq\frac{{n\choose m}}{{n-k\choose m-k}}\sim \frac{n^k}{m^k}\ .$$

The only interesting question is thus the exact value of $\lim_{n\rightarrow\infty}\frac{A(n,d,k)}{n^k}$ which exists by Gowers first argument.

$\endgroup$
2
  • $\begingroup$ A question about "There exists thus a critical exponent $\alpha$": Although the answer from Gowers shows that $\alpha$ exists, I don't see how this existence would follow just from the bounds in the previous paragraph of the question. Is "thus" to be interpreted as asserting a necessary connection, or does it merely mean that the bounds lead one to believe that $\alpha$ exists? $\endgroup$ Jun 22, 2011 at 13:21
  • $\begingroup$ The definition of $\alpha$ uses $\liminf$ which (together with the easy inequalities) ensures its existence. $\endgroup$ Jun 22, 2011 at 13:42

3 Answers 3

11
$\begingroup$

I'm not sure this is as interesting as you think. Here is a sketch that $\alpha=k$. For large enough $n$ we can apply Szemer\'edi's regularity lemma simultaneously to all the colour classes. The result is a collection of block graphs that add up to 1 everywhere (approximately). If the number of blocks is larger than the corresponding Ramsey number (plus a little bit to allow for the error) then you get a block-clique joined by block-edges all of the same colour. Then a counting lemma gives you a number of cliques that is proportional (with a very small constant of proportionality) to $n^k$.

Actually, I'm being stupid. As I know perfectly well, since I've used it frequently, one can just average over all subgraphs with m vertices, where m is the relevant Ramsey number. Each one contains a monochromatic clique, and since m doesn't depend on n the number of cliques you end up with is proportional to $n^k$.

Essentially the same argument works for van der Waerden and many other problems.

Edit: actually, the regularity lemma comment wasn't entirely stupid, because it can be used to show that $A(n,k,d)/n^k$ tends to a limit as $n$ tends to infinity, answering another of your questions above.

$\endgroup$
7
  • $\begingroup$ Thank you. Your first argument is a little bit too sketchy for me but I like your second argument which can be made quite explicit (added at the end of the question). I do however not understand how to treat van der Waerden since we have to restrict ourself to subsets forming arithmetic progressions and I do not see an uniform bound of a given monochromatic progression of length $k$ in aritmetic subprogressions of length $m$ in $\lbrace 1,2,\dots,n\rbrace$. The bound depends very much on the step-size of the monochromatic arithmetic progression of length $k$. $\endgroup$ Jun 23, 2011 at 7:37
  • $\begingroup$ The trick with progressions is to work in the cyclic group of order n instead of the interval {1,2,...,n}. Then, at least if n is prime, the number of progressions of a given step size does not depend on the step size. Of course, not all progressions in the cyclic group correspond to progressions in the original group, but there are various tricks for dealing with this. (One, for instance, is to prove a lemma that every progression of length k in the cyclic group contains a "genuine" subprogression of length about $\sqrt{k}$, which comes from a pigeonhole argument.) $\endgroup$
    – gowers
    Jun 23, 2011 at 9:01
  • $\begingroup$ PS Would it be useful if I expanded a bit on the regularity-lemma argument? $\endgroup$
    – gowers
    Jun 23, 2011 at 9:02
  • 3
    $\begingroup$ Actually, the regularity lemma is not needed even to prove the limit exists. Indeed, the standard averaging argument shows that $\frac{A(k,n,d)}{{n \choose k}}$ is a monotone increasing function of $n$, which is bounded from above by $1$, and hence the limit as $n$ tends to infinity of this ratio converges. $\endgroup$
    – Jacob Fox
    Aug 25, 2013 at 23:52
  • 1
    $\begingroup$ The function $A(k,n,d)$ is a version of the Ramsey multiplicity function. A couple additional references for this topic include: D. Conlon, On the Ramsey multiplicity of complete graphs, Combinatorica 32 (2012), 171–186 and J. Fox, There exist graphs with super-exponential Ramsey multiplicity constant, J. Graph Theory 57 (2008), 89–98. $\endgroup$
    – Jacob Fox
    Aug 25, 2013 at 23:56
5
$\begingroup$

OK, this is an attempt to amplify the very brief sketch of what could be done with the regularity lemma. Of course, I'll still give a sketch, but I'll try to say more clearly what I mean.

First of all, the regularity lemma itself says that for every $\epsilon&gt;0$ there exists a constant $K$ such that for every graph $G$ you can partition the vertex set into $k\leq K$ sets $V_1,\dots,V_k$ of roughly equal size such that for all but $\epsilon k^2$ of the pairs $(i,j)$ the induced bipartite subgraph (or just subgraph if $i=j$) is $\epsilon$-regular. Here, $\epsilon$-regular means something like "behaves to within $\epsilon$ like a typical random graph of the same density". I won't say precisely what that means, but I hope it will be plausible that this quasirandomness property will have the consequences I claim it has.

Now if we $r$-colour a complete graph, that's the same as partitioning the edges into $r$ graphs. It turns out that a simple modification of the proof of the regularity lemma allows us to apply it to all these $r$ graphs at once, obtaining a single partition that works for all of them. (Of course, now the constant $K$ will depend on $r$ as well as on $\epsilon$.) What I mean here is that for all but $\epsilon k^2$ pairs, all $r$ of the induced bipartite subgraphs are $\epsilon$-quasirandom.

For many purposes, all random graphs of a given density behave in the same way. That is the case here, so once we have our partition the only information we really care about is the densities of the various colours in the various bipartite graphs. That is, we care about numbers like $\alpha_{ijs}$ where that is the density of edges in $V_i\times V_j$ that are coloured with colour $s$.

Let's call a pair $(i,j)$ good if all the colour classes of edges in $V_i\times V_j$ are quasirandom. The main consequence we need of quasirandomness is that if you have $d$ of the sets $V_1,\dots,V_k$ such that all the pairs from among those $d$ sets are good, then the number of cliques of colour $s$ will be approximately $|V_{i_1}|\dots|V_{i_d}|\prod_{j,h\leq d}\alpha_{i_ji_hs}$, where $V_{i_1}\dots V_{i_d}$ are the sets in question. Since almost all pairs are good, almost all $d$-tuples generate $\binom d2$ pairs that are all good. It follows that up to some error that tends to zero with $\epsilon$, the number of monochromatic cliques, as a fraction of $n^k$, depends just on the numbers $\alpha_{ijs}$. (To see this, you just add up over all possible $d$-tuples.) It follows that the minimum number of monochromatic cliques can be found by calculating a minimum over all choices of $\alpha_{ijs}$. Since $k$ is bounded above by a number that depends on $\epsilon$ and $r$ only, this is in principle a finite problem for any given $\epsilon$, $d$ and $r$. (However, the bound on $k$ is absolutely vast, so this problem is absolutely not feasible in practice.) More to the point, it proves that $A(n,d,r)/n^d$ tends to a limit as $n$ tends to infinity with fixed $d$ and $r$. (Apologies -- I've changed your $k$ to a $d$ and your $d$ to an $r$. That's because I chose $k$ in the regularity lemma, which I now regret.)

It remains to establish that this limit isn't zero. A quick and dirty way of doing that is to make $\epsilon$ so small that there must exist $R(r,d)$ of the sets $V_i$ such that all pairs are good, where $R(d,r)$ is the number needed to get a monochromatic clique of size $d$ when you have $r$ colours. For each pair we can now choose the colour that occurs most frequently and colour that pair with that colour. Applying Ramsey's theorem, we obtain a monochromatic clique of size $d$, which translates into $d$ sets $V_{i_1}\dots V_{i_d}$ that are all quasirandomly joined in that colour with density at least $1/r$. By quasirandomness, that gives us (to within a small error) at least $r^{-\binom d2}|V_{i_1}|\dots|V_{i_d}|$. Each $V_i$ has at least $n/K$ elements, and $K$ is independent of $n$, which completes the proof.

$\endgroup$
5
  • $\begingroup$ One remark that I ought to have made is that the minimum number of monochromatic cliques is not what you might expect. You might think that the best example (when n is large) was a random colouring, but a famous result of Andrew Thomason is that if you 2-colour a graph and want to minimize the proportion of cliques of size 4 that are monochromatic, then there is a sequence of colourings that give a lower limiting density than 1/32 (which is what you get for a random colouring). This disproved a conjecture of Erd&#337;s. $\endgroup$
    – gowers
    Jun 23, 2011 at 16:58
  • $\begingroup$ Still very much open is what the minimum density actually is ... $\endgroup$
    – gowers
    Jun 23, 2011 at 16:59
  • $\begingroup$ Are there any ideas for the minimum density? (A rather naive approach is to suppose that one gets a Gaussian distribution for uniformly chosen random distribution and to look at the value corresponding to the inverse of the total number of colourings. Should this roughly give the correct answer?) $\endgroup$ Jun 24, 2011 at 8:07
  • $\begingroup$ I'm afraid I don't understand the approach you are suggesting, but the general class of difficult problem this one falls into is where any small example can be turned into a sequence of big examples, but the best small examples known are rather complicated, so one has no confidence in their being best possible or any hint of what the best possible would look like (and it's conceivable that the examples get more and more complicated as they get better and better). $\endgroup$
    – gowers
    Jun 24, 2011 at 8:44
  • $\begingroup$ My approach was rubbish! $\endgroup$ Jun 24, 2011 at 9:07
2
$\begingroup$

First, the short answer to the general question is that $\frac{A(n,d,k)}{\binom nk}$ is (nonstrictly) increasing in $n$, whence for $n\ge m$ we have $$A(n,d,k)\ge\frac{A(m,d,k)}{\binom mk}\binom nk\ge\frac{\binom nk}{\binom mk}=\frac{\binom nm}{\binom{n-k}{m-k}}$$ where $m=\min\{n:A(n,d,k)\gt0\}$ is the appropriate Ramsey number. This was mentioned in a comment by @Jacob Fox which is almost buried by all the other answers and comments, so it may be worth repeating.

Second, it should be noted that the exact answer is known for the simplest nontrivial case, $2$ colors and monochromatic triangles: $$A(n,2,3)=\binom n3-\left\lfloor\frac n2\left\lfloor\frac{(n-1)^2}4\right\rfloor\right\rfloor.$$ This is Goodman's theorem; see A014557 and A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783. A proof can also be found in my answer to the math.SE question counting triangles in a graph or its complement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.