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
