9
$\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$ Commented 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$ Commented 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$ Commented 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
    Commented Aug 7, 2017 at 12:09

1 Answer 1

4
$\begingroup$

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

https://arxiv.org/abs/1708.01434

$\endgroup$

You must log in to answer this question.

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