login
Ramsey core number rc(n,n).
3

%I #24 Feb 18 2024 02:08:55

%S 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 83,86,90,93,97,100,103,107,110,114,117,121,124,127,131,134,138,141,

%U 144,148,151,155,158,161,165,168,172,175,179,182,185,189,192,196,199,202

%N Ramsey core number rc(n,n).

%C 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 The beginning of the square array is:

%C 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

%C 3, 5, 6, 8, 9, 10, 12, 13, 14, 15, 17, ...

%C 4, 6, 8, 10, 11, 13, 14, 15, 17, 18, 19, ...

%C 5, 8, 10, 11, 13, 15, 16, 18, 19, 20, 22, ...

%C 6, 9, 11, 13, 15, 16, 18, 20, 21, 23, 24, ...

%C 7, 10, 13, 15, 16, 18, 20, 21, 23, 25, 26, ...

%C 8, 12, 14, 16, 18, 20, 22, 23, 25, 26, 28, ...

%D 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 Paolo Xausa, <a href="/A361684/b361684.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 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 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 a(n) = rc(n,n) = ceiling(2*n - 3/2 + sqrt(2*(n-1)^2 + 9/4)).

%e 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[n_]:=Ceiling[2n-3/2+Sqrt[2(n-1)^2+9/4]];

%t Array[A361684,100] (* _Paolo Xausa_, Dec 01 2023 *)

%Y Cf. A361261 (array of rc(s,t)), A080036 (rc(2,n)).

%K nonn,tabl

%O 1,1

%A _Allan Bickle_, Mar 28 2023