0
$\begingroup$

The ratio between the number of unordered couples of sets, with empty intersection between the two sets, and the total number of unordered couples of sets, for a powerset on $n$ elements without the empty set, $\mathcal{P}([n]) \setminus \emptyset$, is:

$$\frac{{n+1 \brace 3}}{{2^n-1 \choose 2}}=\frac{(1 + 3^n - 2^{n+1})}{(2^n-1)(2^n-2)}$$

Where ${n+1 \brace 3}$ denotes a Stirling number of the second kind. Is it possible to find a finite separating union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with size of the universe $|U(\mathcal{F})| = n$, with a biconnected Hasse diagram graph (without articulation vertices), and with the ratio defined as above higher than the value for $\mathcal{P}([n]) \setminus \emptyset$?

$\endgroup$
0

1 Answer 1

1
+150
$\begingroup$

The numerator grows faster than the denominator, so we can do better by making a minimal extension of a previous powerset: $2^{[k]} \cup \{[m] : k+1 \le m \le n \} \setminus \emptyset$ gives $$\frac{(1 + 3^k - 2^{k+1})}{(2^k+n-k-1)(2^n+n-k-2)}$$ and for $n \ge 5$ the optimal value of $k$ is less than $n$ and grows logarithmically.

k    First n for which k is optimal
2    2
3    3
4    4
5    7
6    12
7    24
8    46
9    91
10   182
11   366

By brute force enumeration, $2^{[n]} \setminus \emptyset$ is optimal for $n \le 4$.

$\endgroup$
13
  • $\begingroup$ Thank you very much, although I am tempted to reformulate the question excluding families such that there does not exist $A,B \in \mathcal{F}$, $A \not = B$, $A,B \not = U(\mathcal{F})$ such that $A \cup B = U(\mathcal{F})$. I don't know if it is better that I post a new question. $\endgroup$ Oct 5, 2022 at 9:20
  • $\begingroup$ @BillyJoe, take the construction given and add one set: $[n-2] \cup \{n\}$ to meet the new constraint. $\endgroup$ Oct 5, 2022 at 10:06
  • $\begingroup$ I wonder if there is a way to formalize the concept of a family without "cap", because here we have a smaller union closed family $2^{[k]}$ then "capped" where the abundant elements of $2^{[k]}$ are also abundant elements of $\mathcal{f}$. $\endgroup$ Oct 5, 2022 at 10:21
  • 1
    $\begingroup$ I'm pretty sure that just requires adding $[k-1]\cup\{k+1\}$ and $[k-1]\cup\{k+2\}$. $\endgroup$ Oct 8, 2022 at 23:55
  • 1
    $\begingroup$ @BillyJoe, the brute force search terminated without finding anything better than (compressed format) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 31, 63]. $\endgroup$ Oct 20, 2022 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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