Organisers: Viresh Patel and Leen Stougie

Location: CWI, Science Park 123, 1098 XG Amsterdam, lecture room L120.

Registration is free of charge, expressing your intention to attend is highly appreciated by using the electronic registration form here.

Topic

A main theme of the workshop concerns efficient approximation algorithms for counting different types of combinatorial objects. By considering the appropriate generating functions, the problem naturally extends to that of approximately evaluating corresponding partition functions and this in turn has close connections to phase transitions in statistical physics. One approach to the sampling (and hence also to the counting) problem is through suitably defining Markov chains on the space of all the objects to be sampled and then to show that this chain mixes rapidly. This brings together ideas from combinatorics, probability, algorithms, and statistical physics. A second closely related theme is that of random graphs and their typical properties, another very active area of research in probability and discrete mathematics.

Speakers

Martin Dyer (University of Leeds, UK)

Catherine Greenhill (University of New South Wales, Sydney)

Pieter Kleer (CWI, Amsterdam)

Matteo Sfragara (University of Leiden)

Program

13:30 Matteo Sfragara

14:15 Martin Dyer

15:00 Coffee / tea

15:30 Catherine Greenhill

16:15 Pieter Kleer

17:00 Drinks

Titles and abstracts

Martin Dyer

Title: *Counting independent sets in (fork,odd hole)-free graphs*

Abstract: Jerrum, Sinclair and Vigoda showed that the permanent of any square matrix can be estimated in polynomial time. This can be viewed as approximating the partition function of edge-weighted matchings in a bipartite graph. Equivalently, this may be viewed as approximating the partition function of vertex-weighted independent sets in the line graph of a bipartite graph. Line graphs of bipartite graphs are known to be precisely the class of (claw,diamond,odd hole)-free graphs. So how far does the result of Jerrum, Sinclair and Vigoda extend? We first show that it extends to all (claw,odd hole)-free graphs, and then show that it extends to the even larger class of (fork,odd hole)-free graphs.

(Joint work with Mark Jerrum, Haiko Müller and Kristina Vušković.)

Catherine Greenhill

Title: *Approximately counting independent sets in graphs with bounded bipartite pathwidth*

Abstract: In 1989, Jerrum and Sinclair showed that a natural Markov chain for counting matchings in a given graph G is rapidly mixing. This chain can equivalently be viewed as counting independent sets in line graphs. We generalise their approach to the class of all graphs with the following property: every bipartite induced subgraph of G has pathwidth at most p. Here p is a positive integer and the mixing time of the Markov chain will depend on p. We also describe two classes of graphs (described in terms of forbidden induced subgraphs) that satisfy this condition. Both of these classes generalise the class of claw-free graphs.

Pieter Kleer

Title: *The switch Markov chain for generating regular graphs with a partition constraint*

Abstract: The switch Markov chain is a simple procedure to randomize network topologies while preserving the degree sequence of the network. It proceeds by uniformly at random selecting two edges, and switching them if this is possible. For d-regular graphs, it is known that a polynomial number of switch suffices to get an almost uniform sample from the set of all d-regular graphs. In this work we consider an extension of the problem where, given some partition of the nodes into two parts, it is also specified how much edges there should be between the two parts of the partition, i.e., we are interested in d-regular graphs with a partition constraint. This is a special case of the joint degree matrix problem. In this talk, we show that a polynomial number of switches suffices to get d-regular graph, satisfying the partition constraint, which is close to being a uniform sample from the set of all graphs with the given partition constraint.

Matteo Sfragara

Title: *Spectrum of Adjacency and Laplacian Matrices of Inhomogeneous Erdős-Rényi Random Graphs*

Abstract: In homogeneous Erdős-Rényi random graphs **G_***N* on *N* vertices in the non-dense regime are considered in this talk. The edge between the pair of vertices {*i, j*} is retained with probability ε_*N f*(*i*/*N* ,* j*/*N*), 1≤*i*=*j*≤*N*, independently of other edges, where *f*: [0,1]x[0,1] → [0,∞) is a continuous function such that *f*(*x*,*y*) = *f*(*y*,*x*) for all *x*, *y* ∈ [0,1]. We study the empirical distribution of the adjacency matrix *A*_*N* associated with **G**_*N* in the limit as *N* → ∞ when lim_(*N*→∞) ε_*N*= 0 and lim_(*N*→∞) *N*ε_*N*=∞. In particular, it is shown that the empirical spectral distribution of *A*_*N*, after appropriate scaling and centering, converge to deterministic limits weakly in probability. For the special case where *f*(*x*, *y*) = *r*(*x*)*r*(*y*) with *r*: [0,1]→[0,∞) a continuous function, we give an explicit characterization of the limiting distribution. Furthermore, applications of the results to Chung-Lu random graphs and social networks are shown.

**Support:**We gratefully acknowledge funding from Networks