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

Author

Nathan Hurtig, Jul 01 2023

Keywords

• nonn
• tabl

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.

Examples

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

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

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

Crossrefs

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

Programs

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]]

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