When: Sunday, May 30,
10am
Where: Schreiber 309
Speaker: Peleg Michaeli,
Tel Aviv University
Title:
Discrepancies of Spanning Trees
Discrepancy theory is concerned with colouring elements of a ground set so that each set in a given set system is as balanced as possible. In the graph setting, the ground set is the edge set of a given graph, and the set system is a family of subgraphs. In this talk, I shall discuss the discrepancy of the set of spanning trees in general graphs, a notion that has been recently studied by Balogh, Csaba, Jing and Pluhar. More concretely, for every graph $G$ and a number of colours $r$, we look for the maximum $D$ such that in any $r$-colouring of the edges of $G$ one can find a spanning tree with at least $(n-1+D)/r$ edges of the same colour. As our main result, we show that under very mild conditions (for example, if $G$ is 3-connected), the discrepancy equals, up to a constant factor, to the minimal integer $s$ such that $G$ can be separated into $r$ equal parts by removing $s$ vertices. This strong and perhaps surprising relation between this extremal quantity and a geometric quantity allows us to estimate the spanning-tree discrepancy for many graphs of interest. In particular, we reprove and generalize results of Balogh et al., as well as obtain new ones. For certain graph families, we also obtain tight asymptotic results.
The talk is based on joint work with Lior Gishboliner and Michael Krivelevich.