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