5
$\begingroup$

Let $D\subseteq\mathbb{N}^+$, and consider the graph $G_D$ with vertices set $\mathbb{N}$ and edges set $\{(x,y)\in\mathbb{N}\times\mathbb{N}\;s.t.\;|x-y|\in D\}$. I expect that if $D$ is dense enough in $\mathbb{N}^+$, then the chromatic number of $G_D$ is large. As Wojowu pointed out in the comments, positive density does not guarantee infinite chromatic number. Hence, one can ask the following question:

if $D$ has density (say, e.g., lower asymptotic density) one in $\mathbb{N}^+$, is it true that the chromatic number of $G_D$ is infinite?

Thank you for any suggestion.

Improve this question
$\endgroup$
12
  • 4
    $\begingroup$ 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. $\endgroup$
    – Wojowu
    Commented Jun 8, 2020 at 17:22
  • 4
    $\begingroup$ 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$). $\endgroup$
    – Pat Devlin
    Commented Jun 8, 2020 at 17:49
  • 2
    $\begingroup$ (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$) $\endgroup$
    – Pat Devlin
    Commented Jun 8, 2020 at 17:53
  • 3
    $\begingroup$ @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. $\endgroup$
    – Benoît Kloeckner
    Commented Jun 8, 2020 at 18:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Anthony Quas
    Commented Jun 8, 2020 at 20:41

2 Answers 2

Reset to default
4
$\begingroup$

I'll show that if $G_D$ has chromatic number $k$ then $D$ has upper Banach density at most $(k-1)/k$.

So suppose $G_D$ has chromatic number $k$. Let $\mathbb{N}$ be partitioned into $P_1,\ldots,P_k$, where each $P_i$ is independent with respect to $G_D$. Without loss of generality, $P:=P_1$ has upper Banach density at least $1/k$. Let $Q=\{|x-y|:x,y\in P\text{ are distinct}\}$. Then $Q\subseteq \mathbb{N}^+\backslash D$ since $P$ is $G_D$-independent. We claim that $Q$ has lower Banach density at least $1/k$, which implies the desired result for $D$.

(The proof of the claim is an adaptation of Ruzsa's Covering Lemma and/or the well-known fact that if a set $A$ of integers has positive upper Banach density then $A-A$ is syndetic.)

Call a set $X\subset\mathbb{N}$ $P$-separating if $(x+P)\cap (y+P)=\emptyset$ for all distinct $x,y\in X$. Since $P$ has upper Banach density at least $1/k$, it follows that any $P$-separating subset of $\mathbb{N}$ has size at most $k$. So we may choose a $P$-separating set $X$ of maximal size. Now fix $a\in\mathbb{N}^+$ such that $a>\max X$. By maximality, there is some $x\in X$ such that $(a+P)\cap (x+P)\neq\emptyset$. So there are $p,q\in P$ such that $a+p=x+q$. Since $a>x$ it follows that $a\in x+Q$.

Altogether, we have shown that $X+Q$ is cofinite in $\mathbb{N}^+$. Since $|X|\leq k$, it follows that $Q$ has lower Banach density at least $1/k$.


Remark. The proof actually shows that if $G_D$ has chromatic number $k$ then there are $k$ translates of the complement of $D$ whose union is cofinite in $\mathbb{N}^+$, which I suppose is stronger than saying $D$ has upper Banach density at most $(k-1)/k$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice answer, thank you! $\endgroup$
    – Capublanca
    Commented Jun 9, 2020 at 0:20
  • $\begingroup$ The upper bound is tight (as suggested in Ilya Bogdanov's answer and observed earlier in the comments by Wojowu). If $D$ is the set of natural numbers not divisible by $k$ then $D$ has density $(k-1)/k$, and $G_D$ is $k$-colorable via the partition into equivalence classes modulo $k$. $\endgroup$
    – Gabe Conant
    Commented Jun 9, 2020 at 12:25
4
$\begingroup$

Assume that the chromatic number is $k$. Among the numbers $1,2,\dots, N$ there are at least $N/k$ numbers of the same color, say $a_1,\dots, a_t$. Then $D$ does not contain at least $t-1\geq N/k-1$ numbers not exceeding $N-1$, namely $a_i-a_1$, $i\geq2$. Thus the density of $D$ is at most $1-1/k$. Surely, this estimate is tight...

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer! $\endgroup$
    – Capublanca
    Commented Jun 9, 2020 at 0:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .