44 KAM Mathematical Colloquium
Prof. ERNST SPECKER
ETH Zurich
MODULAR COUNTING
March 5, 2002
Lecture Room K9, Charles University, Sokolovska 83, Praha 8
16:00 PM
Abstract
Suppose that the cardinality n of a certain set is determined to
be 6942 in one paper and 7181 in another. What should we do? We can try
to decide whether n is even or odd. In order to find an answer to
such a problem, it is often advantageous to generalize it. If e.g. we want
to know whether the number of different equivalence relations on a set
of 1000 elements is even or odd, we study the function B where B(n)
is then the number of equivalence relations on a set of n elements.
It is easy to see that the B(n) mod 2 is periodic; the period being
3, the parity of B(1000) is equal to the parity of B(1),
i.e. B(1000) is odd. Does a corresponding theorem hold for the function
which counts the number of 3-colourable graphs on a set of n elements?
The aim of the talk is to characterize structures for which the answer
is positive.
