# 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 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 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 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 at 14:52