cp's OEIS Frontend

Definition: if the edges of a complete graph with at least a(n) nodes are colored with n colors then there is always a monochromatic triangle, and a(n) is the smallest number with this property.

Has it been proved that a(4)=62, or is it just an upper bound? - N. J. A. Sloane, Jun 12 2016

62 is an upper bound. It is probably not the correct value, which is likely closer to the lower bound of 51. - Jeremy F. Alm, Jun 12 2016

From Pontus von Brömssen, Jul 23 2021 (updated Mar 13 2025): (Start)

According to the survey by Radziszowski, the following are the best known bounds:

51 <= a(4) <= 62,

162 <= a(5) <= 307,

538 <= a(6) <= 1838,

1698 <= a(7) <= 12861.

(End)

In general, if a(n)=r then a(n+1) <= n*(r-1) + r + 1 = (n+1)*(r-1) + 2. - Roderick MacPhee, Mar 03 2023

The complete graph K_n has (n-1) + (n-2) + ... + 1 = n(n-1)/2 edges connecting the n vertices to each other. We associate a color to each edge such that there is no monochromatic triangle, i.e., no three vertices i < j < k such that the tree edges (i,j), (i,k) and (j,k) all have the same color.

For each n, consider the smallest possible number k of colors allowing such an edge-coloring. This table lists in row n, of length n(n-1)/2, the lexicographic earliest such coloring, i.e., the colors (between 0 and k-1) of edges AB = (1,2), AC = (1,3), BC = (2,3), ..., AZ = (1,n), ..., YZ = (n-1,n).

This is the lower left part (read by rows) or the upper right part (read by columns) of the symmetric n X n matrix where the element with indices (i,j) gives the color of the edge (i,j).

We conjecture that the rows converge to a limit in the sense that an increasingly long initial segment will always remain constant for all subsequent rows: for all k >= 0 there is n such that a(m,j) = a(n,j) for all m >= n and 1 <= j <= k.

Obviously, the first element a(n,1) = 0 for all n >= 2, and the first three elements will always be a(n, 1..3) = (0, 0, 1) for all n >= 3.

It seems that for n = 6 and n = 7, too, we have a(m,k) = a(n,k) for all m >= n and 1 <= k <= n(n-1)/2. Are there other row indices with this property? (This is of course much stronger than the requirement of convergence.)

Let us call min-color any solution that uses the minimum number of colors for the respective n. The restriction of any row n to the length of an earlier row m < n is always a solution for m, but not necessarily min-color: For n = 5 we have a solution using only 2 colors, but the lex earliest solutions for n >= 6 use 3 colors among the edges between the first 4 vertices. However, the lex earliest solution for n = 5, using only 2 colors, can be extended to solutions for all n >= 6. But the lex earliest solution for n = 4 cannot be extended to a min-color solution for n = 5.

Can one or the other of the following conjectures be (dis)proved?

Conjecture 1: For any n there is a min-color solution that can be extended to a min-color solution for all larger m > n?

Conjecture 2 (implies conjecture 1): For any n there is a min-color solution that can be restricted to a min-color solution for any smaller m < n.

Since Conjecture 2 does not make any assumption about the lexicographical order, it is independent of the convergence of the rows of this sequence mentioned above.

The Prime Zeta modulo function at 7 for primes of the form 3k+1 is Sum_{primes in A002476} 1/p^7 = 1/7^7 + 1/13^7 + 1/19^7 + 1/31^7 + ...

The complementary Sum_{primes in A003627} 1/p^7 is given by P_{3,2}(7) = A085967 - 1/3^7 - (this value here) = 0.0078253541130504928742517... = A343607.