School of Technology and Computer Science Seminars

Spencer's Proof of a Random Greedy Packing

by Siddharth Bhandari (School of Technology and Computer Science, TIFR)

Friday, July 27, 2018 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
We will prove the following theorem which gives an alternate proof to the Erdős-Hanani conjecture.

Let $H$ be a $k+1$-uniform hypergraph on a vertex set $V$ of size $n$. We will assume the following two conditions: 
Degree: Every $v\in V$ is in precisely $D$ edges. 
Co-Degree: Every distinct pair $v,v'\in V$ have only $o(D)$ edges in common.

It is easy to see that the size of a maximum matching is $N/(k+1)$.

Spencer showed the following surprising theorem. By ordering the edges randomly and then greedily selecting a maximal matching, the expected size is asymptotically $N/(k+1)$.