Tata Institute of Fundamental Research
Spencer's Proof of a Random Greedy Packing
STCS Student Seminar
Speaker:
Siddharth Bhandari
Organiser:
Nikhil S Mande
Date:
Friday, 27 Jul 2018, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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)$.
| Speaker: | Siddharth Bhandari |
| Organiser: | Nikhil S Mande |
| Date: | Friday, 27 Jul 2018, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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)$.
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)$.