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

1 Answer 1

1
$\begingroup$

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 [1] 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 [1] 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).

[1] Selmer Johnson, Upper Bounds for Constant Weight Error Correcting Codes, 1972.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.