Spring 2019

Colouring locally sparse graphs via the hard-core model

Wednesday, Apr. 17, 2019 11:30 am12:30 pm PDT

Add to Calendar

Parent Program: 

Ewan Davies, Simons Institute


Room 116

We discuss how some well-known results on maximum independent sets and colourings of triangle-free graphs can be proved using the hard-core model from statistical physics. The method can be extended to more general 'local sparsity' conditions where the flexibility of the hard-core model seems to play a more important role than in the special case of triangle-free graphs, which leads to new results.