A361684 Ramsey core number rc(n,n).

2, 5, 8, 11, 15, 18, 22, 25, 28, 32, 35, 39, 42, 45, 49, 52, 56, 59, 62, 66, 69, 73, 76, 80, 83, 86, 90, 93, 97, 100, 103, 107, 110, 114, 117, 121, 124, 127, 131, 134, 138, 141, 144, 148, 151, 155, 158, 161, 165, 168, 172, 175, 179, 182, 185, 189, 192, 196, 199, 202

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

The beginning of the square array is:

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

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.
		

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

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000
• 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. A361261 (array of rc(s,t)), A080036 (rc(2,n)).

Programs

Mathematica

A361684[n_]:=Ceiling[2n-3/2+Sqrt[2(n-1)^2+9/4]];
Array[A361684,100] (* Paolo Xausa, Dec 01 2023 *)

Formula

a(n) = rc(n,n) = ceiling(2*n - 3/2 + sqrt(2*(n-1)^2 + 9/4)).