Discrepancy of spanning trees

Abstract: Recently there has been some interest in discrepancy-type problems on graphs. Here we study the discrepancy of spanning trees. For a connected graph $G$ and a number of colors $r$, what is the maximum $d = d_r(G)$ such that in any $r$-coloring of the edges of $G$, there is a spanning tree with at least $(n-1)/r + d$ edges of the same color? $d_r(G)$ is called the $r$-color spanning-tree discrepancy of $G$, and has been recently studied by Balogh, Csaba, Jing and Pluhar. As our main result, we show that under very mild conditions (for example, if $G$ is 3-connected), $d_r(G)$ is equal, up to a constant factor, to the minimal integer s such that G can be separated into r equal parts $V_1,...,V_r$ by deleting at most $s$ vertices. This strong and perhaps surprising relation between these two parameters allows us to estimate $d_r(G)$ for many graphs of interest. In particular, we reprove and generalize results of Balogh et al., as well as obtain new ones. Some tight asymptotic results for particular graph classes are also obtained.

Joint work with Michael Krivelevich and Peleg Michaeli.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).