cp's OEIS Frontend

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

%I A361261 #45 May 04 2024 07:05:41
%S A361261 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,
%T A361261 13,13,13,13,12,9,10,13,14,15,15,15,14,13,10,11,14,15,16,16,16,16,15,
%U A361261 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
%N A361261 Array of Ramsey core number rc(s,t) read by antidiagonals.
%C A361261 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.)
%D A361261 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.
%H A361261 Allan Bickle, <a href="https://allanbickle.files.wordpress.com/2016/05/dissertation4.pdf">The k-Cores of a Graph</a>, Ph.D. Dissertation, Western Michigan University, 2010.
%H A361261 Allan Bickle, <a href="https://www.dmgt.uz.zgora.pl/publish/pdf.php?doi=1637">Structural results on maximal k-degenerate graphs</a>, Discuss. Math. Graph Theory 32 4 (2012), 659-676.
%H A361261 Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H A361261 Sascha Stoll, <a href="https://limejuicestudio.com/pdf/Final_Master_thesis.pdf">On Subgraphs With Minimum Degree Restrictions</a>, Master's Thesis, Karlsruhe Institute of Technology, 2019.
%F A361261 rc(s,t) = ceiling(s + t - 3/2 + sqrt(2*(s-1)*(t-1) + 9/4)).
%e A361261 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.
%e A361261 The square array begins:
%e A361261    2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
%e A361261    3,  5,  6,  8,  9, 10, 12, 13, 14, 15, 17, ...
%e A361261    4,  6,  8, 10, 11, 13, 14, 15, 17, 18, 19, ...
%e A361261    5,  8, 10, 11, 13, 15, 16, 18, 19, 20, 22, ...
%e A361261    6,  9, 11, 13, 15, 16, 18, 20, 21, 23, 24, ...
%e A361261    7, 10, 13, 15, 16, 18, 20, 21, 23, 25, 26, ...
%e A361261    8, 12, 14, 16, 18, 20, 22, 23, 25, 26, 28, ...
%t A361261 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 *)
%Y A361261 Cf. A361684 (rc(n,n)), A080036 (rc(2,n)).
%K A361261 nonn,tabl
%O A361261 1,1
%A A361261 _Allan Bickle_, Mar 28 2023