Timeline for Can we color Z^+ with n colors such that a, 2a, ..., na all have different colors for all a?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2016 at 22:43 | history | edited | domotorp | CC BY-SA 3.0 |
changed kos to pach
|
| Jan 12, 2012 at 22:53 | answer | added | Andrés E. Caicedo | timeline score: 19 | |
| Sep 28, 2010 at 21:57 | comment | added | domotorp | It is a little late but I don't see why such a graph could not contain an induced $C_5$. Suppose n is big and pick five primes that are each almost as big as n, $p_1,\ldots,p_5$. If now you take the numbers $p_1p_2, p_2p_3, \ldots, p_5p_1$, then they will form an induced $C_5$. So I guess these graphs are not perfect. | |
| Sep 25, 2010 at 13:23 | comment | added | Péter Komjáth | Using Fedor's nice remark, one possibility is to show that the graph in question is perfect. Using the recent Strong Perfect Graph Theorem, this reduces to showing that the graph does not contain, as an induced subgraph, one of the circuits $C_5,C_7,\dots$ or their complements. | |
| May 31, 2010 at 18:36 | history | edited | Greg Kuperberg |
There is evidence that it is an open problem
|
|
| May 31, 2010 at 6:16 | comment | added | Gerry Myerson | @Fedor, yes, this was a conjecture of Ron Graham, Advanced Problem 5749, Amer Math Monthly 77 (1970) 775. A solution was published by R Balasubramanian and K Soundararajan, On a conjecture of R L Graham, Acta Arith 75 (1996) 1-38, matwbn.icm.edu.pl/ksiazki/aa/aa75/aa7511.pdf | |
| May 30, 2010 at 10:43 | answer | added | Lucas K. | timeline score: 2 | |
| May 30, 2010 at 7:07 | answer | added | Greg Kuperberg | timeline score: 3 | |
| May 30, 2010 at 4:37 | answer | added | Victor Protsak | timeline score: 4 | |
| May 30, 2010 at 2:18 | comment | added | Victor Protsak | Greg, you beat me to that, I was just about post that François's trick works for $p=2n+1$ prime by coloring $a$ to $(a')^2,$ which is one of $n$ quadratic residues $\mod p.$ Unfortunately, I can't see a way to extend it to $dn+1$ with larger $d.$ | |
| May 30, 2010 at 2:10 | comment | added | Greg Kuperberg | Dorais' trick also works if $p = 2n+1$ is prime, if you define the color of $a$ to be the set $\pm a + p \mathbb{Z}$. | |
| May 29, 2010 at 22:39 | comment | added | Lucas K. | Have you checked if it is possible to color in such way that the coloring for each a is the same, except for a fixed permutation of the color? This is true for n = 3. If that is possible, then you only need to a find a coloring up to n^2 with this additional constraint. This can be checked by computer, for much larger numbers than 30. | |
| May 29, 2010 at 21:58 | history | edited | domotorp | CC BY-SA 2.5 |
added ideas
|
| May 29, 2010 at 17:29 | comment | added | Fedor Petrov | If we always may colour, that it implies that corresponding graph does not have $(n+1)$-clique, i.e. for any set of $n+1$ positive integers there exist two, $a<b$ such that $b/gcd(a,b)>n$. As I remember, it is quite hard statement itself... | |
| May 29, 2010 at 17:17 | answer | added | gowers | timeline score: 4 | |
| May 29, 2010 at 15:54 | answer | added | Ewan Delanoy | timeline score: 3 | |
| May 29, 2010 at 14:06 | comment | added | François G. Dorais | The case when $p = n+1$ is prime is easy: for $a \geq 1$, write $a = a'p^e$ where $p \nmid a'$, then define the color of $a$ to be $a' + p\mathbb{Z}$. | |
| May 29, 2010 at 13:41 | history | asked | domotorp | CC BY-SA 2.5 |