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