Discrete Math, Second series, 9th Problem Set (August 6)
REU 2003

Instructor: László Babai
Scribe: Daniel Štefankovic

Recall that $\chi(X)$ is the chromatic number of $X$ and $\alpha(X)$ is the independence number of $X$ (size of the largest independent set). (An independent set, or anticlique, is a set of pairwise non-adjacent vertices).

This preceding exercise shows that $\chi(X)$ can be much larger (by a factor of $\Omega(n)$) than its lower bound $n/\alpha(X)$, so this lower bound is far from being tight. Contrast this with the situation for vertex-transitive graphs:

Definition 0.1   A sequence $a_1,\dots,a_n$ is unimodal if there is $k$ such that $a_1,\dots,a_k$ is increasing and $a_{k},\dots,a_n$ is decreasing (not necessarily strictly). A sequence $a_1,\dots,a_n$ is log-concave if $a_{i-1}a_{i+1}\leq a_i^2$ for all $i$.

Definition 0.2   A graph $X$ is distance-transitive if $\forall a,b,x,y\in V(X)$ if ${\rm dist}(a,b)={\rm dist}(x,y)$ then $(\exists g\in \mathop{\rm Aut}X)(a^g=x,b^g=y)$.

Kneser's graph $K(n,s)$, $n\geq 2s+1$ has ${n\choose s}$ vertices corresponding to the subsets of $[n]$ of size $s$ with two vertices being adjacent if the corresponding sets are disjoint. Johnson's graph $J(n,s)$, $n\geq s+1$ has ${n\choose s}$ vertices corresponding to the subsets of $[n]$ of size $s$ with two vertices being adjacent if the corresponding sets have symmetric difference of size $2$.

Let $S(x,r)$ denote the sphere of radius $r$ about vertex $x$, i.e.

$$S(x,r)=\{y\in V(X)\,\vert\,{\rm dist}(x,y)=r\}.$$

Let $B(x,r)$ be the ball of radius $r$ around vertex $x$, i.e.

$$B(x,r)=\{y\in V(X)\,\vert\,{\rm dist}(x,y)\leq r\}.$$

Lemma 0.3 (Gromov)   Let $X$ be a vertex-transitive graph. Let $f(r)=\vert B(x,r)\vert$ for some $x$. Then

$$f(r)f(5r)\leq f(4r)^2.$$

In Gromov's Lemma, $X$ may be infinite but it must be locally finite (the vertices have finite degree).