Unfriendly partition of graphs without an infinite subdivided clique

Thursday, September 16, 2010 -
2:30pm to 4:30pm
In this talk I prove that every graph with less than $\aleph_\omega$ vertices, which does not contain a subdivision of an infinite clique as a subgraph, must have a partition of its vertices to two sets, so that no vertex has more neighbors in its own set than in the other set. The proof uses the theorem given by Robertson Seymour and Thomas (http://www.ams.org/mathscinet/pdf/1079057.pdf), saying that such a graph has a tree decomposition with certain properties. The unfriendly partition is then constructed by analyzing some infinite game played on this tree.
Eli Berger
University of Haifa
Event Location: 
Fine Hall 224