Department of Mathematical Sciences, KAIST

## Archive for the ‘2011’ Category

### Shishuo Fu, A conjecture on the (q,t)-binomial coefficients

Wednesday, September 7th, 2011A conjecture on the (q,t)-binomial coefficients

Shishuo Fu

Department of Mathematical Sciences, KAIST

Department of Mathematical Sciences, KAIST

2011/09/23 Fri 4PM-5PM

In one of their joint papers, Victor Reiner and Dennis Stanton introduced a (q,t)-generalization of the binomial coefficient. There was an interesting conjecture for the cases when q≤-2 is a negative integer. In this talk, I will prove this conjecture and try to give some combinatorial sense using integer partitions.

### Andreas Holmsen, Convex representations of Oriented Matroids

Thursday, September 1st, 2011Convex representations of Oriented Matroids

Andreas Holmsen

Department of Mathematical Sciences, KAIST

Department of Mathematical Sciences, KAIST

2011/09/16 Fri 4PM-5PM

Many combinatorial problems and arguments concerning finite point sets in the Euclidean plane (or higher dimensions) often do not use the linear structure. A more general concept is that of an Oriented Matroid (OM). It is well-known that every OM can realized by pseudolines, and in fact most oriented matroids can not be realized by straight lines.

Recently, Alfreod Hubard (Courant Institute) and myself have found a new way to represent an OM by convex sets which retains much more of the “straightness” of the Euclidean plane. Interestingly, in our model the isotopy conjecture holds in a very strong sense, and it unifies several aspects of pseudoline arrangements.

Recently, Alfreod Hubard (Courant Institute) and myself have found a new way to represent an OM by convex sets which retains much more of the “straightness” of the Euclidean plane. Interestingly, in our model the isotopy conjecture holds in a very strong sense, and it unifies several aspects of pseudoline arrangements.

### Maryam Verdian-Rizi, Toroidal triangulations with few odd degree vertices

Saturday, July 16th, 2011 Toroidal triangulations with few odd degree vertices

Maryam Verdian-Rizi

Department of Mathematics, Simon Fraser University, Vancouver, Canada

Department of Mathematics, Simon Fraser University, Vancouver, Canada

2011/8/11 Thu 4PM-5PM

We present a simple geometric description for the set of toroidal triangulations with two odd vertices where each vertex has degree five or more. Each such triangulation is described by a cut-and-glue construction starting from an infinite triangular grid. To achieve that, we define some invariants to study the cycles of toroidal triangulations. The motivation for studying such family comes from Fisk triangulations and Grünbaum coloring, which will be discussed as well.

### June Huh (허준이), Characteristic polynomials and the Bergman fan of matroids

Thursday, July 14th, 2011Characteristic polynomials and the Bergman fan of matroids

June Huh (허준이)

Department of Mathematics, University of Michigan, Ann Arbor, USA

Department of Mathematics, University of Michigan, Ann Arbor, USA

2011/7/28 Thu 4PM-5PM

Let V be a subvariety of the complex projective space. The amoeba of V is the set of all real vectors log|x| where x runs over all points of V in the complex torus. The asymptotic behavior of the amoeba is given by a polyhedral fan called the Bergman fan of V. We use the tropical geometry of the Bergman fan to prove the log-concavity conjecture of Rota and Welsh over any field. This work is joint with Eric Katz and is based on arXiv:1104.2519.

### Eric Vigoda, Improved bound on the phase transition for independent sets in the square lattice

Wednesday, July 13th, 2011Improved bound on the phase transition for independent sets in the square lattice

Eric Vigoda

College of Computing, Georgia Institute of Technology, Atlanta, USA

College of Computing, Georgia Institute of Technology, Atlanta, USA

2011/7/14 Thu 4PM-5PM (Room 3433, Bldg. E6-1)

The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science.

In this model, each independent set I in a graph G is weighted proportionally to λ

We focus on the well-studied particular case of the square lattice Z

This is joint work with Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, and Linji Yang. A preprint is available from the arXiv at: arxiv:1105.0914

In this model, each independent set I in a graph G is weighted proportionally to λ

^{|I|}, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree Δ≥3, is a well known computationally challenging problem. More concretely, let λ_{c}(T_{Δ}) denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite Δ-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified λ_{c}(T_{Δ}) as a threshold where the hardness of estimating the above partition function undergoes a computational transition.We focus on the well-studied particular case of the square lattice Z

^{2}, and provide a new lower bound for the uniqueness threshold, in particular taking it well above λ_{c}(T_{4}). Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to Z^{2}we prove that strong spatial mixing holds for all λ<2.3882, improving upon the work of Weitz that held for λ<27/16=1.6875. Our results imply a fully-polynomial*deterministic*approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution.This is joint work with Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, and Linji Yang. A preprint is available from the arXiv at: arxiv:1105.0914