The canonization theorem says that for given m,n for some m(*)
(the first one is called ER(n;m)) we have
for every function f with domain {1,...,m(*)]^n, for some A in
[1,...,m(*)]^m, the question of when the equality
f({i(1),...,i(n)}) = f({j(1),...,j(n)})
(where i(1)<, ..., i(n) and j(1)<, ..., j(n) are from A)
holds has the simplest answer:
for some subset v of {1,...,n} the equality holds if
i(1)=j(1) for all 1 in v.
We improve the bound on ER(n,m) so that fixing n the number of
exponentiation needed to calculate ER(n,m) is the best possible.
DIMACS Home Page