Aarhus University Seal / Aarhus Universitets segl

Hvad er det kromatiske tal af planet?

Jonas Andersen
Foredrag for studerende
Fredag, 23 maj, 2014, at 15:15-16:00, in Koll. G3 (1532-218)
Abstrakt:

Et af Erdös ' ynglings problemer var det følgende: Hvad er $\chi(\mathbb{E}^2)$ , det kromatiske tal af planet?

Lad os hurtigt give mening til spørgsmålet; En graf $G$ er et objekt $G=(V,E)$ , bestående af en punktmængde $V$ og en kant mængde $E$ . En kant er af formen $e=(x,y)$, hvor $x,y\in V$ er punkter, hvis $(x,y)\in E$ så kaldes $x$ og $y$ incidente . En $r$ -farvning af punkterne, er en inddeling af punkterne i $r$ disjunkte ikke tomme klasser . En $r$ -farvning kaldes ægte, hvis der ikke findes to incidente punkter i samme farveklasse. Det kromatiske tal for en graf, er det mindste antal farver $r$ , således at der eksistere en ægte $r$ - farvning.

Ved planet $\mathbb{E}^2$ forstås grafen, som har $\mathbb{R}^2$ som punktmængden og to punkter er incidente hvis afstanden mellem dem er 1 . Problemet er blevet studeret meget i de seneste 60 år. Men, vi er ikke kommet meget nærmere svaret, vi ved blot at:

$4 \leq \chi(\mathbb{E}^2) \leq 7$

Men, nye fremskridt hentyder at, svaret måske er meget afhængigt af valget af aksiomer . Vi vil se på simple graf konstruktioner, hvor det kromatiske tal afhænger meget af hvorvidt man antager udvalgsaksiomet.