Seminars in April 2010

  • Jang Soo Kim (김장수), Combinatorics on permutation tableaux
    Combinatorics on permutation tableaux
    Jang Soo Kim (김장수)
    Laboratoire d’Informatique Algorithmique: Fondements et Applications (LIAFA), University of Paris 7, France
    2010/4/26 Mon 3PM-4PM (Room: 3433, Bldg E6-1)

    A permutation tableau is a relatively new combinatorial object introduced by Postnikov in his study of totally nonnegative Grassmanian. As one can guess from its name, permutation tableaux are in bijection with permutations. Surprisingly, there is also a connection between permutation tableaux and a statistical physics model called PASEP (partially asymmetric exclusion process). In this talk, we study some combinatorial properties of permutation tableaux. One of our result is a sign-imbalace formula for permutation tableaux which is very similar to the sign-imbalace formula for standard Young tableaux conjectured by Stanley.

    Tags:

  • Woong Kook (국웅), A Combinatorial Formula for Information Flow in a Network
    A Combinatorial Formula for Information Flow in a Network
    Woong Kook (국웅)
    Department of Mathematics, University of Rhode Island, Kingston, Rhode Island, U.S.A.
    2010/04/09 Fri 4PM-5PM

    In 1989, Stephenson and Zelen derived an elegant formula for the information Iab contained in all possible paths between two nodes a and b in a network, which is described as follows. Given a finite weighted graph G and its Laplacian matrix L, the combinatorial Green’s function \mathcal{G}, of G is the inverse of L+J, where J is the all 1’s matrix. Then, it was shown that Iab=(gaa+gbb-2gab)-1, where gij is the (i,j)-th entry of \mathcal{G}. In this talk, we prove an intriguing combinatorial formula for Iab:

    I_{ab}=\kappa(G)/\kappa(G_{a\ast b}),

    where \kappa(G) is the complexity, or tree-number, of G, and Ga*b is obtained from G by identifying two vertices a and b. We will discuss several implications of this new formula, including the equivalence of Iab and the effective conductance between two nodes in electrical networks.

    Tags:

  • Carsten Thomassen, On the Number of Spanning Trees, Orientations, and Cycles
    On the Number of Spanning Trees, Orientations, and Cycles
    Carsten Thomassen
    Department of Mathematics, Technical University of Denmark, Lyngby, Denmark
    2010/04/02 Friday 4PM-5PM (Room: 3433, Bldg E6-1)

    One of the most fundamental properties of a connected graph is the existence of a spanning tree. Also the number τ(G) of spanning trees is an important graph invariant. It plays a crucial role in Kirchhoff’s classical theory of electrical networks, for example in computing driving point resistances. More recently, τ(G) is one of the values of the Tutte polynomial which now plays a central role in statistical mechanics. So are a(G), the number of acyclic orientations, and c(G), the number of orientations in which every edge is in a directed cycle. As a first step towards convexity properties of the Tutte polynomial, Merino and Welsh conjectured that

    τ(G) ≤ max{a(G),c(G)}

    for every loopless and bridgeless multigraph G. We shall here prove that τ(G) ≤ c(G) for all loopless and bridgeless multigraphs with n vertices and at least 4n edges and that τ(G) ≤ a(G) for all loopless multigraphs with n vertices and at most 16n/15 edges. We also verify the conjecture for cubic graphs (which are in between these two bounds).

    Tags:

  • (Colloquium) Carsten Thomassen, Rendezvous numbers and von Neumann’s min-max theorem
    FYI (Department Colloquium)
    Rendezvous numbers and von Neumann’s min-max theorem
    Carsten Thomassen
    Department of Mathematics, Technical University of Denmark, Lyngby, Denmark
    2010/04/01 Thursday 4:30PM-5:30PM (Room 1501)

    A rendezvous number for a metric space M is a number a such that, for every finite subset Q of M, there is an element p in M, such that the average distance from p to the elements in Q is a.

    O. Gross showed in 1964 that every compact connected metric space has precisely one rendezvous number. This result is a consequence of von Neumann’s min-max theorem in game theory.

    In an article in the American Math. Monthly 93(1986) 260-275, J. Cleary and A. A. Morris asked if a (more) elementary proof of Gross’ result exists.

    In this talk I shall formulate a min-max result for real matrices which immediately implies these results of Gross and von Neumann.

    The proof is easy and involves only mathematical induction.

    Tags:

Monthly Archives