Department of Mathematics, Shanghai Jiao Tong University, Shanghai, China

## Archive for the ‘2015’ Category

### Yaokun Wu, Graph dynamical systems: Some combinatorial problems related to Markov chains

Tuesday, July 28th, 2015Department of Mathematics, Shanghai Jiao Tong University, Shanghai, China

### Andreas Galanis, Approximately Counting H-Colorings is #BIS-Hard

Thursday, June 25th, 2015Department of Computer Science, University of Oxford, Oxford, UK

*Mon 11AM-12PM*

We show that if H is any fixed graph without trivial components, then the problem is as hard as the well-known problem #BIS, which is the problem of (approximately) counting independent sets in a bipartite graph. #BIS is a complete problem in a important complexity class for approximate counting, and is widely believed not to have an FPRAS. If this is so, then our result shows that for every graph H without trivial components, the H-coloring counting problem has no FPRAS.

This problem was studied a decade ago by Goldberg, Kelk and Paterson. They were able to show that approximately sampling H-colorings is #BIS-hard, but it was not known how to get the result for approximate counting. Our solution builds on non-constructive ideas using the work of Lovasz.

Joint work with Leslie Goldberg and Mark Jerrum.

### [Lecture Series] Johann Makowsky, Graph Polynomials

Wednesday, June 17th, 2015Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel

Lecture 2: 2015/07/21 Tue 3:30PM-5:10PM

Lecture 3: 2015/07/22 Wed 3:30PM-5:10PM

Room: E6-1, Room 2412

We introduce the most prominent graph polynomials (characteristic, Laplacian, chromatic, matching, Tutte) and discuss how to compare them.

Lecture 2: Why is the Chromatic Polynomial a Polynomial?

We give an alternative proof for the fact that the chromatic polynomial is indeed a polynomial. From this we introduce generalized chromatic polynomials, and show that this actually represents the most general case; Every (reasonably defined) graph polynomial can be represented as a generalized chromatic polynomial.

Lecture 3: Hankel matrices and Graph Polynomials.

We introduce Hankel matrices of graph paramaters, which generalize Lovasz’ connection matrices. We show that many (but not all) graph polynomials have Hankel matrices of finite rank. We show how to use the Finite Rank Property to show definability/non-definability of graph parameters/polynomials in Monadic Second Order Logic.

### Ae Ja Yee (이애자), Partitions associated with three third order mock theta functions

Wednesday, June 17th, 2015Department of Mathematics, The Pennsylvania State University, University Park, PA, USA

### Charilaos Efthymiou, A Simple Algorithm for Sampling Colourings of G(n, d/n) Up to Gibbs Uniqueness Threshold

Friday, May 29th, 2015Uniqueness Threshold

Georgia Institute of Technology, Atlanta, GA, USA

**10 Wed**4PM-5PM

studied problem in computer science, discrete mathematics and

statistical physics. It amounts to constructing a k-colouring of G

which is distributed close to Gibbs distribution in polynomial time.

In this talk, we deal with the problem when the underlying graph is an

instance of Erdos-Renyi random graph G(n,d/n), where d is fixed. In

this paper we propose a novel efficient algorithm for approximate

random k-colouring G(n,d/n). To be more specific, with probability at

least 1-n

^{-Ω(1)}over the input instances G(n,d/n) and for kgeq

(1+ε)d, the algorithm returns a k-colouring which is distributed

within total variation distance n

^{-Ω(1)}from the Gibbs

distribution of the input graph. The algorithm we propose is neither a

MCMC one nor inspired by the message passing algorithms proposed by

statistical physicists. Roughly the idea is as follows: Initially we

remove sufficiently many edges of the input graph. This results in a

graph which can be coloured randomly efficiently. Then we move back

the removed edges one by one. Every time we add an edge we update the

colouring of the graph, with the new edge, so that the colouring

remains (sufficiently) random. The performance depends heavily on

certain spatial correlation decay properties of the Gibbs

distribution.