KAIST Discrete Math Seminar

Lecture 1: A Landscape of Graph Polynomials.</p>

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.

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.

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.

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

During the last decade, an active line of research in proof complexity has been the space complexity of proofs and how space is related to other complexity measures (like size, length, width, degree). Space is (roughly) how large of an erasable board one would need to show a proof line-by-line.
Here, we are interested in the space complexity of refuting 3-CNFs (formulas in conjunctive normal form with at most 3 literals per clause). We prove that a random 3-CNF with n variables requires, with high probability, Ω(n²) total space in Resolution. This is best possible up to a constant factor.
This lower bound is obtained via a variant of Hall’s Lemma which may be of independent interest. Namely, we show that in bipartite graphs G with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2-ε), for ε < 1/23.
This is joint work with Patrick Bennett, Ilario Bonacina, Nicola Galesi, Mike Molloy, and Paul Wollan.