Sparse Graphs Coalition

Algorithmic aspects of partition functions includes finding fast algorithms for counting combinatorial objects e.g. independent sets, matchings, colourings, and more generally approximately evaluating of their generating functions e.g. independence polynomial, matching polynomial, chromatic/Tutte polynomials /Potts model. This could include using Markov chain techniques, correlation decay, the use of zero-free regions, cluster expansion, etc.

On the extremal side one is interested in maximising or minimising the polynomials above for various graph classes. Special cases of this would include questions of finding the graph(s) that maximise/minimise e.g. the number of independent sets / matchings / proper colourings amongst graphs of a certain type, e.g. n-vertex d-regular graphs.

The aim of the workshop is to introduce participants to some of the available problems and techniques in this exciting area of research, to see connections between them, and to have fun working on some open problems together.

17-21 May 2021

• Viresh Patel (organiser)
• Guus Regts (organiser)

• Alexander Barvinok*
• Yufei Zhao*
• Will Perkins*
• Jason Brown*
• Andreas Galanis*
• Ewan Davies
• Matthew Jenssen
• Péter Csikvári
• Mohan Ravichandran
• Heng Guo
• Ferenc Bencs
• David de Boer
• Pjotr Buys
• Jeroen Huijben
• Mehmet Akif Yildiz

*denotes speaker

Registration details: contact organisers by email expressing your interest and mention whether you would like to submit an open problem. By signing up, one commits to an active involvement in the meeting's activities, roughly 3 or 4 hours per day. There may be a cap on the number of participants.

Registration deadline: Wednesday 12 May

Submission details: see above

Submission deadline: Wednesday 12 May

1. Monday, 17 May  
  a. Talk (15:00 Barvinok) 
  b. Open problem session/group formation (17:00-18:30)
2. Tuesday, 18 May
  a. Talk (15:00 Zhao)
3. Wednesday, 19 May
  a. Talk (15:00 Perkins)
  b. Progress reports (16:00)
4. Thursday, 20 May
  a. Talk (15:00 Brown)  
5. Friday, 21 May
  a. Talk (15:00 Galanis)
  b. Progress reports/Closing (16:00-17:30)

Alexander Barvinok

Yufei Zhao

Will Perkins

Jason Brown

Andreas Galanis