Combinatorics Seminar 2019

Date: Fri, May 24, 2019

Time: 10:45 - 11:15

Venue: Room 630

Title: Up and down in a tree

Abstract:

Let $(V,2^V,P)$ be a discrete probability space. Consider a rooted tree $T$ with vertex set $V$ and root $r$. A subset $D$ of $V$ is called $T$-down if $d\in D$ implies that all the vertices which do not lie in the same component of $T-d$ with $r$ fall into $D$. For every positive integer $k$, we show that there is either a set $U$ such that $P(U)\geq \frac{1}{2k-1}$ and $U$ induces a path with $r$ as one endpoint, or there are $k$ disjoint $T$-down subsets $D_1,\ldots,D_k$ such that $P(D_1)\geq \cdots \geq P(D_k)\geq \frac{1}{2k-1}$. Related results and questions will also be discussed.

Ongoing joint work with Yaokun Wu.

Webmaster