Proof of Theorem 2, p. 51 — adding one edge increases the edge-disjoint K^r packing number X by at most one
ProvedBollobasChromatic.Main.packingNum_add_edgecliquescombinatoricsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-graphs
Let be a graph on , let , and let be a pair of distinct vertices. Write for the maximal number of pairwise edge-disjoint subgraphs of , and for with the edge added. Then
In the proof of Theorem 2 this is the reason why the edge-exposure martingale has differences , which makes Lemma 1 applicable with .
Formalization Note The page states only the upper bound ("increases by at most one"); the lower bound (monotonicity) is implicit in the two-sided claim and is stated as well. If is already an edge both inequalities are trivial.
Preamble
import Mathlib import Definitions.Def_BollobasChromatic_Main_Setting
Formal statement
namespace BollobasChromatic.Main
open Filter Topology Asymptotics
theorem packingNum_add_edge (n r : ℕ) (G : SimpleGraph (Fin n)) (u v : Fin n) (huv : u ≠ v) :
packingNum G r ≤ packingNum (G ⊔ SimpleGraph.edge u v) r ∧
packingNum (G ⊔ SimpleGraph.edge u v) r ≤ packingNum G r + 1 := by sorry
end BollobasChromatic.Main
Source
Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), p. 51, proof of Theorem 2 (sentence before display (5))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.