Timeline for Maximizing the mutual Hamming distance in $\big[{\cal P}([n])\big]^n$
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 26 at 15:35 | answer | added | Claude Chaunier | timeline score: 3 | |
| Aug 26 at 9:11 | comment | added | Dominic van der Zypen | Excellent @ClaudeChaunier - I have just updated the hypothesis in the question above. | |
| Aug 26 at 9:09 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
updated hypothesis
|
| Aug 26 at 8:51 | comment | added | Claude Chaunier | HiGHS again shows $M_{17}=8, M_{18}=9, M_{19} = M_{20} = 10, M_{21} \le 10, M_{23} = 12, M_{25} \le 12$, confirming your guess, as so far it looks like $M_{2k}=k$ when $k\ge 2$ and $M_{2k+1} = k$ when $k$ is even and $M_{2k+1} = k+1$ when $k$ is odd. That suggests the optimal solutions might have general patterns. | |
| Aug 26 at 8:34 | comment | added | Claude Chaunier | You are welcome, it is interesting. Here is a small improvement on Kodlu's upper bound that speeds up proofs and explorations by several magnitudes. When $u_i\in\{-1,1\}^n$ with $n$ odd, we have $\sum_{i=1}^n u_i\in (2\mathbb{Z}+1)^n$ hence $|\sum_{i=1}^n u_i|^2\ge n$. Then if the $n$ sets in $\mathcal{P}(n)$ are all at mutual Hamming distance $d$ or more, we find $d\le\frac{n+1}{2}$ and equality is only possible if the sets are all exactly at the same distance $d$. Add that substantial tight constraint when looking for a solution with minimal distance $\frac{n+1}{2}$ or proving there aren't. | |
| Aug 26 at 7:30 | comment | added | Dominic van der Zypen | Thanks @ClaudeChaunier for the effort that you put into this! | |
| Aug 25 at 18:34 | comment | added | Claude Chaunier | HiGHS linear optimization solver yields $M_{14}=7$ and $M_{15}=M_{16}=8$ by finding valid examples which are reaching kodlu's upper bound $\frac{n^2}{2(n-1)}$. | |
| Aug 23 at 17:51 | comment | added | Claude Chaunier | Chuffed (a lazy clause generation solver) says $M_{13}= 6 = k$. | |
| Aug 22 at 15:07 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
added 135 characters in body
|
| Aug 22 at 15:03 | comment | added | Dominic van der Zypen | @RobPratt Apologies for my sloppiness! | |
| Aug 22 at 12:46 | comment | added | RobPratt | @DominicvanderZypen $M_9=4\not=5$ | |
| Aug 22 at 6:48 | comment | added | Dominic van der Zypen | Thanks @RobPratt! Hypothesis: $M_{2k} = k$ for $k>1$ and $M_{2k+1} = k+1$ for $k>2$? | |
| Aug 21 at 21:03 | history | edited | RobPratt |
edited tags
|
|
| Aug 21 at 19:43 | comment | added | RobPratt | Integer linear programming yields $M_2=M_3=M_4=M_5=2$, $M_6=3$, $M_7=M_8=M_9=4$, $M_{10}=5$, $M_{11}=M_{12}=6$. | |
| Aug 21 at 15:53 | comment | added | Karl Fabian | Brute force gives $M_5=2$ and random tests provide the lower bounds $M_6,M_7\geq 3$, $M_8,\ldots,M_{13} \geq 4$, $M_{14},\ldots,M_{16} \geq 5$, and $M_{17}\geq 6$. | |
| Aug 21 at 14:21 | comment | added | Claude Chaunier | Wouldn't it be worth mentioning @kodlu's upper bound [mathoverflow.net/a/319790/127616] which looks like $k+1$ ? | |
| Aug 21 at 14:01 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |