KAIST Discrete Math Seminar


Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.
  • Masao Ishikawa (石川雅雄), Refined Enumeration Problems of Totally Symmetric Self-Complementary Plane Partitions

    Refined Enumeration Problems of Totally Symmetric Self-Complementary Plane Partitions
    Masao Ishikawa (石川雅雄)
    Dept. of Mathematics, Tottori University, Koyama, Japan.
    2008/02/21 Thu, 3PM-4PM

    In this talk we give Pfaffian or determinant expressions and constant term identities for the conjectures in the paper “Self-complementary totally symmetric plane partitions” (J. Combin. Theory Ser. A 42, (1986), 277 – 292) by W.H. Mills, D.P. Robbins and H. Rumsey. These conjectures are about weighted enumerations of certain plane partitions and have been open more than 20 years. We also settle a weak version of Conjecture in the paper, i.e., the number of shifted plane partitions invariant under a certain involution is equal to the number of alternating sign matrices invariant under the vertical flip.

  • Kyomin Jung (정교민), Approximate Inference Algorithms for Doubling Dimensional Graphs and Minor Excluded Graphs

    Approximate Inference Algorithms for Doubling Dimensional Graphs and Minor Excluded Graphs
    Kyomin Jung (정교민)
    Dept. of Mathematics, MIT, Cambridge, USA.
    2008/01/29 Tue, 4PM-5PM

    A Markov Ramdom Fields(MRF) is an n-dimensional random variable defined on a graph G such that the probability distribution of each node(assigned with one random variable) depends only on the value of its negihbors. Application of MRF includes Ising model in statistical physics, statistical language modelling in linguistics, and vision and graphics in computer science.

    We present a new local approximation algorithm for computing MAP(Maximum a-posteriori) assignemt and log-partition function for arbitrary exponential family distribution represented by a pair-wise MRF. Our algorithm is based on decomposition of G into appropriately chosen small components; computing estimates locally in each of these components and then producing a global solution. Specifically, we show that if the underlying graph G either has finite doubling dimension or excludes some finite-sized graph as its minor (e.g. Planar graph) and has a finite degree bound, then our algorithm will produce solution for both questions within arbitrary accuracy. The running time of the algorithm is Theta(n) (n is the number of nodes in G), with constant dependent on accuracy and either doubling dimension or, maximum vertex degree and the size of the graph that is excluded as a minor (e.g. 3 for all Planar graphs).

    As a (somewhat unexpected) consequence of our algorithmic result, we show that the normalized log-partition function (known as free-energy) for a class of regular MRFs (e.g. Ising model on 2-dimensional grid) will converge to a limit, that is computable, as the size of the MRF goes to infinity. This method may be of interest in its own right.

    This work is a joint work with Devavrat Shah and appeared in NIPS(The Neural Information Processing Systems) 2007.

    Tags:

Monthly Archives