cp's OEIS Frontend

A361684 Ramsey core number rc(n,n).

%I A361684 #24 Feb 18 2024 02:08:55
%S A361684 2,5,8,11,15,18,22,25,28,32,35,39,42,45,49,52,56,59,62,66,69,73,76,80,
%T A361684 83,86,90,93,97,100,103,107,110,114,117,121,124,127,131,134,138,141,
%U A361684 144,148,151,155,158,161,165,168,172,175,179,182,185,189,192,196,199,202
%N A361684 Ramsey core number rc(n,n).
%C A361684 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.)
%C A361684 The beginning of the square array is:
%C A361684    2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, ...
%C A361684    3,  5,  6,  8,  9, 10, 12, 13, 14, 15, 17, ...
%C A361684    4,  6,  8, 10, 11, 13, 14, 15, 17, 18, 19, ...
%C A361684    5,  8, 10, 11, 13, 15, 16, 18, 19, 20, 22, ...
%C A361684    6,  9, 11, 13, 15, 16, 18, 20, 21, 23, 24, ...
%C A361684    7, 10, 13, 15, 16, 18, 20, 21, 23, 25, 26, ...
%C A361684    8, 12, 14, 16, 18, 20, 22, 23, 25, 26, 28, ...
%D A361684 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-1.
%H A361684 Paolo Xausa, <a href="/A361684/b361684.txt">Table of n, a(n) for n = 1..10000</a>
%H A361684 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 A361684 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 A361684 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 A361684 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 A361684 a(n) = rc(n,n) = ceiling(2*n - 3/2 + sqrt(2*(n-1)^2 + 9/4)).
%e A361684 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.
%t A361684 A361684[n_]:=Ceiling[2n-3/2+Sqrt[2(n-1)^2+9/4]];
%t A361684 Array[A361684,100] (* _Paolo Xausa_, Dec 01 2023 *)
%Y A361684 Cf. A361261 (array of rc(s,t)), A080036 (rc(2,n)).
%K A361684 nonn,tabl
%O A361684 1,1
%A A361684 _Allan Bickle_, Mar 28 2023