Timeline for Graphs on $\{0,1\}^n$ based on fixed Hamming distance
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2020 at 19:20 | comment | added | Joseph Gordon | The upper bound, I think, is given by Fisher's inequality (which is stated in a various number of ways, see e.g. this for relevant statement) | |
| Oct 20, 2020 at 14:23 | vote | accept | Dominic van der Zypen | ||
| Oct 20, 2020 at 13:09 | answer | added | Antoine Labelle | timeline score: 5 | |
| Oct 20, 2020 at 12:55 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
forgot the $|..|$ in the definition of the Hamming distance
|
| Oct 20, 2020 at 12:52 | comment | added | Dominic van der Zypen | That's right, thanks @JosephGordon, I should have restricted the question to even $k$ | |
| Oct 20, 2020 at 12:50 | comment | added | Joseph Gordon | Note that for odd $k$ the graph is bipartite (color by parity of the number of $1$'s). For even $k$ quantity $\omega(G_{n,k})-1$ corresponds to the maximal number of $k$-subsets of $[n]$ with pairwise intersections of size $k/2$ (clique containing $(0,0,...)$ looks in such a way). | |
| Oct 20, 2020 at 12:34 | answer | added | Steve Huntsman | timeline score: 2 | |
| Oct 20, 2020 at 11:14 | comment | added | Gordon Royle | Not 3. This is the famous result of Payan that cubelike graphs never have chromatic number 3 (or clique number). Your graphs, called “distance graphs” by Payan are special cases of cubelike graphs. Start here core.ac.uk/download/pdf/82733314.pdf for more including a reference to a paper by Dvorak et al. | |
| Oct 20, 2020 at 10:26 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |