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

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

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.

Formula

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

Example

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.

Mathematica

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

Crossrefs

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

Sequence in context: A257984 A186228 A184747 * A130258 A186496 A032765

Adjacent sequences: A361681 A361682 A361683 * A361685 A361686 A361687

Keyword

nonn,tabl

Author

Allan Bickle, Mar 28 2023

Status

approved