Seminars in July 2012

  • Jang Soo Kim (김장수), Proofs of Two Conjectures of Kenyon and Wilson on Dyck Tilings
    Proofs of Two Conjectures of Kenyon and Wilson on Dyck Tilings
    Jang Soo Kim (김장수)
    School of Mathematics, University of Minnesota, Minneapolis, MN, USA
    2012/7/27 Fri 4PM-5PM
    Recently, Kenyon and Wilson introduced a certain matrix M in order to compute pairing probabilities of what they call the double-dimer model. They showed that the absolute value of each entry of the inverse matrix M-1 is equal to the number of certain Dyck tilings of a skew shape. They conjectured two formulas on the sum of the absolute values of the entries in a row or a column of M-1. In this talk we prove the two conjectures. As a consequence we obtain that the sum of the absolute values of all entries of M-1 is equal to the number of complete matchings. We also find a bijection between Dyck tilings and complete matchings.
    This talk is based on the following paper: arxiv:1108.5558.
    Tags:

  • Choongbum Lee (이중범), Self-similarity of graphs
    Self-similarity of graphs
    Choongbum Lee (이중범)
    Department of Mathematics, UCLA, Los Angeles, USA
    2012/7/4 Wed 4PM-5PM (Bldg. E6-1, Room 3433)

    An old problem raised independently by Jacobson and Schönheim asks to determine the maximum s for which every graph with m edges contains a pair of edge-disjoint isomorphic subgraphs with s edges. We determine this maximum up to a constant factor and show that every m-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least c (m log m)2/3 edges for some absolute constant c, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erdős, Pach, and Pyber from 1987.
    Joint work with Po-Shen Loh and Benny Sudakov.

    Tags:

Monthly Archives