8
$\begingroup$

Is the following claim true?

Let $\mathcal{F} \subseteq 2^{[n]}$ be a union-closed family. That is, if $A,B \in \mathcal{F}$, then $A \cup B \in \mathcal{F}$. Then

$$|\partial^+\mathcal{F}\setminus \mathcal{F}|\leq 2^{n-1},$$

where $\partial^+ \mathcal{F}$ is the upper shadow of $\mathcal{F}$.

Edit: To be explicit about what is the upper shadow of $\mathcal{F}$:

$\partial^+ \mathcal{F}=\{A\cup \{x\}|A \in \mathcal{F}, x\in [n]\setminus A\}$

Edit: Ok, so the above statement turned out to be true. What about the following generalization?

Similar to the above definition of the upper shadow, we can also define, for any $k$, the $k$th upper-shadow of a family $\mathcal{F}\subseteq 2^{[n]}$ as follows:

$\partial_k^+\mathcal{F}:=\{A \cup K|A \in \mathcal{F}\wedge K\subseteq [n]\setminus A \wedge |K|=k\}$.

Denote $\partial_{\leq k}^+\mathcal{F}:=\bigcup_{i=1}^k\partial_i^+\mathcal{F}$.

Now, Let $\mathcal{F}\subseteq 2^{[n]}$ be a union-closed family. Is it true that for any $k \in [n]$, $|\partial_{\leq k}^+\mathcal{F}\setminus \mathcal{F} |\leq 2^n-2^{n-k}$? We know it's true for $k=1$, but I wonder if it's true in general. If true, this would be tight for any $k$, since one can take the family $\mathcal{F}=2^{[n-k]}$ as a subfamily of $2^{[n]}$.

Also, it would be interesting to find bounds on $|\partial_k^+\mathcal{F}\setminus \mathcal{F}|$.I can prove that for any $k$ this quantity is at most $2^{n-1}$, and I know that for $k=1$ this is tight, but for larger $k$ perhaps the bound is lower. For instance, for $k=2$ the best I can do is $\frac{3}{8}2^n$, by taking $\mathcal{F}=2^{[n-3]}$.

$\endgroup$
4
  • $\begingroup$ Note that \cal does not take an argument; it is an old-style font declaration that remains in effect until the end of the current group. You really want to use \mathcal. See e.g. tex.stackexchange.com/a/84043 . $\endgroup$ Mar 13, 2017 at 18:38
  • 3
    $\begingroup$ Since you explain what does union-closed mean, I believe it would be natural to also explain what is upper shadow. $\endgroup$ Mar 13, 2017 at 21:32
  • $\begingroup$ A subfamily $\{\varnothing,\{1\},\{2,3\},\{2,4\},\{3,4\}\}$ of $2^{[4]}$ shows that the fact does not hold if we omit the union-closedness assumption. $\endgroup$ Apr 11, 2017 at 15:32
  • 1
    $\begingroup$ I suspect that if we omit the union-closedness condition, we can get something like $(1-O(1/n))2^n$, or maybe $(1-O(\log{n}/n))2^n$. $\endgroup$
    – karpasi
    Aug 7, 2017 at 12:09

1 Answer 1

3
$\begingroup$

I ended up proving that this is indeed the case. Theorem $1.3$ in this paper:

https://arxiv.org/abs/1708.01434

$\endgroup$

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.