Draft — mutable and not usable as a dependency; its citation marks the draft state.

Proof of `The sparse-house trichotomy`

groundedproofs/Lax57Proofs/SparseHouseTrichotomy.lean · lax-57

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

Use the prepared blockade from Claim 7.1.1. A vertex mixed on at least a 1/Q1/Q fraction of the blocks cannot meet a complete pair among them, because anticonnectivity would supply four vertices that, together with it, induce a house. Their union gives the sparser outcome. Otherwise, double-counting mixed incidences finds a block with few mixed outside vertices. The original sparsity bound and the size of the prepared blockade leave a large set anticomplete to that block, giving the peel outcome.

Attribution

Lemma 7.1 of Nguyen, Scott, and Seymour, including the house construction shown in their Figure 2.