Skip to main content
added 187 characters in body
Source Link
Ramiro de la Vega
  • 11.5k
  • 1
  • 45
  • 56

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfies conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty. To show this just note (for the "hard" direction) that if $A$ is a maximal intersecting family and $x$ is a subset of $n$ that does not contain any element of $A$ then $x^c$ intersects anyevery element of $A$ and hence belongs to $A$.

Another characterization that follows easily from the one above but only works for finite $n$: A family $A$ satisfies $1$ and $2$ if and only if $A$ is intersecting and $|A|=2^{n-1}$.

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfies conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty. To show this just note (for the "hard" direction) that if $A$ is a maximal intersecting family and $x$ is a subset of $n$ that does not contain any element of $A$ then $x^c$ intersects any element of $A$ and hence belongs to $A$.

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfies conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty. To show this just note (for the "hard" direction) that if $A$ is a maximal intersecting family and $x$ is a subset of $n$ that does not contain any element of $A$ then $x^c$ intersects every element of $A$ and hence belongs to $A$.

Another characterization that follows easily from the one above but only works for finite $n$: A family $A$ satisfies $1$ and $2$ if and only if $A$ is intersecting and $|A|=2^{n-1}$.

added 205 characters in body
Source Link
Ramiro de la Vega
  • 11.5k
  • 1
  • 45
  • 56

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfysatisfies conditions $1$ and $2$ if and only if $A$ is a maximal intersecting familymaximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty. To show this just note (for the "hard" direction) that if $A$ is a maximal intersecting family and $x$ is a subset of $n$ that does not contain any element of $A$ then $x^c$ intersects any element of $A$ and hence belongs to $A$.

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfy conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty.

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfies conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty. To show this just note (for the "hard" direction) that if $A$ is a maximal intersecting family and $x$ is a subset of $n$ that does not contain any element of $A$ then $x^c$ intersects any element of $A$ and hence belongs to $A$.

added 205 characters in body
Source Link
Ramiro de la Vega
  • 11.5k
  • 1
  • 45
  • 56

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfy conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty.

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Your two examples are of the following form: Fix a collection $C$ of subsets of $n$ such that any two elements of $C$ have non-empty intersection and any other subset of $n$ either contains or is disjoint from an element of $C$. Then let $A$ be the collection of those subsets of $n$ which contain an element of $C$.

In the first example $C=\{\{0\}\}$ while in the second example $C$ is the collection of subsets of size $(n+1)/2$. It is not hard to show that any example must be of this form.

Actually, a family $A$ satisfy conditions $1$ and $2$ if and only if $A$ is a maximal intersecting family. Here intersecting means that the intersection of any two members of the family is non-empty.

Source Link
Ramiro de la Vega
  • 11.5k
  • 1
  • 45
  • 56
Loading