Combinatorics of Intervals

Central European University
8.4K
531 views
Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Apr 14, 2015

Speaker: András Gyárfás (Rényi Institute)

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?

When autoplay is enabled, a suggested video will automatically play next.

Up next

to add this to Watch Later

Add to