BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/894
DTSTAMP:20230914T125942Z
SUMMARY:Spencer's Proof of a Random Greedy Packing
DESCRIPTION:Speaker: Siddharth Bhandari\n\nAbstract: \nWe will prove the fo
llowing theorem which gives an alternate proof to the Erdős-Hanani conjec
ture.\nLet $H$ be a $k+1$-uniform hypergraph on a vertex set $V$ of size $
n$. We will assume the following two conditions: \nDegree: Every $v\\in V
$ is in precisely $D$ edges. \nCo-Degree: Every distinct pair $v\,v'\\in
V$ have only $o(D)$ edges in common.\nIt is easy to see that the size of a
maximum matching is $N/(k+1)$.\nSpencer showed the following surprising t
heorem. By ordering the edges randomly and then greedily selecting a maxim
al matching\, the expected size is asymptotically $N/(k+1)$.\n
URL:https://www.tcs.tifr.res.in/web/events/894
DTSTART;TZID=Asia/Kolkata:20180727T171500
DTEND;TZID=Asia/Kolkata:20180727T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR