New lower bounds for some small Ramsey numbers

The new revision of the dynamic survey Small Ramsey Numbers has recently been published [2]. I’m happy to see that many of the lower bounds G. Exoo and I obtained in [1] are included. I’m going to use this post to maintain the updates on the bounds that weren’t listed in the survey.

Ramsey Number Old Bound [2] New Bound
R(7,8) 217 219
R(6,11) 256 262
R(4,15) 155 158
R(4,16) 166 170
R(12,12) 1639 1640

The majority of the graphs used to establish the bounds listed above are discovered in 2016 using the techniques described in [1], or their variations.
The proof that R(12,12) \geq 1640, including additional explanations, can be found here.
To access other colorings, feel free to contact me.

[1] G. Exoo and M. Tatarevic, New Lower Bounds for 28 Classical Ramsey Numbers, The Electronic Journal of Combinatorics, 22 (3), #P11, 2015. [PDF]
[2] S. P. Radziszowski, Small Ramsey Numbers, The Electronic Journal of Combinatorics, #DS1, 2017. [PDF]
Advertisements

On the Ramsey Number R(12,12)

Improving the lower bounds for some small diagonal Ramsey numbers R(k, k) seems to be surprisingly difficult. Although a significant effort has been made, most of the lower bounds for 6 \leq k \leq 16 did not change over the last few decades. These lower bounds are either obtained from Paley colorings (k=6,8,10) or by the construction discovered independently by Mathon [1] and Shearer [2] (k=7,9,11,13,14,15,16). The Ramsey number R(12, 12) 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:

R(k, s + 1) \geq R(k, s) + 2k - 2\  for  k \geq 5. \ \ \ \ \ (1)

They established the lower bound for R(12,12) by applying this inequality two times. First, we have R(11, 12) \geq R(11, 11) + 2 \cdot 11 - 2 \geq 1617, and then R(12, 12) \geq R(12, 11) + 2 \cdot 12 - 2 \geq 1639.

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 (1) for the case where (k, k + 1)-coloring is derived from the best known (k, k)-coloring.

Let me first note that I did not find a way to improve the (k, k + 1)-coloring obtained by (1) 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 K_{k} in the first color, and no K_{k+1} in the second color. I was able to replicate this construction for 7 \leq k \leq 11. If we use a complement of the graph obtained by this new construction, and then apply the construction used to prove (1), it is possible to produce a coloring with one K_{k+1} in the first color and k \ K_{k+1} in the second color. These remaining K_{k+1} can be eliminated by running a local improvement procedure. This result yields the next theorem.

Theorem. R(12,12) \geq 1640.

Proof. The proof is given by the existence of the (12,12)-coloring of K_{1639} that can be downloaded here. \square

Note that the computation time required to verify this coloring can be significantly reduced by exploiting the fact that this graph already contains a (11,11)-coloring on 1596 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 R(k+1,s+1) \geq R(k,s) + 2k + 2s - 1 holds for k \geq 5. 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.

On distinct residues of factorials

The paper “On distinct residues of factorials” written by Vladica Andrejic and me will appear in Publications de l’Institut Mathématique.

“We investigate the existence of primes p > 5 for which the residues of
2!, 3!, ..., (p-1)! modulo p are all distinct. We describe the connection
between this problem and Kurepa’s left factorial function, and report that there are no such primes less than 10^{11}.”

[PDF] [arXiv]

New Lower Bounds for 28 Classical Ramsey Numbers

Recently, Geoffrey Exoo and I performed an extensive search and improved the lower bounds for 28 classical Ramsey numbers. We also introduced several new search techniques. Our paper, with summarized results and methods, is published in the Electronic Journal of Combinatorics.

“We establish new lower bounds for 28 classical two and three color Ramsey numbers, and describe the heuristic search procedures we used. Several of the new three color bounds are derived from the two color constructions; specifically, we were able to use (5,k)-colorings to obtain new (3,3,k)-colorings, and (7,k)-colorings to obtain new (3,4,k)-colorings. Some of the other new constructions in the paper are derived from two well-known colorings: the Paley coloring of K_{101} and the cubic coloring of K_{127}.”

[PDF] [E-JC] [arXiv] [MR] [DATA]

On Limits of Dense Packing of Equal Spheres in a Cube

My paper “On Limits of Dense Packing of Equal Spheres in a Cube” is published in the Electronic Journal of Combinatorics.

“We examine packing of n congruent spheres in a cube when n is
close but less than the number of spheres in a regular cubic close-packed (ccp) arrangement of  \lceil p^3/2\rceil spheres. For this family of packings, the previous best-known arrangements were usually derived from a ccp by omission of a certain number of spheres without changing the initial structure. In this paper, we show that better arrangements exist for all n \leq \lceil p^3/2\rceil - 2. We introduce an optimization method to reveal improvements of these packings, and present many new improvements for n \leq 4629.”

[PDF][E-JC][arXiv] [MR]

Searching for a counterexample to Kurepa’s Conjecture

The paper Vladica Andrejic and I wrote regarding the Kurepa’s left factorial conjecture will appear in Mathematics of Computation.

“Kurepa’s conjecture states that there is no odd prime p that
divides !p=0!+1!+...+(p-1)!. We search for a counterexample to
this conjecture for all p<2^{34}. We introduce new optimization
techniques and perform the computation using graphics processing
units. Additionally, we consider the generalized Kurepa's left
factorial given by !^{k}n=(0!)^k +(1!)^k +...+((n-1)!)^{k}, and show
that for all integers 1<k<100 there exists an odd prime p such
that p|!^{k}p.”

[PDF] [arXiv] [MCOM] [MR]

Construction of Ramsey (4,6)-Coloring

In 2012, Geoffrey Exoo improved the lower bound of the Ramsey number R(4,6) by discovering 37 new colorings of the complete graph on 35 vertices [1]. This result was unexpected while similar bounds weren’t improved for years. For example, there is a strong evidence that R(5,5) is most likely 43 [3], or similarly that further improvements of R(3,10) aren’t expected [2].

Recently, I found a slightly different method than one described in Exoo’s paper.

Construction requires two steps:

  1. The initial adjacency matrix A is produced using eleven 7 \times 7 circulant matrices given below. By circ(a_0, a_1, \ldots, a_n) we denote circulant matrix with the first row (a_0, a_1, \ldots, a_n).
    Described coloring has no monochromatic copies of K_4 in the first color, and there are only 7 monochromatic copies of K_6 in the second color.

    B = circ(0,1,1,0,0,1,1)
    C = circ(0,1,1,0,1,1,0)
    D = circ(0,1,1,1,1,1,0)
    E = circ(0,1,0,1,1,1,1)
    F = circ(0,0,0,0,1,1,0)
    G = circ(0,1,0,1,1,0,1)
    H = circ(0,1,1,0,0,0,0)
    I = circ(1,0,0,1,1,0,1)
    J = circ(0,0,1,1,1,1,0)
    K = circ(1,0,0,1,1,1,1)
    L = circ(0,1,1,0,1,0,1)

    A=\left[\begin{array}{ccccc}  B & C & D & E & F\\  C^{t} & G & G & H & I\\  D^{t} & G^{t} & J & K & L\\  E^{t} & H^{t} & K^{t} & B & B\\  F^{t} & I^{t} & L^{t} & B^{t} & G  \end{array}\right]

  2. Bad subgraphs are eliminated using simulated annealing. The adjacency matrix is given below.

01100110111110011111000011110000110
10110000011011001111110101110000011
11011001001101100111111010111000001
01101101100110110011111100011100000
00110110110011111001111110000110000
10011011011001111100101111010011000
10001101101100111110010111100001100
00110110101111010110101100001001111
10011011010110101011000110001100111
11001100101111010101100011001110011
11100111010101101010100001101111001
10110011111010110101000000111101100
11011001110101011010110000010111110
01101101011010101101011000000011111
00111110101101001001110011110110101
10011111010110000100111001111011010
11001110101011100110111100110101101
11100111010101011011011110011010110
11110011101010001100111111000101011
11111000110101100100001111101010101
01111101011010111010000111111101010
01111010000011111110001000110110011
00111101000001011111010110011111001
01011111100000001111101011001101100
10101110110000100111101101100110110
11000110011000110011100110110011011
11100010001100111001110011011001101
11110100000110111100111001101100110
00110001111100010101101100110111101
00011000111110101010111110011010110
00001100011011110101011011001101011
00000111001111011010101101101010101
10000011100111101101000110111101011
11000001110011010110110011010110101
01100001111001101011011001101011110

[1] G. Exoo, On the Ramsey Number R (4, 6), Electronic Journal of Combinatorics, #P66, 19(1) (2012)
[2] G. Exoo, On Some Small Classical Ramsey Numbers, Electronic Journal of Combinatorics, #P68, 20(1) (2013)
[3] B.D. McKay and S.P. Radziszowski, Subgraph Counting Identities and Ramsey Numbers, Journal of Combinatorial Theory, Series B, 69 (1997) 193-209.