Skip to main content
edited title
Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Mininum Minimum number of sets for a union-closed sets conjecture counterexample

added 112 characters in body
Source Link

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).
  3. For any two disjoint sub-families $\mathcal{F}_1$ and $\mathcal{F}_2$ of $\mathcal{F}$, not containing the empty set, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, it must be $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n$ if $\emptyset \in \mathcal{F}$ or $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n+1$ if $\emptyset \not\in \mathcal{F}$.

Like $\mathcal{F}$, $\mathcal{F}_1$ and $\mathcal{F}_2$ are allowed to contain multiple instances of the same set.

An example of such $\mathcal{F}$ can be constructed from this answer (where the problem was formulated in the dual form) by taking each line of the Fano plane with multiplicity $15$, adding the empty set, and adding all the possible unions, with multiplicity $1$, to have a union-closed family. The resulting familiy has $135$ sets counted with their multiplicity. The only two sub-families, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, are $\mathcal{F}_1 = \mathcal{F}_2 = \emptyset$, therefore the third requirement is satisfied.

I think I can prove that any counterexample family to the union-closed sets conjecture must have a size greater or equal than the size of a minimal $\mathcal{F}$ (background here).

I tried therefore to find an $\mathcal{F}$ with smaller size by removing points or lines from the Fano plane and constructing as above, but in this way requirement $3$ fails.

Is there an example with $|\mathcal{F}| \lt 135$? Any possible idea on how to prove a lower bound for $|\mathcal{F}|$?

Just to be clear, to compute the size of all families above, each set must be counted with its multiplicity.

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).
  3. For any two disjoint sub-families $\mathcal{F}_1$ and $\mathcal{F}_2$ of $\mathcal{F}$, not containing the empty set, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, it must be $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n$ if $\emptyset \in \mathcal{F}$ or $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n+1$ if $\emptyset \not\in \mathcal{F}$.

Like $\mathcal{F}$, $\mathcal{F}_1$ and $\mathcal{F}_2$ are allowed to contain multiple instances of the same set.

An example of such $\mathcal{F}$ can be constructed from this answer (where the problem was formulated in the dual form) by taking each line of the Fano plane with multiplicity $15$, adding the empty set, and adding all the possible unions, with multiplicity $1$, to have a union-closed family. The resulting familiy has $135$ sets counted with their multiplicity. The only two sub-families, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, are $\mathcal{F}_1 = \mathcal{F}_2 = \emptyset$, therefore the third requirement is satisfied.

I think I can prove that any counterexample family to the union-closed sets conjecture must have a size greater or equal than the size of a minimal $\mathcal{F}$ (background here).

I tried therefore to find an $\mathcal{F}$ with smaller size by removing points or lines from the Fano plane and constructing as above, but in this way requirement $3$ fails.

Is there an example with $|\mathcal{F}| \lt 135$? Any possible idea on how to prove a lower bound for $|\mathcal{F}|$?

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).
  3. For any two disjoint sub-families $\mathcal{F}_1$ and $\mathcal{F}_2$ of $\mathcal{F}$, not containing the empty set, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, it must be $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n$ if $\emptyset \in \mathcal{F}$ or $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n+1$ if $\emptyset \not\in \mathcal{F}$.

Like $\mathcal{F}$, $\mathcal{F}_1$ and $\mathcal{F}_2$ are allowed to contain multiple instances of the same set.

An example of such $\mathcal{F}$ can be constructed from this answer (where the problem was formulated in the dual form) by taking each line of the Fano plane with multiplicity $15$, adding the empty set, and adding all the possible unions, with multiplicity $1$, to have a union-closed family. The resulting familiy has $135$ sets counted with their multiplicity. The only two sub-families, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, are $\mathcal{F}_1 = \mathcal{F}_2 = \emptyset$, therefore the third requirement is satisfied.

I think I can prove that any counterexample family to the union-closed sets conjecture must have a size greater or equal than the size of a minimal $\mathcal{F}$ (background here).

I tried therefore to find an $\mathcal{F}$ with smaller size by removing points or lines from the Fano plane and constructing as above, but in this way requirement $3$ fails.

Is there an example with $|\mathcal{F}| \lt 135$? Any possible idea on how to prove a lower bound for $|\mathcal{F}|$?

Just to be clear, to compute the size of all families above, each set must be counted with its multiplicity.

Source Link

Mininum number of sets for a union-closed sets conjecture counterexample

Let $\mathcal{F}$ be a family of $n$ finite sets. In this case, the family can be regarded as a multiset, since it is allowed to contain multiple instances of the same set. Let $U(\mathcal{F})$ be the universe, i.e. the union of all sets in $\mathcal{F}$.

We require that:

  1. $\mathcal{F}$ is union-closed ($\mathcal{F}$ must contain at least one instance of $A \cup B$ for any $A,B \in \mathcal{F}$);
  2. Each element in $U(\mathcal{F})$ is in at most $\lfloor (n+1)/2 \rfloor$ sets of $\mathcal{F}$ (every set is counted with its multiplicity).
  3. For any two disjoint sub-families $\mathcal{F}_1$ and $\mathcal{F}_2$ of $\mathcal{F}$, not containing the empty set, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, it must be $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n$ if $\emptyset \in \mathcal{F}$ or $(1+|\mathcal{F}_1|)(1+|\mathcal{F}_2|) \le n+1$ if $\emptyset \not\in \mathcal{F}$.

Like $\mathcal{F}$, $\mathcal{F}_1$ and $\mathcal{F}_2$ are allowed to contain multiple instances of the same set.

An example of such $\mathcal{F}$ can be constructed from this answer (where the problem was formulated in the dual form) by taking each line of the Fano plane with multiplicity $15$, adding the empty set, and adding all the possible unions, with multiplicity $1$, to have a union-closed family. The resulting familiy has $135$ sets counted with their multiplicity. The only two sub-families, such that if $A \in \mathcal{F}_1$ and $B \in \mathcal{F}_2$ then $A \cap B = \emptyset$, are $\mathcal{F}_1 = \mathcal{F}_2 = \emptyset$, therefore the third requirement is satisfied.

I think I can prove that any counterexample family to the union-closed sets conjecture must have a size greater or equal than the size of a minimal $\mathcal{F}$ (background here).

I tried therefore to find an $\mathcal{F}$ with smaller size by removing points or lines from the Fano plane and constructing as above, but in this way requirement $3$ fails.

Is there an example with $|\mathcal{F}| \lt 135$? Any possible idea on how to prove a lower bound for $|\mathcal{F}|$?