Combinatorics of Intervals

Type: 
PhD Student Seminar
Audience: 
Open to the Public
Building: 
Zrinyi u. 14
Room: 
310/A
Wednesday, March 18, 2015 - 2:00pm
Add to Calendar
Date: 
Wednesday, March 18, 2015 - 2:00pm

Abstract:

Assume that J is a set of intervals on the real line. The following
two important minimax theorems have been discovered by Tibor Gallai.

1. minimum number of partition classes of J into pairwise disjoint
intervals = maximum number of pairwise intersecting members of J

2. minimum number of points piercing all members of J = maximum number
of pairwise disjoint members of J

What happens if J is replaced by other structures? By subtrees of a
tree? By arcs of a circle? By boxes? By intervals of the plane?