Archive for the ‘2010’ Category

HwanChul Yoo (유환철), Triangulations of Product of Simplices and Tropical Oriented Matroid

Monday, November 15th, 2010
Triangulations of Product of Simplices and Tropical Oriented Matroid
HwanChul Yoo (유환철)
Department of Mathematics, MIT
2010/12/22 Wed 4:30PM-5:30PM (Room 3433)

In 2006 at MSRI, nine tropical geometers and combinatorialists met and announced the list of ten key open problems in (algebraic and combinatorial side of) tropical geometry. Axiomatization of tropical oriented matroids was one of them. After the work of Develin and Sturmfels, tropical oriented matroids were conjectured to be in bijection with subdivisions of product of simplices as well as with tropical pseudohyperplane arrangements. Ardila and Develin defined tropical oriented matroid, and showed one direction that tropical oriented matroids encode subdivision of product of simplices. Recently, in joint work with Oh, we proved that every triangulation of product of simplices encodes a tropical oriented matroid.

In this talk, I will give a survey on this topic, and discuss this well known conjecture. I will also suggest a new class of combinatorial objects that may describe all subdivisions of a bigger class of polytopes.

(CS Colloquium) David Eppstein, Graph algorithms in computational geometry

Monday, October 18th, 2010
Graph algorithms in computational geometry
David Eppstein
University of California, Irvine, CA, USA
2010/12/13 Mon 4:00PM-5:30PM (CS Bldg., Room 1501)

TBA. This is a colloquium of department of computer science.

Xavier Goaoc, Helly numbers and nerve theorems

Monday, October 18th, 2010
Helly numbers and nerve theorems
Xavier Goaoc
LORIA, INRIA Nancy – Grand Est, Villers-Lès-Nancy cedex, France.
2010/12/10 Fri 4PM-5PM

The Helly number of a collection of sets is the size of its largest inclusionwise minimal subfamily with empty intersection. The precise conditions that lead to bounded Helly numbers have been studied since the 1920’s, when Helly showed that the Helly number of any collection of compact convex sets in Rd has Helly number at most d+1.

I will discuss a proof that any collection of subsets of Rd where the intersection of any subfamily consists of at most r connected components, each of which is contractible, has Helly number at most r(d+1). I will show how this implies, in a unified manner, quantitative bounds for several Helly-type theorems in geometric transversal theory.

Our main ingredients are a new variant of the nerve, a “homological nerve theorem” for this structure and an extension of a projection theorem of Kalai and Meshulam.

This is joint work with Eric Colin de Verdiere and Gregory Ginot.

Heesung Shin (신희성), On q-enumeration of permutations

Sunday, October 17th, 2010
On q-enumeration of permutations
Heesung Shin (신희성)
Department of Mathematics, POSTECH, Pohang, Korea
2010/11/19 Fri 4PM-5PM
Laguerre histories are certain colored Motzkin paths with some weight for each elementary steps. In this talk, we study two famous bijections between permutations and Laguerre histories, made by Francon-Viennot and Foata-Zeilberger. This two bijections are enable us to give permutations as combinatorial interpretations of continued fractions. The former is associated in linear statistics and the latter be in cyclic statistics. Using two mappings, we are able to make various results about several statistics of permutations.

Greg Markowsky, Distance-Regular Graphs and Potential Theory

Saturday, October 9th, 2010
Distance-Regular Graphs and Potential Theory
Greg Markowsky
Pohang Mathematics Institute, POSTECH, Pohang, Korea
2010/11/4 Thu 4PM-5PM (Room 3433)

The study of electric potentials on graphs has a close connection with probability theory. On distance-regular graphs the theory is particularly elegant, as known results concerning such graphs allow explicit calculations to be made. In this talk, I will introduce these topics and discuss some recent results that Jacobus Koolen and I have obtained, as well as some conjectures and open problems.