Seminars in July 2015

  • [Lecture Series] Johann Makowsky, Graph Polynomials
    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.</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.

    Tags:

  • Andreas Galanis, Approximately Counting H-Colorings is #BIS-Hard
    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.
    Tags:

Monthly Archives