Timeline for Chromatic number of distance graphs over the integers
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2020 at 3:58 | comment | added | Pat Devlin | This post, subsequent comments, and answers all seemed to go quite well with everybody being very cordial! Yay community! :-) [PS, I was getting groceries, so I forgot to reply for a bit, but I didn’t feel like writing an answer since it didn’t feel like the right proof anyway! What’s there now feels much better.] | |
| Jun 9, 2020 at 1:24 | history | became hot network question | |||
| Jun 9, 2020 at 0:23 | comment | added | Capublanca | @Anthony Quas, thank you for the reference | |
| Jun 9, 2020 at 0:19 | vote | accept | Capublanca | ||
| Jun 8, 2020 at 20:41 | comment | added | Anthony Quas | Maybe you're familiar with the following somewhat-related paper, showing that if $D$ grows exponentially, then the chromatic number is finite. Katznelson, Y.(1-STF) Chromatic numbers of Cayley graphs on $\mathbb Z$ and recurrence. (English summary) Paul Erdős and his mathematics (Budapest, 1999). Combinatorica 21 (2001), no. 2, 211–219. | |
| Jun 8, 2020 at 19:54 | answer | added | Gabe Conant | timeline score: 4 | |
| Jun 8, 2020 at 19:52 | answer | added | Ilya Bogdanov | timeline score: 4 | |
| Jun 8, 2020 at 19:37 | comment | added | Gabe Conant | I'll post a proof of what I've claimed. But if one of the earlier commenters posts theirs then it should be accepted over mine. | |
| Jun 8, 2020 at 19:26 | comment | added | Capublanca | Thank you everybody for the interesting comments! If all of you prefer, I can edit the post by summarizing what you said so far, and by posing more refined questions. Otherwise, I keep the actual post and accept the answer of who want to write it. | |
| Jun 8, 2020 at 18:45 | comment | added | Gabe Conant | I believe infinite chromatic number also follows from the weaker assumption of $D$ having upper Banach density 1. However, the argument is different from what @BenoîtKloeckner has written (based on the comments of @PatDevlin) since two sets of upper Banach density 1 need not intersect. | |
| Jun 8, 2020 at 18:25 | comment | added | Benoît Kloeckner | One gets this way, with a crude estimate, that if the lower density of $D$ is at least $1-\frac{2}{k(k+1)}$ then $G_D$ has a $k$-clique, and in particular has chromatic number at least $k$. There might be lots of interesting follow-up questions in this. | |
| Jun 8, 2020 at 18:20 | comment | added | Benoît Kloeckner | @PatDevlin: you should post an answer, this solves the question. Actually, you only need to say that if $D$ has density $1$, then so does $D_2:=\{x\in\mathbb{N}|2x\in D\}$, and so do $D_3$, ..., $D_k$. Then $D\cap D_2\cap \dots\cap D_k$ has density one, and is non empty. You get a $k$-clique. | |
| Jun 8, 2020 at 17:53 | comment | added | Pat Devlin | (E.g., $\epsilon = 1/k^2$ can be proven by noting there are at least $n/k$ such sets the complement must intersect, and any element meets at most $k$ of these. So the complement has size at least $n/k^2$) | |
| Jun 8, 2020 at 17:49 | comment | added | Pat Devlin | Following up on this comment, if the density is big, you’ll have big cliques (and thus big chromatic number). That is, if you insist there are no $k$-element cliques, then in particular $D$ has no sets of the form $x, 2x, ..., kx$. But this means $D$ has at most $(1-\varepsilon)N$ elements less than $N$ (for some $\varepsilon > 0$ depending on $k$). | |
| Jun 8, 2020 at 17:37 | comment | added | Capublanca | Sure, thank you a lot for pointing it out. I edited the question, focusing on the case of density one. | |
| Jun 8, 2020 at 17:34 | history | edited | Capublanca | CC BY-SA 4.0 |
added 82 characters in body
|
| Jun 8, 2020 at 17:22 | comment | added | Wojowu | If $D$ contains no numbers divisible by $k$, then the graph is $k$-colorable, by coloring each residue class modulo $k$ differently. Hence for no $d<1$ does density $d$ guarantee infinite chromatic number. On the other hand, I believe density equal to $1$ is sufficient to guarantee that. | |
| Jun 8, 2020 at 17:14 | history | asked | Capublanca | CC BY-SA 4.0 |