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