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.

Viresh Patel and Guus Regts

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
• Tobias Müller
• Vilhelm Agdur
• Allan Lo
• Ashwin Sah
• Mehtaab Sawhney
• Cynthia Stoner
• Dingding Dong
• Nitya Mani
• Krystal Guo
• Jiaheng Wang
• Giorgos Mousa

*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. Welcome (14:55)
  b. Talk (15:00-15:45 Barvinok) 
  c. Open problem session/group formation (16:00-)
2. Tuesday, 18 May
  a. Open working sessions
  b. Talk (15:00-15:45 Zhao)
  c. Coffee break in gather.town (after talk)
3. Wednesday, 19 May
  a. Open working sessions
  b. Talk (15:00-15:45 Perkins)
  c. Progress reports (16:00)
  d. Social event in gather.town/zoom (organised by David de Boer)
4. Thursday, 20 May
  a. Open working sessions
  b. Talk (15:00-15:45 Brown)
  c. Coffee break in gather.town (after talk)
5. Friday, 21 May
  a. Talk (15:00-15:45 Galanis)
  b. Progress reports/Remaining open problems (16:00-)
  c. Closing

The zoom room for talks: https://uva-live.zoom.us/j/87839343064?pwd=M25UNmhwcnd4NURXRkI0Q09MWWdEUT09

This is a brief overview of how to compute partition functions (combinatorially defined polynomials) by interpolation. As examples, we will consider permanents of complex matrices and matching polynomials of graphs.

I will survey some problems, results, and techniques concerning tight upper bounds on the number of independent sets, proper q-colorings, and, more generally, graph homomorphisms, specifically problems of the following form: fix d and a (weighted) graph H, which d-regular graph G maximizes hom(G, H)^{1/v(G)}?

I will introduce abstract polymer models (as introduced by Kotecky and Preiss) and describe how they can be used to analyze low-temperature statistical physics models by changing perspective from a spin system at low temperature to a dilute polymer system. I will mention applications including proving zero-freeness results for polynomials, describing low temperature phase diagrams, and combinatorial and algorithmic enumeration.

Independence polynomials are generating functions for the number of independent sets of each cardinality in a graph G. In addition to encoding useful information about the graph (such as the number of vertices, the number of edges and the independence number), the analytic and algebraic properties can say much about the shape and inter-dependence of the coefficients. In this talk we focus on the nature and location of the roots of such polynomials, and even cross paths with a fractal or two! This research is joint with Ben Cameron, Iain Beaton, Karl Dilcher and Richard Nowakowski.

In this talk, we will review recent approaches to study the approximability of partition functions in the complex plane, using ideas from complex dynamics. We will focus mainly on the hard-core and Ising models, and discuss how these techniques have recently been applied to obtain strong inapproximability results for computing averages on the real line, such as the average size of independent sets or the mean magnetization in the Ising model.