0
$\begingroup$

I'd like to prove the following question:

Let $[n] = \{1, \dots, n\}$. Let $\mathcal{S}\subseteq 2^{[n]}$ be a family of sets. What is the largest possible $|\mathcal{S}|$ such that every $i\in [n]$ appears in at least a $1/2+\alpha$ fraction of the sets $S\in \mathcal{S}$? Maybe the $\alpha$s im interested in are $1/10,1/\sqrt{n}$ and so on, what is the best upper bound on $|\mathcal{S}|$ that we can show?

Do we have an upper bound on the size of such set families where each element $i$ appears in more than $1/2$ the sets in the family (I suppose we could also cast it as the largest such $|\mathcal{S}|\times n$ matrix that satisfies the columns have Hamming weight $\geq 1/2+\alpha$)? Any reference would be nice!

$\endgroup$
2
  • 2
    $\begingroup$ We can certainly take all subsets of size $k_n=\lceil (\alpha+1/2)n\rceil.$ That gives a family of size $\sum_{i=k_n}^n\binom ni.$ Somehow this seems related to Sperner’s theorem, but not sure if it can be applied. en.wikipedia.org/wiki/Sperner%27s_theorem $\endgroup$ Commented Apr 7, 2022 at 18:46
  • 1
    $\begingroup$ More than $1/2$ is easy - we can choose $S=2^{[n]}\setminus\{\emptyset\}.$ Basically, every element is in exactly half the sets, and removing the empty set means that every element is in more than half of the remaining sets. $\endgroup$ Commented Apr 7, 2022 at 18:52

1 Answer 1

1
$\begingroup$

Not an answer, just looking at a class of families. These seem intuitively like a basis for the largest such families.

We’ll look at the family of subsets subsets of size $\geq k.$ This will work for any $k\geq(\alpha+1/2)n,$ but might work for smaller $k.$

Each element is in $$\frac{\sum_{i=k}^{n}\binom {n-1}{i-1}}{\sum_{i=k}^n\binom ni}$$ as a proportion of the subsets of size $\geq k$.

Now, $\binom{n}{i}=\binom{n-1}{i}+\binom{n-1}{i-1},$ so $$\sum_{i=k}^n \binom ni=\sum_{i=k}^n \binom{n-1}{i-1}+\sum_{i=k}^{n}\binom{n-1}i=-\binom{n-1}{k-1}+2\sum_{i=k}^{n}\binom{n-1}{i-1} $$

So if $$\beta_k=\frac{\binom {n-1}{k-1}}{\sum_{i=k}^n\binom {n-1}{i-1}},$$ each element is in $\frac{1}{2-\beta_k}$ of the sets. So you need $2-\beta_k\leq \frac{2}{1+2\alpha},$ or $$\beta_k\geq \frac{4\alpha}{1+2\alpha}\tag1$$

Now $\beta_k$ is the conditional probability, if you flip a coin $n-1$ times, and you get at least $k-1$ heads, that you get exactly $k-1$ heads. Off the top of my head, I don’t recall how to estimate this, but I’d bet there is way to estimate with the law of large numbers, for $n,k$ large.

Of course, if $(1)$ is an inequality, we can add a number of sets of size $k-1.$ How many we can add would depend on how great the inequality is in $(1).$

When $n=2m+1,k=m+1,$ you get:

$$\beta_{k}=\frac{\binom{2m}{m}}{2^{2m}+\frac12\binom{2m}{m}}$$

Using the asymptote $\binom{2m}m\sim \frac{2^{2m}}{\sqrt{\pi m}},$

this gives $$\beta_{k}\sim \frac{1}{\sqrt{m\pi}+\frac12}.$$

And $$\frac1{2-\beta_k}\sim \frac{\sqrt{m\pi}+1/2}{2\sqrt{m\pi}}$$


If $\mathcal S$ is such a maximal family, and $T\in \mathcal S$ and $T’\notin \mathcal S$ , for some $T\subset T’,$ we can replace $T$ with $T’$ in $\mathcal S$ and get a new family with the same size that still has the property that you want.

So we can restrict our search to $\mathcal S$ that are filters - if $T\in \mathcal S,$ and $T\subseteq T’,$ then $T’\in\mathcal S.$

That’s sort of the intuition for using the families of the above sort - larger sets cover more.

This makes $\mathcal S$ entirely defined by its minimal elements. Not sure how that helps, though.

More generally, for distinct $T_1,\dots,T_m\in \mathcal S,$ and distinct $T_1’,T_2’,\dots,T_m’\notin\mathcal S,$ with $\sum|T_i|<\sum|T_i’|,$ and each $j\in [n]$ is in at least as many $T_i’$ as in $T_i,$ we can swap, also.

Foe example, if $\{1,2,3\},\{1,4,5\}\in S,$ and $\{1,2,5,7\}$ add $\{1,4,3,8\}$ are not, we can choose the sets of bigger total size. This might break the filter property, but we can still, after that, ensure the resulting set is a filter.

Basically, these sort of swaps all increase $\sum_{T\in\mathcal S}|T|.$


If $\mathcal S$ is such a family, partition into $\mathcal S_i,$ consisting of the sets of size $i.$ Then we can use a double counting to show that:

$$(\alpha+1/2)n|S|\leq \sum_i i|\mathcal S_i|$$

I think we can show that for any integers $a_0,\dots, a_n$ with $0\leq a_i\leq \binom{n}i,$ and $$\sum_i ia_i>(\alpha+1/2)n\sum a_i\tag2$$ we can find a set $\mathcal S$ with $|\mathcal S_i|=a_i.$

We might need something slightly stronger than $(2),$ however.

Basically, you select $a_i$ $i$-subsets such that for each $j,j’$ the number of occurrences of $j$ and $j’$ differs by at most one. And at the next level, you ensure that the elements that occur more often are the ones that occurred less often on previous levels.

If this is true, we’d get that our families from the first part, plus some sets of size $k-1,$ are maximal.

This is because if $i<i’,$ and $a_i>0,a_{i’}<\binom{n}{i’},$ the existence of a $\mathcal S$ for these numbers would mean the existence of a $\mathcal S’$ with $a_i-1,a_{i’}+1.$ So we’d get a family of the same cardinality but larger total size.

$\endgroup$
5
  • $\begingroup$ Very nice answer. In essence, your answer seems to show that there is a set $\mathcal{S}$ with $|\mathcal{S}|\sim 2^n/\sqrt{n}$ which satisfies the property in my question for $ \alpha \sim 1/\sqrt{n}$. I wonder if one can show that the best one can have is $|\mathcal{S}|\leq 2^n/n$, which is something I conjecture, but dont see if its true or not. If I dont get any useful answers soon, i'll mark this as answered :) $\endgroup$
    – Vaas
    Commented Apr 7, 2022 at 21:39
  • $\begingroup$ Is your conjecture also for $\alpha\sim1/{\sqrt{n}}?$ @Annonymous $\endgroup$ Commented Apr 7, 2022 at 21:46
  • $\begingroup$ my conjecture is, if $\alpha\sim1/\sqrt{n}$, then $|\mathcal{S}|\leq 2^n/n$. $\endgroup$
    – Vaas
    Commented Apr 7, 2022 at 21:48
  • $\begingroup$ But you just said in your first comment that I showed under that condition that there is an $S$ with $|S|\sim 2^n/\sqrt{n},$ which is bigger. I assumed that was based on some knowledge of estimating $\beta_k,$ because I certainly didn’t show that directly. @Annonymous $\endgroup$ Commented Apr 7, 2022 at 21:55
  • $\begingroup$ Ok i take back what I said, I dont completely see how $|\mathcal{S}|\sim 2^n/\sqrt{n}$. I simply thought one could take all sets of size $\geq (n(\alpha+1/2))$, but then the $\beta_k$s are unclear to handle. $\endgroup$
    – Vaas
    Commented Apr 8, 2022 at 1:12

You must log in to answer this question.

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