|
|
A361261
|
|
Array of Ramsey core number rc(s,t) read by antidiagonals.
|
|
2
|
|
|
2, 3, 3, 4, 5, 4, 5, 6, 6, 5, 6, 8, 8, 8, 6, 7, 9, 10, 10, 9, 7, 8, 10, 11, 11, 11, 10, 8, 9, 12, 13, 13, 13, 13, 12, 9, 10, 13, 14, 15, 15, 15, 14, 13, 10, 11, 14, 15, 16, 16, 16, 16, 15, 14, 11, 12, 15, 17, 18, 18, 18, 18, 18, 17, 15, 12, 13, 17, 18, 19, 20, 20, 20, 20, 19, 18, 17, 13
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
The Ramsey core number rc(s,t) is the smallest n such that for all edge 2-colorings of K_n, either the factor induced by the first color contains an s-core or the second factor contains a t-core. (A k-core is a subgraph with minimum degree at least k.)
|
|
REFERENCES
|
R. Klein and J. Schönheim, Decomposition of K_{n} into degenerate graphs, In Combinatorics and Graph Theory Hefei 6-27, April 1992. World Scientific. Singapore, New Jersey, London, Hong Kong, 141-155.
|
|
LINKS
|
|
|
FORMULA
|
rc(s,t) = ceiling(s + t - 3/2 + sqrt(2*(s-1)*(t-1) + 9/4)).
|
|
EXAMPLE
|
For order 5, one of the two factors has at least 5 edges, and so contains a cycle. For order 4, K_4 decomposes into two paths. Thus rc(2,2) = 5.
The square array begins:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
3, 5, 6, 8, 9, 10, 12, 13, 14, 15, 17, ...
4, 6, 8, 10, 11, 13, 14, 15, 17, 18, 19, ...
5, 8, 10, 11, 13, 15, 16, 18, 19, 20, 22, ...
6, 9, 11, 13, 15, 16, 18, 20, 21, 23, 24, ...
7, 10, 13, 15, 16, 18, 20, 21, 23, 25, 26, ...
8, 12, 14, 16, 18, 20, 22, 23, 25, 26, 28, ...
|
|
MATHEMATICA
|
rc[s_, t_]:=Ceiling[s+t-3/2+Sqrt[2(s-1)(t-1)+9/4]]; Flatten[Table[rc[s-t+1, t], {s, 12}, {t, s}]] (* Stefano Spezia, Apr 03 2023 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|