Timeline for Combinatorics - how many $c$-distinct sets are possible?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2023 at 13:46 | vote | accept | nir shahar | ||
| Dec 7, 2021 at 15:43 | answer | added | Tassle | timeline score: 1 | |
| May 23, 2021 at 15:29 | comment | added | Yuval Filmus | The answer might be known for your parameters. | |
| May 23, 2021 at 15:21 | comment | added | nir shahar | So, is this an open problem in the area of ECCs? | |
| May 23, 2021 at 14:52 | comment | added | Yuval Filmus | 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:20 | comment | added | nir shahar | 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:17 | comment | added | nir shahar | 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:04 | comment | added | Yuval Filmus | 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 11:24 | history | edited | nir shahar | CC BY-SA 4.0 |
added 510 characters in body
|
| May 23, 2021 at 10:27 | history | edited | nir shahar | CC BY-SA 4.0 |
added 447 characters in body
|
| May 23, 2021 at 10:19 | history | asked | nir shahar | CC BY-SA 4.0 |