Archive for the ‘2010’ Category

Frédéric Meunier, Topological bounds for graph representations over any field

Monday, October 28th, 2019

IBS/KAIST Joint Discrete Math Seminar

Topological bounds for graph representations over any field
Frédéric Meunier
École Nationale des Ponts et Chaussées, Paris
2019/11/21 Thu 4:30PM-5:30PM, Room B232, IBS (기초과학연구원)

Haviv (European Journal of Combinatorics, 2019) has recently proved that some topological lower bounds on the chromatic number of graphs are also lower bounds on their orthogonality dimension over R. We show that this holds actually for all known topological lower bounds and all fields. We also improve the topological bound he obtained for the minrank parameter over R – an important graph invariant from coding theory – and show that this bound is actually valid for all fields as well. The notion of independent representation over a matroid is introduced and used in a general theorem having these results as corollaries. Related complexity results are also discussed.
This is joint work with Meysam Alishahi.

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.