 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation/2/c/i/solution

A \subseteq X

r (A) = max {∣ I ∣ : I \subseteq A, I \in I} .

A

has this cardinality. We write

A + x = A \cup {x}

, as in the source. Directly from the definition,

A \subseteq B ⟹ r (A) \leq r (B), r (A) \leq r (A + x) \leq r (A) + 1.

For the last upper bound, deleting

x

A + x

leaves an independent subset of

A

 New to topics? Read the docs here!