Seminars in October 2014

  • Mamadou Moustapha Kanté, On the enumeration of minimal transversals in hypergraphs
    On the enumeration of minimal transversals
    in hypergraphs
    (a.k.a. minimal dominating sets in graphs)
    Mamadou Moustapha Kanté
    Université Blaise Pascal, France
    2014/10/28 Tuesday 4PM-5PM
    Room 1409
    A hypergraph on V is a collection E of a subsets of a ground set V. A transversal in a hypergraph H=(V,E) is a subset T of V that intersects every set in E. We are interested in an output-polynomial algorithm for listing the set (inclusion wise) minimal transversals in a given hypergraph (known as Hypergraph Dualization or Transversal Problem). An enumeration algorithm for a set C is an algorithm that lists the elements of C without repetitions; it is said output-polynomial if it can enumerate the set C in time polynomial in the size of C and the input. The Transversal problem is a fifty-year open problem and until now not so many tractable cases are known and has deep connections with several areas of computer science: dualization of monotone functions, data mining, artificial intelligence, etc.</p>

    In this talk I will review some known results. In particular I will show that the Transversal problem is polynomially reduced to the enumeration of minimal dominating sets in co-bipartite graphs. A dominating set in a graph is a subset of vertices that intersect the closed neighborhood of every vertex. This interesting connection, we hope, will help in solving the Transversal problem by bringing structural graph theory into this area. I will also review new graph classes where we obtain polynomial delay algorithm for listing the minimal dominating sets. The talk will emphasize on the known techniques rather than a listing of known tractable cases.

    Tags:

  • Matthieu Josuat-Verges, Ehrhart polynomials and Eulerian statistic on permutations
    Ehrhart polynomials and Eulerian statistic on permutations
    Matthieu Josuat-Verges
    CNRS, France
    2014/10/14 Tuesday 4PM-5PM
    Room 3433
    Consider a polytope P with integer vertices, then one can define its Ehrhart polynomial f(t) by counting integer points in t.P. After a change of basis, it becomes a polynomial with positive integer coefficients, called the h*-polynomial. It is then a problem to find the combinatorial meaning of these coefficients for special polytopes. For example, the n-dimensional hypercube gives the n-th Eulerian polynomial, counting descents in permutations. The goal of this work is to refine this result by considering slices of hypercube and considering descents and excedences in permutations, that are two different Eulerian statistics.</p>
    Tags:

  • Seungsang Oh, Enumeration of multiple self-avoiding polygons in a confined square lattice
    Enumeration of multiple self-avoiding polygons in a confined square lattice
    Seungsang Oh (오승상)
    Korea University
    2014/10/07 *Tuesday 5PM-6PM*
    Room 1409
    \mathbb{Z}_{m \times n} is the rectangle of size m \times n in the square lattice. p_{m \times n} denotes the cardinality of multiple self-avoiding polygons in \mathbb{Z}_{m \times n}. </p>

    In this talk, we construct an algorithm producing the precise value of p_{m \times n} for positive integers m,n that uses recurrence relations of state matrices which turn out to be remarkably efficient to count such polygons. $$ p_{m \times n} = \mbox{(1,1)-entry of the matrix } (X_m)^n -1$$ where the matrix X_m is defined by $$ X_{k+1} = \left( \begin{array}{cc} X_k & O_k \\ O_k & X_k \end{array}\right) \ \ \mbox{and} \ \ \ O_{k+1} = \left( \begin{array}{cc} O_k & X_k \\ X_k & 0 \end{array} \right) $$ for k=1, \cdots, m-1, with 1 \times 1 matrices X_1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) and O_1 = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right).

    Tags:

Monthly Archives