3
$\begingroup$

This question is motivated by Frankl's union-closet sets conjecture.

Let $n\in\mathbb{N}$ and set $[n] = \{0,1,\ldots,n\}$. We say that a family ${\cal A} \subseteq {\cal P}([n])$ is union-closed if $\emptyset\notin{\cal A}$ and $A,B\in {\cal A}$ implies $A\cup B\in{\cal A}$.

For $k\in[n]$ we define the weight of $k$ to be $$w(k) = |\{A\in {\cal A}: k\in A\}|.$$ For a set $A\in{\cal A}$ we set the discrepancy to be $$\text{disc}(A) = \max\{w(j):j\in A\} - \min\{w(j):j\in A\}.$$

Let $r\in ]0,1[$ be given. Is there $n\in\mathbb{N}$ and a union closed family ${\cal A}$ on $[n]$ and $M$ minimal amongst the members of ${\cal A}$ such that $$\frac{\text{disc}(M)}{|{\cal A}|} \geq r?$$

$\endgroup$

1 Answer 1

4
$\begingroup$

Surely yes.

Firstly, we may achieve $\max\{w(j)\colon j\in M\}=|\mathcal A|$ for free. Just take any union-closed family of subsets on $[n-1]$, and add $n$ to every set.

So it suffices to make $\min\{w(j)\colon j\in M\}$ small compared with $\mathcal A$. To make this, take $2^{[n-2]}\setminus\{\varnothing\}$ and add to it $[n-1]\setminus\{1\}$ and $[n-1]$; we get a union-closed family.. Then $[n-1]\setminus \{1\}$ is minimal, and $w(n-1)=2$.

$\endgroup$

You must log in to answer this question.

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