Posts Tagged ‘colloquium’

Newer Entries »

(Colloquium) Carsten Thomassen, Rendezvous numbers and von Neumann’s min-max theorem

Wednesday, March 24th, 2010
FYI (Department Colloquium)
Rendezvous numbers and von Neumann’s min-max theorem
Carsten Thomassen
Department of Mathematics, Technical University of Denmark, Lyngby, Denmark
2010/04/01 Thursday 4:30PM-5:30PM (Room 1501)

A rendezvous number for a metric space M is a number a such that, for every finite subset Q of M, there is an element p in M, such that the average distance from p to the elements in Q is a.

O. Gross showed in 1964 that every compact connected metric space has precisely one rendezvous number. This result is a consequence of von Neumann’s min-max theorem in game theory.

In an article in the American Math. Monthly 93(1986) 260-275, J. Cleary and A. A. Morris asked if a (more) elementary proof of Gross’ result exists.

In this talk I shall formulate a min-max result for real matrices which immediately implies these results of Gross and von Neumann.

The proof is easy and involves only mathematical induction.

Tags:,
Posted in 2010, KAIST Discrete Math Seminar | Comments Closed

(Colloquium) Ken-ichi Kawarabayashi, The disjoint paths problem: Algorithm and Structure

Monday, November 9th, 2009
FYI (Department Colloquium)
The disjoint paths problem: Algorithm and Structure
Ken-ichi Kawarabayashi (河原林 健一)
National Institute of Informatics, Tokyo, Japan.
2009/11/26 Thursday 4:30PM-5:30PM (Room 1501)

In this talk, we shall discuss the following well-known problem, which
is called the disjoint paths problem.

Given a graph G with n vertices and m edges, k pairs of vertices (s1,t1),(s2,t2),…,(sk,tk) in G (which are sometimes called terminals). Are there disjoint paths P1,…,Pk in G such that Pi joins si and ti for i=1,2,…,k?

We discuss recent progress on this topic, including algorithmic aspect of the disjoint paths problem.

We also discuss some structure theorems without the k disjoint paths. Topics include the uniquely linkage problem and the connectivity function that guarantees the existence of the k disjoint paths.

Tags:,
Posted in 2009, KAIST Discrete Math Seminar | Comments Closed

(Colloquium) Paul Seymour, Well-quasi-ordering tournaments and Rao’s degree-sequence conjecture

Saturday, May 16th, 2009
FYI (Department Colloquium)
Well-quasi-ordering tournaments and Rao’s degree-sequence conjecture
Paul Seymour
Department of Mathematics, Princeton University, Princeton, New Jersey, USA.
2009/5/21 Thursday 4:30PM-5:30PM (Room 1501)

Rao conjectured about 1980 that in every infinite set of degree sequences (of graphs), there are two degree sequences with graphs one of which is an induced subgraph of the other. We recently found a proof, and we sketch the main ideas.

The problem turns out to be related to ordering digraphs by immersion (vertices are mapped to vertices, and edges to edge-disjoint directed paths). Immersion is not a well-quasi-order for the set of all digraphs, but for certain restricted sets (for instance, the set of tournaments) we prove it is a well-quasi-order.

The connection between Rao’s conjecture and digraph immersion is as follows. One key lemma reduces Rao’s conjecture to proving the same assertion for degree sequences of split graphs (a split graph is a graph whose vertex set is the union of a clique and a stable set); and to handle split graphs it helps to encode the split graph as a directed complete bipartite graph, and to replace Rao’s containment relation with immersion.

(Joint with Maria Chudnovsky, Columbia)

Tags:,
Posted in 2009, KAIST Discrete Math Seminar | Comments Closed

Newer Entries »