A364026 Table read by descending antidiagonals. T(n,k) is the big Ramsey degree of k in w^n, where w is the first transfinite ordinal, omega.

1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 4, 1, 1, 0, 1, 26, 14, 1, 1, 0, 1, 236, 509, 49, 1, 1, 0, 1, 2752, 35839, 10340, 175, 1, 1, 0, 1, 39208, 4154652, 5941404, 222244, 637, 1, 1, 0, 1, 660032, 718142257, 7244337796, 1081112575, 4981531, 2353, 1, 1, 0, 1, 12818912, 173201493539

Offset

0,13

Comments

T(n,k) is the least integer t such that, for all finite colorings of the k-subsets of w^n, there exists some S, an order-equivalent subset to w^n, where that coloring restricted to the k-subsets of S outputs at most t colors.

By Ramsey's theorem, the first row T(1,k)=1 for all k.

The second row T(2,k) coincides with A000311.

The second column T(n,2) coincides with A079309.

References

Dragan Mašulovic and Branislav Šobot, Countable ordinals and big Ramsey degrees, Combinatorica, 41 (2021), 425-446.

Alexander S. Kechris, Vladimir G. Pestov, and Stevo Todorčević, Fraïssé Limits, Ramsey Theory, and topological dynamics of automorphism groups, Geometric & Functional Analysis, 15 (2005), 106-189.

Links

Table of n, a(n) for n=0..58.

Joanna Boyland, William Gasarch, Nathan Hurtig, and Robert Rust, Big Ramsey Degrees of Countable Ordinals, arXiv:2305.07192 [math.CO], 2023.

Eric Weisstein's World of Mathematics, Ordinal Number.

Formula

T(n,k) = Sum_{p=0..n*k} P(p,n,k), where for n >= 2 and k >= 1,

P(0,n,k) = 0, and for p >= 1,

P(p,n,k) = Sum_{j=1..k} Sum_{0..p-1} binomial(p-1,i)*P(i,n-1,j)*P(p-1-i,n,k-j).

Example

The data is organized in a table beginning with row n = 0 and column k = 0. The data is read by descending antidiagonals. T(2,3)=26.
The table T(n,k) begins:
[n/k]   0   1      2        3       4         5   ...
--------------------------------------------------------------------
[0]     1,  1,     0,       0,      0,        0,  ...
[1]     1,  1,     1,       1,      1,        1,  ...
[2]     1,  1,     4,      26,    236,     2572,  ...
[3]     1,  1,    14,     509,  35839,  4154652,  ...
[4]     1,  1,    49,   10340,  ...
[5]     1,  1,   175,  222244,  ...
[6]     1,  1,   637,  ...

Prog

(Haskell)
pp p n k
  | n == 0 && k >= 2 = 0
  | k == 0 && p == 0 = 1
  | k == 0 && p >= 1 = 0
  | n == 0 && k == 1 && p == 0 = 1
  | n == 0 && k == 1 && p >= 1 = 0
  | n == 1 && k >= 1 && k == p = 1
  | n == 1 && k >= 1 && k /= p = 0
  | n >= 2 && k >= 1 = sum [binom (p-1) i * pp i (n-1) j * pp (p-1-i) n (k-j) | i <- [0..p-1], j <- [1..k]]
binom n 0 = 1
binom 0 k = 0
binom n k = binom (n-1) (k-1) * n `div` k
a364026 n k =
  sum [pp p n k | p <- [0..n*k]]

Crossrefs

T(2,k) is A000311. T(n,2) is A079309.

Sequence in context: A372173 A278987 A135302 * A128760 A057884 A329637

Adjacent sequences: A364023 A364024 A364025 * A364027 A364028 A364029

Keyword

nonn,tabl

Author

Nathan Hurtig, Jul 01 2023

Status

approved