2

Show that a laminar family (of pairwise distinct non-empty sets) has at most $2n-1$ members, where $n$ is number of elements of a family of subsets.

I tried to get only at most $n-1$ members, but we are asked to prove it is at most $2n-1$ members. Any help is appreciated. Source of the question:https://books.google.hu/books?id=CR_oBwAAQBAJ&pg=PA543&lpg=PA543&dq=laminar+family+of+at+most+2n-1+members&source=bl&ots=IV0IYEiNF7&sig=ACfU3U1Iaj_uouxermw4336gxqj4q_yb_w&hl=en&sa=X&ved=2ahUKEwjRivC32ajmAhXil4sKHRScDnsQ6AEwAXoECAoQAQ#v=onepage&q=laminar%20family%20of%20at%20most%202n-1%20members&f=false

Naani Masi
  • 51
  • 5

2 Answers2

1

The answer by isitar gives a way to generate a family of $2n-1$ sets, but doesn't show that this is the maximum size that a laminar family can attain.

Let $V$ be the ground set. We prove by induction on $|V|$ that for any maximal laminar family $L$ of $V$ has at most $2|V| - 1$ elements.

For $|V| = 1$, it is clear that the maximal laminar family has at most $2n - 1$ elements.

Suppose it is true for all $1 \leq |V| < n$. We know that two sets $A, B \in L$ exists such that $A \cup B = V, A \cap B = \emptyset$ and $|A|, |B| < n$ (otherwise $L$ is not maximal). By induction, there are at most $2|A| - 1$ sets in $L$ which is a subset of in $A$, and similarly at most $2|B| - 1$ in $B$. Then we have $$|L| \leq (2|A| - 1) + (2|B| - 1) + 1 = 2|V| - 1$$ where the $1$ comes from $V \in L$.

XeqtR
  • 11
0

I know this question is old, but maybe someone stumbles across it.

We can generate the maximal laminar family with $2n-1$ sets by the following procedure:

  1. Start with a set including all points.
  2. Remove one point from this set and create a new set containing only this point.
  3. The new set with the points removed also are a set for your family.
  4. repeat from 2

For me it's easiest to visualize this with a matrix where each column corresponds to a set and each row to a point. If the entry is a $1$, it means the point is in this set, 0 otherwise.

Here is an example with 4 Points and 7 sets. $$ \mathcal{L} = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $$

As you can see, we always end up with this pyramid-form ($n\times n$) and an identity matrix, missing the last column ($n \times n-1$). Therefore we have a laminar family $\mathcal{L}$ with $|\mathcal{L}|=2n -1$.

Isitar
  • 103