Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Source: published version, p. 241, Proposition 2.3.
Statement
Use the construction and notation of the shrinking-fragment iteration, and put
For every outcome of the iteration, at least one of the following holds:
Full proof
Every edge of has integer size at most . Hence
Suppose first that . Fix . At step , if , stop. Otherwise define
Every is a subset of by the minimum-fragment property. Since no edge survives to , this process stops at some . At that step, and
Thus covers . Since was arbitrary, it covers all of .
Suppose instead that . The invariant (3) on the iteration page, applied to the terminal empty edge, gives
This proves (1).
The published proof's evolution sentence writes at the stopping step. Since , the type-correct index is , used above; this is an indexing correction only and leaves the stated construction unchanged.