login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003323 Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's.
(Formerly M2594)
4

%I M2594 #74 Oct 21 2023 23:49:06

%S 2,3,6,17

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

%C 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.

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

%C 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

%C From _Pontus von Brömssen_, Jul 23 2021: (Start)

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

%C 51 <= a(4) <= 62,

%C 162 <= a(5) <= 307,

%C 538 <= a(6) <= 1838,

%C 1682 <= a(7) <= 12861.

%C (End)

%C 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

%D G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.

%D 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.

%D H. W. Gould, personal communication.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Shalom Eliahou, <a href="https://doi.org/10.48550/arXiv.1912.05353">An adaptive upper bound on the Ramsey numbers R(3,...,3)</a>, Integers 20 (2020), Paper No. A54, 7 pp; arXiv:1912.05353 [math.CO], 2019.

%H H. W. Gould, <a href="/A002998/a002998.pdf">Letters to N. J. A. Sloane, 1974</a>

%H R. E. Greenwood and A. M. Gleason, <a href="http://dx.doi.org/10.4153/CJM-1955-001-4">Combinatorial relations and chromatic graphs</a>, Canad. J. Math., 7 (1955), 1-7.

%H Stanisław Radziszowski, <a href="https://doi.org/10.37236/21">Small Ramsey numbers</a>, The Electronic Journal of Combinatorics, Dynamic Surveys, DS1 (ver. 16, 2021).

%F The limit of a(n)^(1/n) exists and is at least 3.199 (possibly infinite). (See the survey by Radziszowski.) - _Pontus von Brömssen_, Jul 23 2021

%F a(n) = min {k >= 0; A343607(k) > n}. - _Pontus von Brömssen_, Aug 01 2021

%F For n >= 4, a(n) <= n!*(e-1/6) + 1. - _Elijah Beregovsky_, Mar 22 2023

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

%Y Cf. A045652, A343607.

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

%K nonn,more,hard

%O 0,1

%A _N. J. A. Sloane_

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

%E Better definition from _Max Alekseyev_, Jan 12 2008

%E Comment corrected by _Brian Kell_, Feb 14 2010

%E Changed a(4) to 62, following Fettes et al. - _Jeremy F. Alm_, Jun 08 2016

%E Entry revised by _N. J. A. Sloane_, Jun 12 2016

%E a(4) and a(5) deleted (since they are not known), a(0) prepended by _Pontus von Brömssen_, Aug 01 2021

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:58 EDT 2024. Contains 371254 sequences. (Running on oeis4.)