A003323 Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's.

2, 3, 6, 17

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• more
• hard

Comments

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

Examples

			a(2)=6 since in a party with at least 6 people, there are three people mutually acquainted or three people mutually unacquainted.
		

References

• G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
• S. Fettes, R. Kramer, S. Radziszowski, An upper bound of 62 on the classical Ramsey number R(3,3,3,3), Ars Combin. 72 (2004), 41-63.
• H. W. Gould, personal communication.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Shalom Eliahou, An adaptive upper bound on the Ramsey numbers R(3,...,3), Integers 20 (2020), Paper No. A54, 7 pp; arXiv:1912.05353 [math.CO], 2019.
• H. W. Gould, Letters to N. J. A. Sloane, 1974
• R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math., 7 (1955), 1-7.
• Stanisław Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics, Dynamic Surveys, DS1 (ver. 17, 2024).

Crossrefs

Cf. A045652, A343607.

A073591(n) is an upper bound on a(n).

Formula

The limit of a(n)^(1/n) exists and is at least 3.28 (possibly infinite). (See the survey by Radziszowski.) - Pontus von Brömssen, Jul 23 2021 (updated Mar 13 2025)

a(n) = min {k >= 0; A343607(k) > n}. - Pontus von Brömssen, Aug 01 2021

For n >= 4, a(n) <= n!*(e-1/6) + 1. - Elijah Beregovsky, Mar 22 2023

Extensions

Upper bound and additional comments from D. G. Rogers, Aug 27 2006

Better definition from Max Alekseyev, Jan 12 2008

Comment corrected by Brian Kell, Feb 14 2010

Changed a(4) to 62, following Fettes et al. - Jeremy F. Alm, Jun 08 2016

Entry revised by N. J. A. Sloane, Jun 12 2016

a(4) and a(5) deleted (since they are not known), a(0) prepended by Pontus von Brömssen, Aug 01 2021