Kurt Gödel Research Center

2015 seminar talk: Trees, ladders and graphs

Talk held by Daniel Soukup (University of Toronto, Canada) at the KGRC seminar on 2015-01-15.

Abstract

The chromatic number of a graph $G$ is the least (cardinal) number $\kappa$ such that the vertices of $G$ can be covered by $\kappa$ many independent sets. A fundamental problem of graph theory asks how large chromatic number affects structural properties of a graph and in particular, is it true that a graph with large chromatic number has certain obligatory subgraphs? The aim of this talk is to introduce a new and rather flexible method to construct uncountably chromatic graphs from non special trees and ladder systems. Answering a question of P. Erdős and A. Hajnal, we construct graphs of chromatic number $\omega_1$ without uncountable infinitely connected subgraphs.