University of Cambridge > > The Archimedeans (CU Mathematical Society) > Amalgamation


Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Valentin Hübner.

Paul Erdős proved that there exist graphs with no short cycles requiring arbitrary many colours to colour their vertices so that no two adjacent vertices have the same colour. Unfortunately, the proof does not explicitly construct such graphs. A well known example sheet problem asks for an example in the simplest case, where we ban triangles—cycles of length 3. Such examples seem hard to find, and tend to contain many cycles of length 4. I shall discuss a solution to this problem by Nesetril and Rodl using their method of “amalgamation” which, while it is more complicated than other solutions, also allows us to ban longer cycles (and can do much more besides). No prior knowledge of graph theory is required.

This talk is part of the The Archimedeans (CU Mathematical Society) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity