23
$\begingroup$

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.

I am curious what algorithm we would employ if such a situation were to occur. I know analytic results have been used to put bounds on R(5,5) and R(6,6), but I am mostly interested in the problem from a computational perspective. If we were to set a computer to the task and let it run for however long it might take, what algorithm would we use? How many operations might we expect it to take/what would it's time complexity be?

Edit: I should clarify that I am seeking the best classical algorithm. It was after reading the paper that Carlo Beenakker cites using quantum annealing that I became interested in finding the best classical alternative.

$\endgroup$
2
  • $\begingroup$ Aside from brute force? $\endgroup$ Jul 2 '15 at 8:09
  • $\begingroup$ @DavidRoberts if brute force is the best way to calculate R(5,5) and R(6,6) then that would be a valid answer. However, could you please elaborate on the time-complexity and why no better algorithms exist? $\endgroup$ Jul 2 '15 at 8:21
14
$\begingroup$

I'm not sure we could find $R(5,5)$ in one year, because exhaustive search is infeasible and one year is probably not enough time to develop the extra theory that would make it possible.

I'll dispose of one type of exhaustive search, similar to what Masked Avenger proposes. Suppose we generate all graphs with no 5-clique or 5-independent-set by adding one vertex at a time with complete isomorph rejection. Suppose each computer could make one graph per microsecond (better than at present) and we have one billion computers working in parallel. Then we would know $R(5,5)$ in something like $10^{60}$ years. This is an actual estimate, not a guess.

There are ways to constrain the search to a fraction of all graphs, and also other ways to organize the search, but I don't see any that offers a promise of feasibility.

I'm dubious about SAT-solvers doing much better, since the problem is one that has a vast number of near-solutions. That is, one can assign a vast number of values to, say, 90% of the variables (probably: any 90% of the variables) and still all the incomplete constraints will appear feasible.

The only real chance is a theoretical breakthrough. If we got all the world's mathematicians onto the problem, the odds aren't bad I think.

$\endgroup$
7
  • $\begingroup$ On m = R(5,5)-1 nodes, what percentage of graphs avoid a 5-clique and an indepdent set of 5 vertices? Is it like over half or fewer than half of all isomorphism types on m nodes? Or is it a very small percentage, as is the case with R(4,4) (I think)? (I guess it should be small, as random search would have pushed the lower bound up by now.) $\endgroup$ Jul 3 '15 at 17:26
  • $\begingroup$ Thank you for the great answer Brendan! Could you perhaps point me to a source that outlines how the estimates were established? $\endgroup$ Jul 3 '15 at 20:12
  • $\begingroup$ @The Masked: An exceedingly tiny percentage. If our conjectures about $R(5,5)$ are correct, something smaller than $10^{-44000}$. $\endgroup$ Jul 4 '15 at 4:03
  • 1
    $\begingroup$ @Emile: Glad you like it. I used the method described on page 11 of cs.anu.edu.au/~bdm/papers/r45.pdf , but I did it quickly and crudely so I can be out by several powers of 10. Maybe it would take "only" $10^{50}$ years, or as much as $10^{70}$. It isn't published, and I wouldn't mention it in print without doing the calculation more carefully. $\endgroup$ Jul 4 '15 at 4:12
  • 1
    $\begingroup$ @The Masked: Ooops, I was bitten by the Unix shell (my factorial symbol ! got interpretted). The correct answer is about $10^{-205}$. This assumes our conjecture that the largest (5,5)-Ramsey graphs have 42 vertices and there are 656 of them. $\endgroup$ Jul 4 '15 at 4:30
7
$\begingroup$

Well, it seems that quantum computers offer a peaceful alternative to the aliens threat, see Experimental determination of Ramsey numbers. (Here is a tutorial on this work.) "Experimental" refers to the nature of the algorithm, which solves an optimization problem to obtain the Ramsey number with some uncertainty. The cited reference has implemented this "quantum annealing algorithm" in a superconducting circuit (the D-wave machine), correctly finding $R(m,2)$ for $4\leq m\leq 8$ and $R(3,3)$. Progress in quantum computing is sufficiently rapid, that if the aliens won't show up until later this century, we stand a good chance.

Classical algorithms for Ramsey numbers are described in Computational methods for Ramsey numbers (2000) and in Problems of Unknown Complexity: Graph isomorphism and Ramsey theoretic numbers (2009). Indeed, the computational complexity of the calculation of Ramsey numbers is unknown.

$\endgroup$
4
  • $\begingroup$ Thank you for your response. I should perhaps clarify that I meant classical algorithm. The motivation for this question came in fact after reading the paper you cited and trying to figure out what the best classical alternative is. I'll update my question to include this. $\endgroup$ Jul 2 '15 at 8:25
  • $\begingroup$ Is a quantum computing algorithm to calculate random numbers actually known? $R(m,2)$ is trivial and $R(3,3)$ is pretty easy as well. My understanding is that these quantum optimization algorithms scale very poorly. $\endgroup$
    – Will Sawin
    Jul 2 '15 at 17:51
  • $\begingroup$ @WillSawin --- a quantum algorithm for Ramsey numbers is described here, but the computational complexity is unknown. $\endgroup$ Jul 2 '15 at 19:17
  • 1
    $\begingroup$ It could be that the success of this approach would depend on the aliens' notion of "proof". I don't have much knowledge of quantum algorithms, but isn't it true that they cannot prove (in the strict mathematical sense) the non-existence of something? Isn't there always a probability of failure? $\endgroup$ Jul 3 '15 at 1:58
7
$\begingroup$

I think Brendan McKay's paper $R(4,5) = 25$ with Stanisław Radziszowski (appeared as J. Graph Theory, 19 (1995) 309–322) on computing $R(4,5)$ will describe one possible approach. It is available as a pdf here for your downloading pleasure (Added by DR: or from the publisher at doi:10.1002/jgt.3190190304).

$\endgroup$
2
  • $\begingroup$ What kind of pictures does it have? $\endgroup$ Jul 2 '15 at 15:30
  • $\begingroup$ Thanks for the link @GordonRoyle! I had stumbled over this paper earlier in my explorations, but couldn't immediately see how things scaled. Do you know of any estimates on the complexity of the algorithm applied to R(5,5) and R(6,6)? $\endgroup$ Jul 3 '15 at 12:08
6
$\begingroup$

We could view $R(5,5)$ as a satisfiability problem with $1176$ variables and $3813768$ clauses. We could try to improve general SAT solvers to the point where they can handle this, rather than using a pure brute force approach or anything specific to Ramsey numbers.

Recently a SAT solver was used on the Erdős discrepancy problem, which naively had 1161 variables, though I think their encoding used somewhat more variables than that. I have no idea what the computational complexity of using this sort of algorithm on the problem is. I'm sure it would be much more efficient than brute force, though.

$\endgroup$
2
  • 1
    $\begingroup$ It might be worth linking to the revised / updated version of the Konev and Lisitsa paper: arxiv.org/abs/1405.3097 $\endgroup$
    – j.c.
    Jul 2 '15 at 23:37
  • $\begingroup$ Probably the best thing would be either find all colourings for 42 vertices (861 variables), or show that there are none for 43 vertices (903 variables). But I'm dubious. $\endgroup$ Jul 3 '15 at 2:42
6
$\begingroup$

Several years ago I found a method based on continuous optimizaton which can sometimes find lower bound. It also applies to the SAT problem but it may not be exactly the same as the SAT solver method.

Given the number of vertices $n$ and positive integers $k,l$, we can code all $2$-colorings of the edges of $K_n$ by (the upper triangular part of) a binary matrix $x_{ij}, 1\le i < j \le n$, and write down the energy function

$$\phi_{kl}^{(n)}(x)= \sum_{1 \le i_1 <...<i_k \le n} \prod_{1 \le s< t \le k} x_{i_s i_t} + \sum_{1 \le j_1<...<j_l \le n} \prod_{1 \le s < t \le l}(1- x_{j_s j_t}),$$

which counts the total number of monochromatic $1$-$K_k$ or $0$-$K_l$. We now interpolate and think of $\phi(x)$ as a polynomial function of the ${ n \choose 2}$ real variables $x_{ij}$ which is linear in each, and must therefore satisfies a strong mean-value property :

Lemma. Let $f(x_1,...,x_n)$ be a real function which is linear in each variable. Then for any axes-parallel rectangular box of any dimension, the value of $f$ at the center is the average value of $f$ over the vertices of the box.

Proof. This is true for a $n=1$ (i.e. for a line), since $f$ is linear; for a $k$-dimensional box, we just have to take the average over the straight line joining the centers of two opposite $k-1$-dimensional faces which equals the average over the whole box. Apply this to $\phi$, we see that if $$\phi^{(n)}_{kl}(1/2,...,1/2)={ n \choose k } 2^{-{k \choose 2}} +{n \choose l} 2^{-{l \choose 2}}<1,$$ we get a lower bound $R(k,l)>n$, which is the same bound as the original probabilistic counting method. We now observe that we can make the same conclusion if we can find any $x$ inside the unit box $[0,1]^{n \choose 2}$, with $\phi(x)<1$ because of the maximum principle: $\phi$ is harmonic in any subset of the variables so any extremal value of $\phi$ inside the box must already occur at some vertex. So instead of doing brute force searching over the vertices discretely, we can try to minimize $\phi$ over the whole box continuously by some form of gradient descent algorithm.

Finding the minimum of a polynomial inside a box is however an NP-hard problem since the energy function which counts the number of falsified clauses of a truth assignment of a boolean formula in conjunctive normal form has exactly the same sum-product form as $\phi$ and SAT is NP-complete.

Evaluating $\phi$ and its gradient is compute intensive but is polynomial in $n$ for fixed $k$ and $l$ and is certainly doable for the range of $R(5,5)$ up to $n=49$.

Maybe someone with more computing power and better optimization algorithm can try this. The idea is that we don't look at all the vertices just the good ones following the gradient. The problem is of course that we cannot be sure the best we have found is the true minimum unless it is of zero energy.

$\endgroup$
0
5
$\begingroup$

I like intelligent brute force algorithms. While there may be more clever ones, the following is pretty simple. I will specialize it to the case of looking for $R(6,6)$.

Suppose we have a list (or way of streaming) all the colorings of the edges of $K_n$ which do not induce a blue $K_6$ or a red $K_6$. (So if $n$ were $6$, this would be $2$ less than $2^{15}$.) Load up a coloring, and construct a new point connected to the $n$ points. One can employ some smarts in deciding which of the $2^n$ colorings will produce colorings of $K_{n+1}$ which avoid a monchromatic $K_6$. If one is really on the ball, one can toss out colorings which are isomorphic to a coloring already produced.

Once one has generated a comprehensive and nonempty list for $K_{n+1}$, then one can move to $K_{n+2}$. A problem with this is space: when $n$ reaches $20$, the bulk of the colorings will be isomorphic to $20!$ (greater than $10^{17}$) others, and it will require some ingenuity and more time to pick one representative of each isomorphism class. Even when you have such, it is likely that you will have over $2^{50}$ valid colorings to test. You might say that's not too far from $10^{15}$, surely that can be done within a year. Maybe, but n=20 is just the beginning. Even if $R(6,6)$ turned out to be $30$ (a serious underestimate), getting to there will take repeating the process to get to $20$ at least another $2^{50}$ times. Using this algorithm, we may have to worry about heat-death of the universe occurring before we finish.

$\endgroup$
1
  • 1
    $\begingroup$ Even for the much simpler $R(4,5)$, this method needs about $10^{20}$ graphs to be constructed. That is within (non-easy) reach of computers, but for $R(5,5)$ the number of intermediate graphs is MUCH larger. For $R(6,6)$, forget it. $\endgroup$ Jul 3 '15 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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