JohannMakowsky

Archive of posts with tag 'JohannMakowsky'

  • Johann A. Makowsky, The Complexity of Counting Generalized Colorings: New Results and Challenges
    The Complexity of Counting Generalized Colorings: New Results and Challenges
    Johann A. Makowsky
    Faculty of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
    2017/07/14 Fri 4PM-5PM
    Let P be a graph property. We look at graph colorings with k colors where each color class induces a graph satisfying P. By a result of Makowsky and Zilber (2005) the number of such colorings ?P(G;k) is a polynomial in k. We present recent results and open problems on the complexity of evaluating ?P(G;λ) for various properties P and (not only integer) values of λ.
    This is joint work with A. Goodall, M. Hermann, T. Kotek and S. Noble which was initiated during last year’s program “Counting Complexity and Phase Transitions”. See also arXiv:1701.06639v1.
    Tags:

  • [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:

Monthly Archives