## Research Interests

Cover Graphs and Order Dimension |

I am interested in the question: Which properties of a cover graph bound the dimension of the corresponding poset? A quite new direction here is to find connections between structural graph parameters and order dimension. Joret et al. showed the dimension of a poset is bounded in terms of its height and the treewidth of its cover graph. They also mention that bounding both the height and the treewidth is necessary to bound the dimension. But in the case of treewidth 2 it might be that this already implies a bounded dimension (i.e. without bounding the height). This is a nice problem. |

Balanced Pairs and the 1/3-2/3 conjecture |

Kislitsyn conjectured that every partial order (that is not a linear order) has different elements x and y such that the fraction of linear extensions of the poset in which x is smaller than y is between 1/3 and 2/3. This has been proven for some classes of posets like height-2 posets, width-2 posets and semiorders. But in general it is still wide open. In a very nice paper David Eppstein generalized the conjecture to basic words of antimatroids and gave evidence to do so. In my masterthesis i considered antimatroids that are defined by the perfect elimination orderings of a chordal graph. |

On-line coloring algorithms |

It is well known that there are no competitive on-line coloring algorithms for bipartite graphs. So it is maybe more interesting to ask for on-line coloring algorithms that use not many colors compared to the best on-line (instead of off-line) algorithm. Such algorithms are called on-line-competitive and i like the question whether such exist for bipartite graphs. |