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.