4
$\begingroup$

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.


Some (additional) thoughts

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.

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$ May 23 at 14:04
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    May 23 at 14:17
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    May 23 at 14:20
  • $\begingroup$ 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. $\endgroup$ May 23 at 14:52
  • $\begingroup$ So, is this an open problem in the area of ECCs? $\endgroup$
    – nir shahar
    May 23 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.