This is a quite involved question so I'd be happy just to be shown how to understand some small parts. I'm trying to read these slides, in which the lemma in slide 25 is used to prove Pippenger's theorem in slide 20, concerning the smallest size of a cover of a hypergraph.
The plan for the proof is listed in slides 26-27, at the bottom of which there's a section for the change of parameters that I don't understand. My general understanding of the proof is that at subsequent rounds, a set of edges is removed, which leaves behind a set of vertices whose size we can estimate. Doing this multiple times would give us an idea of how close we are at achieving a cover. The parameters are changed at each round so that the lemma could be used again. I'm getting confused about the notations used (e.g. which parameters are fixed, which ones change), or why the parameters change that way. It'd be great if one or two iterations could be done so I can see how the process works.
===========
Edit: I will add several subquestions below as I go along with my reading.
- The question I listed above.
- In the proof for part a) of the lemma (slide 35-36), a probabilistic argument is used to show that, with high probability, $|E'| = (1 \pm 2 \delta_1)\frac{\epsilon n}{r}$, i.e. a) is correct. But how is this equivalent to saying the graph certainly contains a set $E'$, as stated in the lemma?
Pippenger's theorem roughly states that any hypergraph that satisfies certain pseudorandomness properties contains something that looks roughly like perfect matching.
A first attempt for generating this "almost perfect matching" is to sample a subset of around $n/r$ ($r$ being the uniformity of hypergraph) edges uniformly at random. But this doesn't quite work: with high probability, (1) you will end up selecting lots of edges that cover the same set of vertices, and (2) some set of vertices will never be covered by the edges you selected. (Perhaps it's useful to think about what happens when you take a random function from $[n]$ to $[n]$. How close will it be to being a surjection?)
Somehow (1) is the more fatal error, as (2) we could potentially fix by sampling even more edges. In order to remedy (1), we sample only a small subset of the edges at a time (or more accurately, we sample each edge with a smaller probability), thereby greatly reducing the risk of an untolerable amount of clashes between the edges we selected.
In the second question you ask, you are essentially asking why the probabilistic method works. In each iteration of the algorithm, one takes a random "bite" out of the edge set, by sampling each remaining edge with a certain probability. If we can show that the random bite satisfies a property with positive probability, then there exists such a bite, and we can then fix such a bite to be our definitive choice for that stage of the algorithm. The proof after all, is existential, if at each step of the algorithm, we have a positive probability of being able to proceed, we will have shown that there is a universe in which we get very lucky and proceed with the algorithm with no issues along the way. The fact that this can possibly happen proves that the object we desire must exist.
Perhaps it's helpful to think of how this method would apply to trying to generate a function $f\colon[n]\to[n]$ that is almost surjective. Of course, the object that you will end up proving the existence of is rather ridiculous, that is, a function $f$ whose co-domain has size almost n, but perhaps helps with understanding the algorithm. A less trivial playground could be when $r=2$, i.e. you are trying to find an almost perfect matching in the ordinary graph sense (here maximum pair degrees are trivially $0$, which makes tracking the parameters after each bite somewhat more tractable).