|
%I #46 Nov 05 2023 00:20:50
%S 0,1,2,6,18,45,102,213,426,821,1538,2820,5075,8996,15743,27247,46709,
%T 79405,133996,224640,374400
%N a(0)=0, a(1)=1; thereafter a(n) = ceiling((3/2)^(n-3)*n*(n-1)).
%C Original definition was "Conjectured Ramsey number R(n,n)."
%C R(m,n) = minimal number of nodes R such that in any graph with R nodes there is either an m-clique or an independent set of size n. This sequence gives the diagonal entries R(n,n).
%C Only these values have been proved: 0,1,2,6,18. a(5) is known to be in the range 43-49. - _N. J. A. Sloane_, Sep 16 2006
%C a(5) is at most 48, see the Angeltveit/McKay reference. - _Jurjen N.E. Bos_, Apr 11 2017
%C Ramsey numbers for simple binary partition.
%C Campos, Griffiths, Morris, & Sahasrabudhe prove that R(n,n) < 3.993^n for large enough n; they say the constant "could be improved further with some additional (straightforward, but somewhat technical) optimisation". This sequence posits a constant of 1.5. - _Charles R Greathouse IV_, Mar 18 2023
%D G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
%H Vigleik Angeltveit and Brendan D. McKay, <a href="https://arxiv.org/abs/1703.08768">R(5,5) <= 48</a>, arXiv:1703.08768 [math.CO], 2017.
%H Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe, <a href="https://arxiv.org/abs/2303.09521">An exponential improvement for diagonal Ramsey</a>, arXiv preprint arXiv:2303.09521 [math.CO], 2023.
%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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RamseyNumber.html">Ramsey Number</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Ramsey%27s_theorem">Ramsey's theorem</a>.
%Y Cf. A000791, A059442, A212954 (which have many more references).
%K easy,nonn
%O 0,3
%A Jeff Boscole (jazzerciser(AT)hotmail.com), Jul 06 2006
%E Edited by _N. J. A. Sloane_, Sep 16 2006
%E This was initially submitted as a conjecture for the Ramsey number R(n,n). I have replaced the definition with the exct formula that was used. - _N. J. A. Sloane_, Nov 05 2023
|
