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

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, 13, 13, 13, 13, 12, 9, 10, 13, 14, 15, 15, 15, 14, 13, 10, 11, 14, 15, 16, 16, 16, 16, 15, 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

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 square array begins:

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

Links

Table of n, a(n) for n=1..78.

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

rc(s,t) = ceiling(s + t - 3/2 + sqrt(2*(s-1)*(t-1) + 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

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

Crossrefs

Cf. A361684 (rc(n,n)), A080036 (rc(2,n)).

Sequence in context: A280315 A120245 A120246 * A120244 A094727 A341511

Adjacent sequences: A361258 A361259 A361260 * A361262 A361263 A361264

Keyword

nonn,tabl

Author

Allan Bickle, Mar 28 2023

Status

approved