Proof of laminar matroid

Question

Let $S$ be a ground set, and $\mathscr{L}$ be a laminar family of subsets of $S$, which means that for every two distinct subsets $A,B \in \mathscr{L}$, we have either $A \subseteq B$ or $B \subseteq A$ or $A \cap B = \emptyset$. For every $Y \in \mathscr{L}$, we are given a positive number $k(Y) \in \mathbb{Z}^+$. We define the group of subsets $I$ as $$I = \{ X \subseteq S :|X \cap Y| \leq k(Y), \forall Y \in \mathscr{L}\}.$$I need to prove that $(S;I)$ is a laminar matroid. I successfully proved that the empty set is independent and the hereditary property but I am struggling to prove the exchange property. Any direction on how to prove the exchange property in this situation? Thanks in advance.

Answer 1

Let $N$ be the ground set and $\mathscr{L}$ be a laminar of subsets of $N$. Let $\mathscr{I}=\{S\subseteq N: |S\cap L|\leq k(L), \forall L\in \mathscr{L}\}$. We show that $M=(N,\mathscr{I})$ is indeed a matroid by verifying the exchange property.

Let $S,T\in \mathscr{I}$ with $|S|<|T|$.

If there exists $e\in T\backslash S$ such that $e\notin L$ for any $L\in \mathscr{L}$, then $|(S+e)\cap L|=|S\cap L|\leq k(L)$ for any $L\in \mathscr{L}$.

Hence assume that for each $e\in T\backslash S$ there exists $L\in \mathscr{L}$ with $e\in L$. For each $e\in T\backslash S$, let $\mathscr{L}_e$ be the collection of $L\in \mathscr{L}$ with $e\in L$. For each $e\in T\backslash S$ and any $L\in \mathscr{L}\backslash \mathscr{L}_e$, we have $|(S+e)\cap L|=|S\cap L|\leq k(L)$.

Hence it remains to show that there exists $e\in T\backslash S$ such that $|(S+e)\cap L|\leq k(L)$ for any $L\in \mathscr{L}_e$. Note that $\mathscr{L}_e$ is a chain, as $\mathscr{L}$ is a laminar. Let $\mathscr{L}'=\{L_{e_1},\ldots,L_{e_l}\}$ be the collection of inclusion-wise maximal sets in $\mathscr{L}$ such that $|S\cap L_{e_i}|=k(L_{e_i})$ with $e_i\in T\backslash S$. Then $L_{e_i}\cap L_{e_j}=\emptyset$. Moreover, $|T|>|S|$ and $|T\cap L_{e_i}|\leq k(L_{e_i})$ imply that $|T\backslash (\cup L_{e_i})|>|S\backslash (\cup L_{e_i})|$. By the definition of $\mathscr{L}'$, there exists $e^*\in (T\backslash S)\backslash (\cup L_{e_i})$ such that $|S\cap L|<k(L)$ for any $L\in \mathscr{L}_{e^*}$. It follows that $|(S+e^*)\cap L|=|S\cap L|+1\leq k(L)$ for any $L\in \mathscr{L}_{e^*}$ and $|(S+e^*)\cap L|=|S\cap L|\leq k(L)$ for any $L\in \mathscr{L}\backslash \mathscr{L}_{e^*}$.

The exchange property follows.