# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, June 29, 2009

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
10623 Berlin

Lecture - 14:15

### Segment Orders

Abstract:
We study two classes of partial orders defined in a natural way from a family of line segments in the plane. Shahroki asked whether either class contains orders of large dimension. We answered this question in the affirmative by showing that both classes contain the "standard examples", i.e., the poset consisting of the 1-element and n-1 element subsets of the set of the first n positive integers. We also showed that both classes contain all interval orders.
On the other hand, it is straightforward to show that both classes contain all orders having dimension at most 3, and that for fixed t at least 4, almost no orders of dimension t belong to either class.
These results suggest that the classes might in fact be the same, but efforts to establish - or contradict - this assertion have not been successful to date. And there is reason to believe that an order belonging to one class and not the other may be very, very large,
This is joint work with Csaba Biro.

Colloquium - 16:00

### Tree reconstruction and other combinatorial aspects of evolution

Abstract:
I provide a brief overview of how combinatorial techniques have become useful in studying some basic questions arising in evolutionary biology. One purely mathematical problem I will discuss is the following: we have a sequence of discrete states that have evolved independently on some unknown tree by a simple markov process, and we wish to reconstruct the underlying leaf-labeled tree. How long do the sequences need to be so that our estimate is correct with high probability? And in particular, how fast does the sequence length need to grow as a function of the number n of vertices of the tree? We contrast this "reconstruction" question with a corresponding "testing" question: Is the required rate of sequence length growth with n lower if we are given a candidate tree and wish to merely "test" it by asking: Is this the tree that produced the sequences?

Letzte Aktualisierung: 17.06.2009