12
$\begingroup$

(I have posted a corrected version of this question. The limit $\lceil n/2 \rceil$ must be replaced with $\lceil (n+1)/2 \rceil$.)

I have already asked basically the same question here, but now I have found a way to rephrase it simply, so this new formulation might be more interesting.

Consider a union-closed family $\mathcal{F}$ of $n$ finite sets with $\mathcal{F} \not = \{ \emptyset \}$.

Let $\mathcal{H} \subseteq \mathcal{F}$ be the family of all sets in $\mathcal{F}$ which are (not necessarily proper) supersets of at least $\lceil n/2 \rceil$ of the sets in $\mathcal{F}$.

I conjecture that there always exists a non-empty set in $\mathcal{F}$ which is a subset of at least $| \mathcal{H} | - 1$ of the sets in $\mathcal{H}$.

Can we say something or find a counterexample for this conjecture?

I have tried many examples but couldn't find a counterexample.

Proving the conjecture should be difficult, because I believe it implies the union-closed sets conjecture, however finding a counterexample might be easier and could provide a "difficult" example for the union-closed sets conjecture.

If someone wants to experiment, I have written a python program: given an input family on the standard input (use an empty line for the empty set), it removes duplicates and adds all missing unions of some of its sets, in order to obtain a closed family, then verifies the conjecture:

Here it is run over this example, and here over an example similar to this one where the conjecture is satisfied for $| \mathcal{H} | - 1$ sets in $\mathcal{H}$ and not for all of them.

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ I downvoted. Your terminology is bad. Do you mean $\mathcal{H} \subseteq \mathcal{P}(\mathcal{F})$ instead? You shouldn't keep saying "sets"; you should say, e.g., "collections" when referring to things like $\mathcal{F}$. Anyways, I have no idea how $\mathcal{H}$ is defined. If $\mathcal{F} = \{\emptyset,\{1\},\{2\},\{1,2\}\}$, what is $\mathcal{H}$? I would vote to close your question. $\endgroup$
    – mathworker21
    Commented May 8 at 12:47
  • 4
    $\begingroup$ @mathworker21 The terminology seems correct and clear to me. A slight ambiguity is due to the verb "to contain" which is commonly used both in the sense of "as a subset" (like here, as I understand) and "as an element". I guess you would prefer "include". $\endgroup$
    – Pietro Majer
    Commented May 8 at 13:41
  • 4
    $\begingroup$ I may be wrong, but it seems very clear to me. As I wrote: read "containing" = "containing as a subset". In the above example $n=4$ and $\mathcal{H}=\{ \{1\},\{2\},\{1,2\}\}$. Consider e.g. the set $H=\{1,2\}\in\mathcal F$. It includes as subsets all the $4$ elements of $\mathcal F$, more than $4/2$, so $H\in\mathcal H$. The empty set only includes $1$ element of $\mathcal F$, $1$ is less than $4/2$, so $\emptyset\notin \mathcal H$. $\endgroup$
    – Pietro Majer
    Commented May 8 at 13:53
  • 2
    $\begingroup$ @PietroMajer: ah, okay, that does clarify, thanks! EDIT: I edited the question to hopefully make its meaning crystal clear. $\endgroup$
    – Sam Hopkins
    Commented May 8 at 13:55
  • 1
    $\begingroup$ @PietroMajer Thanks for clarifying. [Now that I understand what "contain" is referring to, I think it's much better than "include" though :P] $\endgroup$
    – mathworker21
    Commented May 8 at 17:43

2 Answers 2

Reset to default
6
$\begingroup$

Counterexample with $|\mathcal F|=n=20$. First partition the set $[18]=\{1,2,3,\dots,18\}$ into the disjoint sets
$A=\{1,2,3,4\}$, $B=\{5,6,7,8\}$, $C=\{9,10,11,12\}$,
$X=\{13,14\}$, $Y=\{15,16\}$, $Z=\{17,18\}$. Now define
$\mathcal F=\{\varnothing,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3,C_0,C_1,C_2,C_3,X_0,X_1,Y_0,Y_1,Z_0,Z_1,T\}$ where:
$A_0=B\cup C\cup Z$, $A_1=A_0\cup\{1\}$, $A_2=A_1\cup\{2\}$, $A_3=A_2\cup\{3\}$,
$B_0=A\cup C\cup Y$, $B_1=B_0\cup\{5\}$, $B_2=B_1\cup\{6\}$, $B_3=B_2\cup\{7\}$,
$C_0=A\cup B\cup X$, $C_1=C_0\cup\{9\}$, $C_2=C_1\cup\{10\}$, $C_3=C_2\cup\{11\}$,
$X_0=A\cup B\cup C\cup Y\cup Z$, $X_1=X_0\cup\{13\}$,
$Y_0=A\cup B\cup C\cup X\cup Z$, $Y_1=Y_0\cup\{15\}$,
$Z_0=A\cup B\cup C\cup X\cup Y$, $Z_1=Z_0\cup\{17\}$,
$T=A\cup B\cup C\cup X\cup Y\cup Z=[18]$.

To see that $\mathcal F$ is union-closed and $|\mathcal F|=20$, observe that:
$\varnothing\subsetneqq A_0\subsetneqq A_1\subsetneqq A_3$,
$\varnothing\subsetneqq B_0\subsetneqq B_1\subsetneqq B_3$,
$\varnothing\subsetneqq C_0\subsetneqq C_1\subsetneqq C_3$,
$A_0\cup B_0=X_0\subsetneqq X_1\subsetneqq T$,
$A_0\cup C_0=Y_0\subsetneqq Y_1\subsetneqq T$,
$B_0\cup C_0=Z_0\subsetneqq Z_1\subsetneqq T$,
$A_0\cup B_0\cup C_0=T$.

Finally, $\mathcal H=\{X_0,X_1,Y_0,Y_1,Z_0,Z_1,T\}$, so $|\mathcal H|=7$, while each of the minimal nonempty elements of $\mathcal F$, namely $A_0$, $B_0$, and $C_0$, is contained in just $5$ elements of $\mathcal H$.

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ Is that unusual? I definitely don't carefully check the details of every MO post I upvote... just try to discern whether real effort has been put into it and whether it is likely to make a positive contribution. Anyways I guess this is getting a bit off topic from the question at hand... $\endgroup$
    – Sam Hopkins
    Commented May 10 at 14:11
  • 4
    $\begingroup$ I checked it and it is correct! Thank you very much. I will study this example to see if it is interesting regarding to the linked question. By the way if we remove the empty set the family satisfies the conjecture. So it would be nice to have a counterexample without the empty set. $\endgroup$
    – Fabius Wiesner
    Commented May 10 at 14:17
  • 1
    $\begingroup$ Also, this family with or without the empty set is not independent, so maybe I will ask in the future another question with that restriction, since it suffices to prove the union-closed sets conjecture for independent families (extension of the separating property). Thank you very much anyway. $\endgroup$
    – Fabius Wiesner
    Commented May 10 at 14:34
  • 2
    $\begingroup$ I realized now that I made a mistake in the question. The $\lceil n/2 \rceil$ limit is correct for $n$ odd but needs to be $\lceil (n+1)/2 \rceil$ for $n$ even. In other words it needs to be $n-\lceil n/2 \rceil+1$ for $n$ odd or even. Should I correct the question or start another one? This is because the intersection of all $H_i$ has to give the set of all the abundant elements. $\endgroup$
    – Fabius Wiesner
    Commented May 10 at 15:02
  • 1
    $\begingroup$ I think a separated question should be better - let this one be dedicated to counterexamples :) $\endgroup$
    – Pietro Majer
    Commented May 10 at 15:13
5
$\begingroup$

The following non-counterexample (it had a mistake) can serve to show that the factor $1/2$ can’t be lowered.

Consider for instance, for $r\in \mathbb N$, the family $\mathcal F:=\{F\subset[2r]: |F|\ge r\}$, so that $n:=|\mathcal F|=\sum_{i\ge r}{2r\choose i}=2^{2r-1}+\frac12{2r\choose r}$. Then in $ \mathcal H$ there are all $H\in\mathcal F$ of cardinality $|H|= 2r-1$, because every such $H$ includes $\sum_{i\ge r}{2r-1\choose i}=2^{2r-2}\sim\frac n2 $ sets $F\in\mathcal F$. But every $F\in\mathcal F$ fails to be a subset of at least $r$ elements $H$ of $\mathcal H$, namely $H_i:=[2r]\setminus \{i\}$ for $i\in F$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Are you sure? I think it should be $\sum_{i\ge r}{2r-1\choose i}=2^{2r-2}$ (see here) or am I missing something? $\endgroup$
    – Fabius Wiesner
    Commented May 8 at 14:28
  • $\begingroup$ yes, I wrongly did $\sum _{i\le r}$ ! deleting $\endgroup$
    – Pietro Majer
    Commented May 8 at 14:39
  • 2
    $\begingroup$ well I edited to keep it, as at least it shows that n/2 can’t be improved $\endgroup$
    – Pietro Majer
    Commented May 8 at 15:00
  • $\begingroup$ @PietroMajer Sorry, what factor $1/2$ are you referring to? Why doesn't your answer disprove the OP's conjecture? They ask to show there's some set in $\mathcal{F}$ which is a subset of all but at most one set in $\mathcal{H}$. In your answer $|\mathcal{H}| = 2r$ and each $F \in \mathcal{F}$ is a subset of at most $r$ sets $H \in \mathcal{H}$. $\endgroup$
    – mathworker21
    Commented May 8 at 17:43
  • 1
    $\begingroup$ Yes but here for each set $H\in\mathcal H$ there are approximatively $\frac12 n$ subsets $F\subset H$, $F\in\mathcal F$, yet less than $\frac12 n$, which was required. $\endgroup$
    – Pietro Majer
    Commented May 8 at 18:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .