BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/882
DTSTAMP:20230914T125942Z
SUMMARY:Hansel's Lemma and Interval Graphs
DESCRIPTION:Speaker: Kshitij  Gajjar\n\nAbstract: \nHansel's lemma (not Hen
 sel's lemma) states that if the complete graph on $n$ vertices can be expr
 essed as the union of $r$ bipartite graphs $B_1\,B_2\,\\ldots\,B_r$ such t
 hat $n_i$ is the number of non-isolated vertices in $B_i$\, then $n_1+n_2+
 \\cdots+n_r \\geq n\\log n$. The first published proof of the lemma is by 
 Georges Hansel in 1964\, but the lemma has seen several proofs in literatu
 re\, many of them combinatorial and also an information theoretic proof.\n
 In this talk\, we will prove Hansel's lemma using the probabilistic method
 \, and follow it up with an application of the lemma to distance-preservin
 g subgraphs. Specifically\, we will show a separation between branching ve
 rtices and branching edges by exhibiting an interval graph on $n$ terminal
  vertices for which every distance-preserving subgraph has $O(n)$ branchin
 g vertices and $\\Omega(n\\log n)$ branching edges [joint work with Prof. 
 Jaikumar].\n
URL:https://www.tcs.tifr.res.in/web/events/882
DTSTART;TZID=Asia/Kolkata:20180615T171500
DTEND;TZID=Asia/Kolkata:20180615T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR