BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Lior Gishboliner (Tel-Aviv University)
DTSTART:20210201T140000Z
DTEND:20210201T150000Z
DTSTAMP:20260423T052449Z
UID:EPC/45
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/EPC/45/">Dis
 crepancy of spanning trees</a>\nby Lior Gishboliner (Tel-Aviv University) 
 as part of Extremal and probabilistic combinatorics webinar\n\n\nAbstract\
 nRecently there has been some interest in discrepancy-type problems on gra
 phs. Here we study the discrepancy of spanning trees. For a connected grap
 h $G$ and a number of colors $r$\, what is the maximum $d = d_r(G)$ such t
 hat in any $r$-coloring of the edges of $G$\, there is a spanning tree wit
 h 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 und
 er very mild conditions (for example\, if $G$ is 3-connected)\, $d_r(G)$ i
 s equal\, up to a constant factor\, to the minimal integer s such that G c
 an 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 p
 arameters allows us to estimate $d_r(G)$ for many graphs of interest. In p
 articular\, we reprove and generalize results of Balogh et al.\, as well a
 s obtain new ones. Some tight asymptotic results for particular graph clas
 ses are also obtained. \n\nJoint work with Michael Krivelevich and Peleg M
 ichaeli.\n
LOCATION:https://researchseminars.org/talk/EPC/45/
END:VEVENT
END:VCALENDAR