I am trying to understand the article "A note on the union-closed sets conjecture" by Roberts and Simpson.

At the first paragraph of the second page they write:

"We say that $A$ is a basis set in $\mathcal{A}$ if it is not the union of other sets in $\mathcal{A}$. Suppose that $\mathcal{A}$ is a counterexample with $\mid$$\mathcal{A}$$\mid = 2n + 2$ for some integer $n$. Then no element occurs in more than $n$ of its sets. If we remove a basis set from $\mathcal{A}$, then we get a smaller collection which is also a counterexample. A counterexample of minimum size must therefore contain an odd number of sets."

  1. How to show that $\mathcal{A}$ has always a basis set?
  2. They say that removing a basis set from a family with an even number of sets gives a smaller collection which is also a counterexample: I don't understand why this does not apply starting from a family with an odd number of sets.
up vote 1 down vote accepted

If $\mathcal A$ is finite collection of sets then it has natural partial order using subsets, and so one or more smallest non-empty members of $\mathcal A$. Each of these is a basis set

With $|\mathcal A| =2n+2$ as a counter example, each element would appear no more than $n$ times. Remove a basis set to give $\mathcal A^\prime$, and you would have $|\mathcal A^\prime| =2n+1$ and each element would appear no more than $n$ times, so $\mathcal A^\prime$ would be a smaller counter example

This argument does not work for odd-sized sets: with $|\mathcal B| =2n+1$ as a counter example, each element would appear no more than $n$ times. Remove a basis set to give $\mathcal B^\prime$, and you would have $|\mathcal B^\prime| =2n$ and each element would appear no more than $n$ times, so you could not show whether $\mathcal B^\prime$ would be a smaller counter example

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.