talldoor - Notes on Laminar Matroid

Tags: alg, matroid

references:

https://cdn.vanderbilt.edu/vu-my/wp-content/uploads/sites/2392/2015/07/14141714/Tara-E-Fife.pdf

https://arxiv.org/abs/1606.08354

prove through induction on $∣ A ∣$ (use definition 1)

$∣ A ∣ = 1$ , this is obvious.
assume exchange property holds for $∣ A ∣ \leq k$ . Need to prove that for two independent set $I_{1}, I_{2}$ , $∣ I_{1} ∣ > ∣ I_{2} ∣$ , $\exists i \in I_{1} \ I_{2}$ s.t. $\forall A, ∣ A ∣ = k + 1, ∣ {I_{2} \cup i} \cap A ∣ \leq c (A)$ . Suppose the exchange property doesn’t hold for $∣ A ∣ = k + 1$ . For all $i$ exists $A ∋ i$ , $∣ I_{2} \cap A ∣ = c (A)$ . Since $I_{1}$ is an independent set, $∣ I_{1} \cap A ∣ \leq c (A)$ for those $A$ , ${I_{2} \ I_{1}} \cap A \neq = \emptyset$ , then for those $A$ $∣ A \cap I_{1} ∣ \leq ∣ A \cap I_{2} ∣$ . Thus for any $i \in I_{1} \ I_{2}$ , there is a set $A$ s.t. $∣ A \cap {I_{2} \ I_{1}} ∣ \geq ∣ A \cap {I_{1} \ I_{2}} ∣$ , and those $A$ are disjoint since $A \in A$ . Thus $∣ I_{1} ∣ \leq ∣ I_{2} ∣$ . So exchange property holds for $k + 1$

一点点关于拟阵交和带权拟阵交的原始的想法：