Timeline for Graphs on $\{0,1\}^n$ based on fixed Hamming distance
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2020 at 7:58 | comment | added | Joseph Gordon | Ah, I somehow thought that Hadamard matrix is required to have the same number of $0$'s and $1$'s in each row (which is quite stupid of me since the rank couldn't be full that way) | |
| Oct 21, 2020 at 5:40 | comment | added | Dominic van der Zypen | Thanks @AntoineLabelle! | |
| Oct 20, 2020 at 21:39 | comment | added | Antoine Labelle | I don't understand, the all-zeros vector has nothing special since the graph is vertex transitive. Here is how I see the equivalence: replacing $\{0,1\}^n$ by $\{-1,1\}^n$, two vectors are connected by an edge iff they are orthogonal. Now, an Hadamard matrix correspond to a choice of $n$ pairwise orthogonal vectors, i.e. an $n$-clique in the graph. Hence the clique number being $n$ is equivalent to the existence of an Hadamard matrix. | |
| Oct 20, 2020 at 19:03 | comment | added | Joseph Gordon | @AntoineLabelle well, I expect the equivalence to Hadamard conjecture you mean is the one I described in this comment. Then we need to add $1$ to account for all-zeros vector, don't we? | |
| Oct 20, 2020 at 18:19 | comment | added | Antoine Labelle | @DominicvanderZypen I found some additionnal information for the chromatic number in this special case. It is known that the chromatic number is $\ge n$ with equality if and only if $n$ is a power of $2$: arxiv.org/pdf/math/0509151.pdf | |
| Oct 20, 2020 at 14:24 | comment | added | Dominic van der Zypen | Thanks Antoine for making the connection to the Hadamard matrix conjecture! - It would also be nice to know whether at least the clique number and the chromatic number agree, but this may be open as well | |
| Oct 20, 2020 at 14:23 | vote | accept | Dominic van der Zypen | ||
| Oct 20, 2020 at 13:27 | comment | added | Antoine Labelle | Why would it be $n+1$? | |
| Oct 20, 2020 at 13:19 | comment | added | Joseph Gordon | $n$, not $n+1$? | |
| Oct 20, 2020 at 13:09 | history | answered | Antoine Labelle | CC BY-SA 4.0 |