Seminars in October 2011

  • Hans L. Bodlaender, Algorithms on Tree Decompositions and Time Improvements
    Algorithms on Tree Decompositions and Time Improvements
    Hans L. Bodlaender
    Institute of Information and Computing Sciences, Utrecht University, The Netherlands
    2011/10/31 Mon 4PM-5PM
    Many problems that are intractable on general graphs become linear time solvable on graphs of bounded treewidth. The constant factor however of such algorithms is exponential or worse in the treewidth of the tree decomposition that is used. In this talk, a number of known and some new results are surveyed. In particular, it is shown how speed improvements can be obtained using convolutions, and how a recent technique called “cut-and-count” can be used to obtain fast probabilistic algorithms for problems like Hamiltonian Circuit.
    Tags:

  • Jiang Zeng, Permutation Statistics on Signed Permutation Groups
    Permutation Statistics on Signed Permutation Groups
    Jiang Zeng
    Institut Camille Jordan, Université Claude Bernard Lyon-I, France
    2011/10/19 Wed 4PM-5PM (Room 3433)
    We generalize two bijections due to Garsia and Gessel to compute the generating functions of the two vector statistics (desG, maj, ℓG, col) and (desG, idesG, maj, imaj, col, icol) over the wreath product of a symmetric group by a cyclic group. Here desG, ℓG, maj, col, idesG, imajG, and icol denote the number of descents, length, major index, color weight, inverse descents, inverse major index, and inverse color weight, respectively. Our main formulas generalize and unify several known identities due to Brenti, Carlitz, Chow-Gessel, Garsia-Gessel, and Reiner on various distributions of statistics over Coxeter groups of type A and B.
    Tags:

  • Edward D. Kim, On Diameters of Transportation and Network Flow Polytopes
    On Diameters of Transportation and Network Flow Polytopes
    Edward D. Kim
    Department of Mathematics, POSTECH, Pohang
    2011/10/14 Fri 4PM-5PM
    Transportation and network polytopes are classical objects in operations research. In this talk, we focus on recent advances on the diameters of several classes of transportation polytopes, motivated by the efficiency of the simplex algorithm. In particular, we discuss results on 2-way transportation polytopes, including a recent result of Stougie and report on joint work with Bruhn-Fujimoto and Pilaud, concerning 2-way transportation polytopes with a certain support structure. We also present a bound on 3-way transportation polytopes in joint work with De Loera, Onn, and Santos. To conclude, we discuss avenues for future work on transportation polytopes and their diameters.
    Tags:

  • Michael Dobbins, Realizability of Antiprisms
    Realizability of Antiprisms
    Michael Dobbins
    Department of Mathematical Sciences, KAIST
    2011/10/7 Fri 4PM-5PM
    If one draws the Hasse diagram for the face lattice of a polytope, this may appear to be the 1-skeleton of some other polytope. In 1971 Lindström asked whether the intervals of a polytope’s face lattice ordered by containment can be realized as the face lattice of another polytope. If so, this would be the polytope appearing the Hasse diagram. In this talk, I will give necessary and sufficient conditions for the intervals of a polytope’s face lattice to be realizable, and I will provide a counter example showing that not every polytope satisfies these conditions.
    Tags:

Monthly Archives