$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

We wtorek, 29 października 2002 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Peter MIHÓK

(Technical University of Kosice, SK)

wygłosi referat pod tytułem:

Compactness theorem for generalized colorings

We introduce compactness theorems for generalized colorings and derive several particular compactness theorems from them. It is proved that the theorems and many of their consequences are equivalent in ZF set theory to BPI, the Prime Ideal Theorem for Boolean algebras.

In 1951, de Bruijn and Erdös proved that a graph is k-colorable if every finite subgraph is k-colorable. The proof of this compactness theorem used the Rado Selection Lemma, which is a consequence of BPI, the Prime Ideal Theorem for Boolean algebras. BPI is weaker than AC, the Axiom of Choice in ZF set theory, but has a large number of equivalent forms and can often be substituted for AC in proofs. Twenty years after the appearance of the de Bruijn and Erdös paper, Läuchli showed their theorem is in fact equivalent to BPI. Notions of generalized colorings have been introduced by different authors and it is natural to ask if a compactness theorem can be formulated for these colorings. We show that this is indeed the case for both generalized vertex colorings and generalized edge colorings. In addition we show that these general compactness theorems, along with several of their consequences are equivalent to BPI.

Serdecznie zapraszamy wszystkich chętnych !