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
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
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?