login
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, 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
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
KEYWORD
nonn,tabl
AUTHOR
Nathan Hurtig, Jul 01 2023
STATUS
approved