DIMACS TR: 95-51

Finite Canonization



Author: Saharon Shelah

ABSTRACT

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.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-51.ps.gz

DIMACS Home Page