28
$\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$
3
  • $\begingroup$ Aside from brute force? $\endgroup$
    – David Roberts
    Jul 2, 2015 at 8:09
  • 1
    $\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, 2015 at 8:21
  • 1
    $\begingroup$ Re, perhaps @DavidRoberts meant brute force against the aliens? 😄 $\endgroup$
    – LSpice
    Apr 26, 2023 at 15:45

6 Answers 6

17
$\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$
9
  • $\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, 2015 at 17:26
  • 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, 2015 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, 2015 at 4:30
  • 2
    $\begingroup$ Concerning the last paragraph : It would perhaps be a better approach to give a year to all mathematicians to do free research in the hope that something sparks the interest of the invaders and prompts them for mercy (their interest in the value of 𝑅(5,5) shows that they are at least slightly superior to Vogons). $\endgroup$ Feb 21, 2023 at 13:41
  • 1
    $\begingroup$ @RolandBacher, re, unless perhaps they just want the value of $R(5, 5)$ to finish off a particularly nasty piece of poetry. $\endgroup$
    – LSpice
    Apr 26, 2023 at 15:48
9
$\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) - DOI: 10.22028/D291-25946. Indeed, the computational complexity of the calculation of Ramsey numbers is unknown.

$\endgroup$
5
  • $\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, 2015 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, 2015 at 17:51
  • 1
    $\begingroup$ @WillSawin --- a quantum algorithm for Ramsey numbers is described here, but the computational complexity is unknown. $\endgroup$ Jul 2, 2015 at 19:17
  • 2
    $\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, 2015 at 1:58
  • $\begingroup$ I have replaced the dead link by a link to Internet Archive. But perhaps the link DOI: 10.22028/D291-25946 could be sufficient - DOI is supposed to be stable. Of course, the same text can be found in several other places. $\endgroup$ Mar 10, 2023 at 6:29
8
$\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, 2015 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, 2015 at 12:08
7
$\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, 2015 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, 2015 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 $k$, the value of $f$ at the center is the average value of $f$ over the vertices of the box.

Proof. This is true for $k=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.

Applying 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.

Evaluating $\phi$ at $x=(1/2)^m, m=\binom{n}2$ gives the same bound as the original probabilistic existence method. However our method is constructive. One can always change each $x_{ij}=1/2$ to either $0$ or $1$ without increasing $\phi$ since $\phi$ is linear in each variable. In $m$ steps we will arrive at a vertex $x_0$ with $\phi(x_0) \le \phi(x)<1$ and hence must be zero since $\phi$ is non-negative integral at the verticesr. So $x_0$ defines an extremal graph with no monochromatic. The same method works for 2-colorings of hypergraphs.

$\endgroup$
4
  • 3
    $\begingroup$ Please use the Contact Us form to have your accounts merged, to regain full control over your posts. $\endgroup$
    – Glorfindel
    Feb 28, 2023 at 12:19
  • $\begingroup$ $\phi^{(n)}_{55}(1/2) > 1$ for $n\ge 12$ so you can't get far. In general you won't be able to approach known lower bounds for any $k,l$. It's easier to describe this process in probabilistic terms for an arbitrary function of a random graph which is linear in each edge probability. In your example, the function is the expectation of the number of $k$-cliques plus the number of $l$-indsets. $\endgroup$ Jun 6, 2023 at 6:03
  • $\begingroup$ You could try starting with random values then setting each variable to the best of 0 and 1 in random order. I don't see how an upper bound on $R(s,t)$ can be achieved as it needs proof of non-existence. There are far too many (at least $n!$) local minima for an algorithm to explore them all. Plausibly it could be used to find examples for lower bounds. $\endgroup$ Sep 2, 2023 at 11:30
  • $\begingroup$ The smallest size where this might be useful is $R(5,5)$ at $n=42$, where there are known graphs. At the starting point the value is about 1661. Setting the variables to the best of 0 and 1 gives a value depending on the order the variables are set. Random order seldom makes a value less than 200. Using a more sophisticated search, the smallest value I managed was 138. It seems there are a huge number of local minima with the vast majority of them being of no use. $\endgroup$ Sep 2, 2023 at 14:33
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, 2015 at 2:24

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.