15
$\begingroup$

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large monochromatic subgraphs?

That is, can we explicitly construct (edge) 2-colourings on graphs of size $c^k$, for some $c>0$, with no monochromatic complete subgraph of size $k$?

$\endgroup$
3
  • 5
    $\begingroup$ you mean c>1... $\endgroup$
    – Gil Kalai
    Nov 7, 2009 at 16:17
  • 3
    $\begingroup$ I somehow feel that Erdõs's idea is so fundamental and so generally applicable that the word "trick" doesn't do it justice. $\endgroup$
    – gowers
    Nov 10, 2015 at 21:41
  • 1
    $\begingroup$ Do you have the paper/source for "Erdős 1947 probabilistic trick"? $\endgroup$
    – Asqiir
    Nov 23, 2022 at 12:51

5 Answers 5

5
$\begingroup$

I believe the answer is "no"; the best known constructions only give no clique or independent set of size about $2^\sqrt{n}$ in a graph with $2^n$ vertices. Bill Gasarch has a page on the subject here, although I don't know how frequently it updates.

$\endgroup$
16
$\begingroup$

Finding explicit constructions for Ramsey graphs is a central problem in extremal combinatorics. Indeed, computational complexity gives a way to formalize this problem. Asking for a graph which can be constructed in polynomial time is a fairly good definition although sometimes the definition is taken as having a log-space construction.

Until quite recently the best method for explicit construction was based on extremal combinatorics. The vertices of the graphs were certain sets (say k-subset of an n element sets) and the edges represented pairs of sets with presecibed intersection. The best result was by Frankl and Wilson and it gives a graph with n vertices whose edges are colored by 2 colors with no monochromatic clique of size $\exp (\sqrt{(\log n))}$. (I think this translates to $k^{\log k}$ in the way the question was formulated here.) Using sum-products theorems Barak Rao Shaltiel and Wigderson improved the bound to $\exp (\log n^{o(1)})$.

Payley graphs are conjectured be explicit examples for the correct behavior. But proving it is much beyond reach.

Update(Nov 11, 2015): Gil Cohen found an explicit construction with no monochromatic cliques of size $2^{(\log \log n)^L}$. An independent construction which applies also to the bipartite case was achieved by Eshan Chattopadhyay and David Zuckerman

$\endgroup$
4
$\begingroup$

I also believe the answer is "no". Another reference is this paper, which treats off-diagonal Ramsey numbers (e.g. graphs with no clique of size k and no anti-clique of size l).

$\endgroup$
3
$\begingroup$

As was mentioned in the previous answers, the answer is no. Or more accurately I'd say that the answer is currently no, but possibly yes.

Also, consider the related question of constructing a bipartite graph with parts of size $2^n$, which contains no $K_{k,k}$ and whose complement contains no $K_{k,k}$ where $k = O(n)$. Such an explicit construction will have as far as I can tell huge impact on derandomization of randomized algorithms, among other topics in theoretical computer science. See e.g. this paper, where such an explicit construction is given for $k = 2^{n^{o(1)}}$.

You might also be interested in the following accompanying paper (seems like I cannot post it, being a new user; you can google it though, its title is "Pseudorandomness and Combinatorial Constructions") to Luca Trvisan's talk at ICM '06. This may contain more connections between explicit constructions of combinatorial objects and applications in theoretical computer science.

$\endgroup$
1
$\begingroup$

A question I have here is what do you mean by "explicit"?

Personally, I like the definition that a construction is explicit if it can be constructed in polynomial time (due to Alon? Wigderson??). Given that we are talking about exponentials in n here, this gets (slightly) complicated, but we'll say the controlling parameter here is $N=2^n$, the rough order of the number of vertices in a possible Ramsey graph.

One conjecture I have is that the set of Paley graphs on p vertices, where p ranges over all primes $1 \mod 4$ between $2^{(n/2)}$ and $2^{(n-1)}$ gives a lower bound on $R(n)$. This is NOT an explicit set, by my definition above. ::::grin:::::

If memory serves me, I think the best result known for your original question is in a paper of Noga Alon from a few yrs back. You may want to check his web page as well as Gasartch's survey page mentioned before.

$\endgroup$
1
  • $\begingroup$ Gil, thanks for your comment. I like the log space condition on 'explicit constructions' as stronger(?) than P time. $\endgroup$
    – Mike
    Nov 9, 2009 at 7:08

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.