Archive for the ‘2015’ Category

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

Tuesday, July 28th, 2015
Graph dynamical systems: Some combinatorial problems related to Markov chains
Yaokun Wu
Department of Mathematics, Shanghai Jiao Tong University, Shanghai, China
2015/8/5 Wed 3PM-3:50PM
An order-t Markov chain is a discrete process where the outcome of each trial is linearly determined by the outcome of most recent t trials. The set of outcomes can be modelled by functions from a set V to a set F. The linear influences can be described as t-linear maps. When t=1, the set of linear influences can be conveniently described as digraphs on the vertex set V. Most of our talk is concerned with a combinatorial counterpart of Markov chains, where we can only tell the difference between zero probability and positive probability. We especially focus on the Boolean case, namely F is a 2-element set. This talk is to introduce several easy-to-state combinatorial problems about discrete dynamics, which arise from the combinatorial considerations of Markov chains.

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

Thursday, June 25th, 2015
Approximately Counting H-Colorings is #BIS-Hard
Andreas Galanis
Department of Computer Science, University of Oxford, Oxford, UK
2015/7/13 Mon 11AM-12PM
We consider the problem of counting H-colorings from an input graph G to a target graph H. (An H-coloring of G is a homomorphism from the graph G to the graph H.)
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, 2015
Graph Polynomials
Johann Makowsky
Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
Lecture 1: 2015/07/20 Mon 3:30PM-5:10PM
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
Lecture 1: A Landscape of Graph Polynomials.

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, 2015
Partitions associated with three third order mock theta functions
Ae Ja Yee (이애자)
Department of Mathematics, The Pennsylvania State University, University Park, PA, USA
2015/06/23 Tue 4PM-5PM
The generating function of partitions with repeated (resp. distinct) parts such that each odd part is less than twice the smallest part is shown to be the third order mock theta function ω(q) (resp. ν(-q)). Similar results for partitions with the corresponding restriction on each even part are also obtained, one of which involves the third order mock theta function φ(q). Congruences for the smallest parts functions associated to such partitions are obtained. Two analogues of the partition-theoretic interpretation of Euler’s pentagonal theorem are also obtained. This is joint work with George Andrews and Atul Dixit.

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

Friday, May 29th, 2015
A Simple Algorithm for Sampling Colourings of G(n, d/n) Up to Gibbs
Uniqueness Threshold
Charilaos Efthymiou
Georgia Institute of Technology, Atlanta, GA, USA
2015/6/10 Wed 4PM-5PM
Approximate random k-colouring of a graph G=(V,E) is a very well
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