Borel Graph Combinatorics

Specialeforsvar ved Andreas Hallbäck

 Titel: Borel Graph Combinatorics

Abstract: I denne afhandling undersøges grafteoretiske emner i en Borelmålelig kontekst. Vi viser Borel udgaver af to velkendte sætninger fra endelig grafteori bevist af R. L. Brooks, omhandlende øvre grænser for en grafs kromatiske tal: Det er altid begrænset af en plus graden af grafen, og for en særlig klasse af grafer er det begrænset af graden. Det sidstnævnte resultat er ikke en fuldstændig analog til Brooks' sætning, men hvis vi i stedet betragter det såkaldte approksimative $\mu$-målelige kromatiske tal, opnår vi rent faktisk en fuldstændig analog til dette klassiske resultat. Vi undersøger også en meget nylig udvikling indenfor Borelkombinatorik, der skyldes Andrew Marks. Han anvender Boreldeterminering af uendelige spil, til at vise en lang række sætninger omhandlende Borelkromatiske tal, matchinger, antimatchinger, disjunkte fuldstændige sektioner og orienteringer. Blandt andet viser vi, at det Borelkromatiske tal for en acyklisk graf kan antage en hvilken som helst af de mulige værdier, hvorfor det følger, at selv for acykliske grafer er Brooks' sætning falsk i den Borelmålelige kontekst. 

Vejleder: Asger Törnquist
Censor:   Stig Andur Pedersen