Wiki
Wiki

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

W=⋃i=1γWi,U=⋃i=1γUi.W=\bigcup_{i=1}^{\gamma}W_i, \qquad \mathcal U=\bigcup_{i=1}^{\gamma}\mathcal U_i.

For every outcome of the iteration, at least one of the following holds:

W∈⟨H⟩orH⊆⟨U⟩.(1)W\in\langle\mathcal H\rangle \qquad\text{or}\qquad \mathcal H\subseteq\langle\mathcal U\rangle. \tag{1}

Full proof

Every edge of Hγ\mathcal H_\gamma has integer size at most ℓγ<1\ell_\gamma<1. Hence

Hγ=∅orHγ={∅}.\mathcal H_\gamma=\varnothing \quad\text{or}\quad \mathcal H_\gamma=\{\varnothing\}.

Suppose first that Hγ=∅\mathcal H_\gamma=\varnothing. Fix S0=S∈HS_0=S\in\mathcal H. At step ii, if Si−1∈GiS_{i-1}\in\mathcal G_i, stop. Otherwise define

Si=T(Si−1,Wi)∈Hi.S_i=T(S_{i-1},W_i)\in\mathcal H_i.

Every SiS_i is a subset of Si−1S_{i-1} by the minimum-fragment property. Since no edge survives to Hγ\mathcal H_\gamma, this process stops at some i≤γi\le\gamma. At that step, T(Si−1,Wi)∈UiT(S_{i-1},W_i)\in\mathcal U_i and

T(Si−1,Wi)⊆Si−1⊆S.T(S_{i-1},W_i)\subseteq S_{i-1}\subseteq S.

Thus U\mathcal U covers SS. Since SS was arbitrary, it covers all of H\mathcal H.

Suppose instead that Hγ={∅}\mathcal H_\gamma=\{\varnothing\}. The invariant (3) on the iteration page, applied to the terminal empty edge, gives

W=W∪∅∈⟨H⟩.W=W\cup\varnothing\in\langle\mathcal H\rangle.

This proves (1).

The published proof's evolution sentence writes Si∈GiS_i\in\mathcal G_i at the stopping step. Since Gi⊆Hi−1\mathcal G_i\subseteq\mathcal H_{i-1}, the type-correct index is Si−1∈GiS_{i-1}\in\mathcal G_i, used above; this is an indexing correction only and leaves the stated construction unchanged.