# Networks Workshop on Random Graphs, Counting and Sampling

The problem of finding efficient approximation algorithms for counting different types of combinatorial objects is a very active area of research in theoretical computer science.

## 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.

## Organizers

Viresh Patel University of Amsterdam

Leen Stougie Vrije Universiteit Amsterdam

## Speakers

Martin Dyer University of Leeds, UK

Catherine Greenhill University of New South Wales, Australia

Pieter Kleer CWI, Amsterdam

Matteo Sfragara Leiden University

## Schedule

13:30 Matteo Sfragara

14:15 Martin Dyer

15:00 Coffee and tea

15:30 Catherine Greenhill

16:15 Pieter Kleer

17:00 Drinks

## Registration

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

## Titles and abstracts

**Martin Dyer - University of Leeds, UK**

**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 - University of New South Wales, Australia**

**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.

**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 - Leiden University**

**Title:** Spectra of Adjacency and Laplacian Matrices of Inhomogeneous Erdos-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

## More information