# Combinatorics - how many $c$-distinct sets are possible?

I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here.

I am given two parameters $$m\in\mathbb{N}$$ and $$\frac{1}{2}< p\le 1$$, and I want to find the maximal value $$k\in \mathbb{N}$$, such that there are $$A_1,\dots,A_k\subseteq [m]$$ for $$[m]=\{1,\dots,m\}$$ and, we have the two following properties:

1. For every $$1\le i\le k$$, we have $$|A_i| \ge p\cdot m$$
2. For every $$i\neq j$$, we have $$|A_i\cap A_j|\le (1-p)\cdot m$$

Essentially, I'm trying to find the maximal number of sets with size $$p\cdot m$$, who are $$c$$-far from being distinct in pairs, where $$c:=(1-p)\cdot m$$.

Equivalently, I'm interested in finding for every $$k$$ what is the highest $$p$$ with this property.

## My attempt

I tried to think of an approach similar to one where $$p=1$$, and the sets would be completely disjoint, therefore every $$A_i$$ would add an additional $$p\cdot m$$ new elements, and thus $$k=\frac{m}{p\cdot m}=\frac{1}{p}$$. But this approach didn't work for me, since even if I say each set adds an additional $$p\cdot m - (1-p) \cdot m = (2p-1)\cdot m$$ new elements to every other set, I can't guarantee those elements are not in other sets.

After thinking additionally a bit, I think that one thing that would suffice for me is to show that the solution doesn't depend on $$m$$.

This is because in my usage of this problem, I actually try to find a $$k$$ such that this property won't hold, and I can choose my $$k$$ to be arbitrarily large but it would also increase $$m$$ arbitrarily. So - if the solution here won't depend on $$m$$, I don't need to worry about increasing $$m$$ arbitrarily.

• If $p > 2/3$ then any two sets have intersection at least $(2p-1)m > m/3 > (1-p)m$, and so $k \leq 1$. May 23, 2021 at 14:04
• Yes I already managed to prove this (and something a bit stronger than this, in fact, but I didn't include it here since it would change the problem's definition). The actual problem I'm trying to solve is for $p=\frac{2}{3}$, and I want to see what the maximal $k$ is in this case. If the maximal $k$ is too large (when compared to $m$) for my usage case, then I would be interested in even lower values of $p$, and hence I asked this general question. May 23, 2021 at 14:17
• Just to note what I'm trying to achieve using this question: I'm trying to prove a lower bound on $dMA$ protocols for a certain problem, and solving this question would allow me to know if my thinking strategy could work in this case. May 23, 2021 at 14:20
• If $|A_i| = pm$ then the condition on the intersection is equivalent to $|A_i \Delta A_j| \geq (4p-2)m$, and so you're interested in the size of constant-weight codes. May 23, 2021 at 14:52
• So, is this an open problem in the area of ECCs? May 23, 2021 at 15:21

This is a partial answer for $$p > \frac{\sqrt{5}-1}{2} \approx 0.618.$$ As Yuval Filmus points out in the comments, we are looking for the maximum number $$k$$ of binary codes with length $$m$$, weight $$w = pm$$ and pairwise distance at least $$d = 2(2p-1)m$$. If $$p>2/3$$ then $$k\leq 1$$.
Now let $$\lambda = w-d/2$$. Equation (3) in  tells us that if $$w^2>\lambda m$$ (which is the case when $$p > \frac{\sqrt{5}-1}{2}$$), then $$k \leq \frac{m\cdot d/2}{w^2-\lambda m}.$$ This works out to $$k \leq \frac{2p-1}{p^2+p-1}.$$
In particular for the case which seems to interest you the most ($$p=2/3$$) this gives an upper bound of $$k\leq 3$$ (which is easily seen to be tight).
I wasn't able to apply the other formulas in  to get anything subexponential in $$m$$ when $$\frac{1}{2} < p \leq \frac{\sqrt{5}-1}{2}$$, but I applied the bounds very crudely, so it might be possible (might even be easy).