A361261 Array of Ramsey core number rc(s,t) read by antidiagonals.

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

Offset: 1

Author

Allan Bickle, Mar 28 2023

Keywords

• nonn
• tabl

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.)

Examples

			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, ...
		

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

• Allan Bickle, The k-Cores of a Graph, Ph.D. Dissertation, Western Michigan University, 2010.
• Allan Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 4 (2012), 659-676.
• Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
• Sascha Stoll, On Subgraphs With Minimum Degree Restrictions, Master's Thesis, Karlsruhe Institute of Technology, 2019.

Crossrefs

Cf. A361684 (rc(n,n)), A080036 (rc(2,n)).

Programs

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 *)

Formula

rc(s,t) = ceiling(s + t - 3/2 + sqrt(2*(s-1)*(t-1) + 9/4)).