2
$\begingroup$

Consider a union-closed family $\mathcal{F}$ of $n=\vert \mathcal{F} \vert$ sets, $n$ odd, and its family $\mathit{J}(\mathcal{F})$ of $m = \vert\mathit{J}(\mathcal{F})\vert$ basis sets (or $\cup$-irreducible sets, also called generators), and define $\mathcal{F_a} = \{A \in \mathcal{F}: a \in A \}$, $\mathit{J_a}(\mathcal{F}) = \{A \in \mathit{J}(\mathcal{F}) : a \in A \}$.

It is easy to prove by contradiction that if $\exists a$ such that $\vert\mathit{J_a}(\mathcal{F})\vert \ge m-\Bigl\lfloor\log_2{\frac{n+1}{2}}\Bigr\rfloor$, then $\vert \mathcal{F_a} \vert \ge \frac{n}{2}$.

I have tried the two examples in "The journey of the union-closed sets conjecture" by Bruhn and Schaudt on section 6.3 "Limits of averaging" and both seem to satisfy the above requirement.

I understand it might not be easy, but any idea on how to construct an example of a union-closed family with average set size less than half of the universe and such that $\forall a$ $\vert\mathit{J_a}(\mathcal{F})\vert \lt m-\Bigl\lfloor\log_2{\frac{n+1}{2}}\Bigr\rfloor$?

$\endgroup$

1 Answer 1

2
$\begingroup$

Not a good example, but it might hint for a better one.

Take two integers $N=2k+1,M$. Let the basis sets be $\{x,x+1,...,x+k\},1\leq x\leq N$, taken modulo $N$ (identify $N\equiv 0$) and $\{1,2,...,N,a_1,a_2,...,a_M\}$.

The union-closed family $\mathcal{F}$ contains all set of the form $\{x,x+1,...,x+l\},1\leq x\leq N,k\leq l\leq N-1$ and $\{1,2,...,N,a_1,a_2,...,a_M\}$. So it's easy to see that $m=N+1,n=\frac{N(N-1)}{2}+2,J_i(\mathcal{F})=\frac{N+1}{2},J_{a_j}(\mathcal{F})=1$. The average set size is $f(N)+\frac{M}{\frac{N(N-1)}{2}+2}$ ($f(N)$ is quite complicative to write, but it's independent of $M$).

Now we choosing $N,M$ such that $\frac{N-1}{2}$ is odd, $log_2(\frac{N(N-1)}{2}+2)<\frac{N+1}{2}, f(N)+\frac{M}{\frac{N(N-1)}{2}+2}<\frac{N+M}{2}$ then $\mathcal{F}$ is the union-close family that we want.

$\endgroup$
4
  • 1
    $\begingroup$ Since you want $k = \frac{N-1}2$ odd, take $k = 2k_0 + 1$. Then the average set size is $$\frac{24k_0^3 + 46k_0^2 + 37k_0 + M + 12}{2(4k_0^2 + 7k_0 + 4)}$$ and the constraint that the average set size is less than half of the universe simplifies to $M > \frac{2k_0^2}{k_0+1}$ or, if you prefer, $M > \frac{(N-3)^2}{2(N+1)}$ $\endgroup$ Commented Nov 4, 2022 at 8:54
  • 1
    $\begingroup$ Thank you very much. I accept it, although now another more restrictive question would be if there exists an example with a separating family and/or a family with less than $n/4$ elements... $\endgroup$ Commented Nov 4, 2022 at 10:02
  • 1
    $\begingroup$ @BillyJoe, the additional requirement for a family with fewer than $n/4$ elements comes down to the constraint $8k_0^2 - 6k_0 - 7 > 4M$. Combine that with the previous constraint on $M$ to get $8k_0^2 - 6k_0 - 7 > 4M > \frac{8k_0^2}{k_0 + 1}$. Since the upper bound is $\Theta(k_0^2)$ and the lower bound is $\Theta(k_0)$, there's plenty of margin to find values of $k_0$ and $M$ which satisfy both inequalities simultaneously. $\endgroup$ Commented Nov 4, 2022 at 11:16
  • $\begingroup$ @PeterTaylor yes, sorry, I didn't check carefully. $\endgroup$ Commented Nov 4, 2022 at 11:27

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.