Amalgamation

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

• Dr Paul Russell (University of Cambridge)
• Friday 26 April 2019, 19:00-20:00
• MR2, Centre for Mathematical Sciences.

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.

This talk is included in these lists:

• Guy Emerson's list
• MR2, Centre for Mathematical Sciences
• MR5, Centre for Mathematical Sciences
• The Archimedeans (CU Mathematical Society)
• bld31
• ob366-ai4er

Note that ex-directory lists are not shown.