Lower bound for the chromatic number of $\mathbb{R}^n$

141 Views Asked by At

I'm going through a proof that of the following lower bound for the chromatic number of $\mathbb{R}^n$:

$$\chi(\mathbb{R}^n) \geq (1.2 + o(1))^n$$

At some point in the proof we get that

$$\chi(\mathbb{R}^n) \geq \frac{\binom{n}{2q-1}}{\binom{n}{q-1}}$$ and it remains to maximize this ratio for some $q$ a power of prime.

I'm not familiar with this kind of procedure and I don't really know where to start... How can we show that $(1.2 + o(1))^n$ is a lower bound ?

1

There are 1 best solutions below

0
On

Use Stirling's approximation $n! = \sqrt{2\pi n}(n/e)^n (1+o(1))$

We have ${n\choose 2q-1}/{n \choose q-1} = \frac{(n-q+1)!(q-1)!}{(n-2q+1)!(2q-1)!}$

So this equals (the combined square root term is $(1+o(1))$ and the powers of $e$ exactly cancel):

$\frac{(n-q+1)^{n-q+1} (q-1)^{q-1}}{ (n-2q+1)^{n-2q+1}(2q-1)^{2q-1}}(1+o(1))$

Let's test this with $q = rn$ where $0 < r < 1/2$. Then we have:

$\left[\frac{(1-r)^{1-r} r^r}{ (1-2r)^{1-2r} (2r)^{2r}} + o(1)\right]^n$

(The powers of the form $n^n$ exactly cancel. All other terms/adjustments not included here are either explicitly of the form $(1+o(1))^n$ or are $n^{a}$, which is also $(1+o(1))^n$.)

The inside $f(r) = \frac{(1-r)^{1-r} r^r}{ (1-2r)^{1-2r} (2r)^{2r}}$ is maximized at $r \approx .146$ with value of approximately $1.207$. (I just did this part numerically.)

In fact, for $.12 \leq r \leq .17$ we have $f(r) \geq 1.2$.

So if you can prove that for $n$ sufficiently large there's always a prime power $q$ with $.12 n \leq q \leq .17 n$ then you're good. In fact it's fine to restrict just to primes; the prime number theorem guarantees this for primes.