Improving the lower bounds for some small diagonal Ramsey numbers seems to be surprisingly difficult. Although a significant effort has been made, most of the lower bounds for did not change over the last few decades. These lower bounds are either obtained from Paley colorings () or by the construction discovered independently by Mathon [1] and Shearer [2] (). The Ramsey number is an interesting exception, with the lower bound derived consequently as some more general inequalities were improved. The last such effort is described in [3], where Xu, Shao and Radziszowski proved the following general inequality:

for

They established the lower bound for by applying this inequality two times. First, we have , and then .

We can show that this bound can be slightly improved by analyzing the colorings of lower order. In particular, I examined the construction used to prove the inequality for the case where -coloring is derived from the best known -coloring.

Let me first note that I did not find a way to improve the -coloring obtained by by simply adding a new vertex and recoloring the edges. But, this process produced an interesting side effect. After one vertex is added and recoloring of the edges is performed, the best coloring I got contained one in the first color, and no in the second color. I was able to replicate this construction for . If we use a complement of the graph obtained by this new construction, and then apply the construction used to prove , it is possible to produce a coloring with one in the first color and in the second color. These remaining can be eliminated by running a local improvement procedure. This result yields the next theorem.

**Theorem.** .

*Proof.* The proof is given by the existence of the -coloring of that can be downloaded here.

Note that the computation time required to verify this coloring can be significantly reduced by exploiting the fact that this graph already contains a -coloring on vertices. Additionally, to confirm the validity of this coloring, I verified the result using the several different implementations of the exact algorithms for the maximum clique problem, available online.

The approach described above implies that there is a good chance that the more general holds for . Although this inequality is weak, I did not find a way to prove it. Feel free to contact me if you are interested in working on this problem.

[1] R. Mathon, Lower Bounds for Ramsey Numbers and Association Schemes, *Journal of Combinatorial Theory*, Series B, 42: 122–127, 1987.

[2] J. B. Shearer, Lower Bounds for Small Diagonal Ramsey Numbers, *Journal of Combinatorial Theory*, Series A, 42: 302–304, 1986.

[3] X. Xiaodong, Z. Shao and S.P. Radziszowski, More Constructive Lower Bounds on Classical Ramsey Numbers, *SIAM Journal on Discrete Mathematics*, 25: 394–400, 2011.

### Like this:

Like Loading...