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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Oct 20, 2022 at 13:15

You must log in to answer this question.

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