19-25 June 2011

Bled, Slovenia

Europe/Ljubljana timezone

# The chromatic numbers of distance graphs and applications to combinatorial problems.

Presented by Mr. Andrey KUPAVSKII

Type: Oral presentation

Track: Coloring, independence and forbidden subgraphs

## Content

We consider \textit{distance graphs in $\mathbb{R}^n$}. The sets of vertices of these graphs are subsets of $\mathbb{R}^n.$ Two vertices are connected by an edge if the distance between them is exactly $d$. This work deals with distance graphs $G=G(n,m,\{a_0, a_1, \ldots, a_m\},x) = (V,E)$ of certain type. Namely, such graphs have the sets of vertices
$$V =\{y=(y_1,\ldots,y_n), y_i\in \{0,1,\ldots,m\}, $$
$$\ \ \ \ \ \ |\{i:y_i=j\}|=a_jn\ \ \forall j=0,\ldots,m, \ a_i\in(0,1), a_0+a_1+\ldots +a_m=1\}$$
and the sets of edges $$E=\{\{y_1,y_2\}| y_1,y_2\in V, (y_1,y_2)=xn\}.$$
We managed to prove the following theorem.
\begin{thm} Let $m=1, a_1=a, x>0, a,x\in \mayhbb{Q},$ and consider the sequence of dimensions $n_1, n_2,\ldots,$ which satisfies the condition $an_i, xn_i\in \mathbb{N}.$ Consider distance graphs $G_i=G(n_i,1,\{1-a,a\},x)$. Let $k$ be a natural number, $k\ge 3$.
If $$x<\frac{(ka)^2-\{ka\}^2-[ka]}{k(k-1)}=f_1,$$
then $G_i$ do not contain complete subgraphs (cliques) on $k$ vertices.
Moreover, this bound is in some sense sharp. Namely, there exists a constant $c=c(k,a),$ such that in the sequence of dimensions $cn_1, cn_2,\ldots$ graphs $\tilde{G}_i=G(cn_i,1,\{1-a,a\},f_1)$ contain complete subgraphs on $k$ vertices.
\end{thm}
We proved similar theorems for bigger values of $m$. We applied these results to the following problem. Let $G$ be a distance graph in $\mathbb{R}^n$, that does not contain cliques of size $k$. How large can the chromatic number of such graph be?
This problem is related to the classical problem of finding the value
$ \chi(\mathbb {R}^n) $ which is equal to the minimum number of colors needed to paint all the points in $ \mathbb {R}^n $ so that any two points at distance 1 apart receive different colors. It is known, that
$$(1.239+o(1))^n\le\chi(\mathbb{R}^n)\le (3+o(1))^n.$$
We obtained new exponential lower bounds for the chromatic number of $k$-clique-free distance graphs for small $k\ge 4$.
Another application is related to well-known Borsuk's problem -- the problem of finding the minimum number $f(n)$ of parts of smaller diameter, into which an arbitrary set of diameter 1 in $ \mathbb {R}^n $ can be divided. Famous Borsuk's conjecture states that $ f(n) = n+1 $? We study some modification of Borsuk's problem. Namely, we consider sets of diameter 1, lying on the spheres $ S_r^{n-1}$ of radius $r$. Using graphs of the above described type, we managed to prove the following theorem:
\noindent {\bf Theorem 1.} {\it Let $ S_r^{n-1} \subset {\mathbb R}^n $ be the sphere of radius $ r $ with center at the origin.
For any $ r > \frac{1}{2} $, there exists a $ n_0 = n_0(r) $ such that for every $ n \ge n_0 $,
one can find a set $ \Omega \subset S_r^{n-1} $ which has diameter 1 and does not admit a partition into $ n+1 $ parts of smaller diameter.}
The work is done under the financial support of the grant 09-01-00294 of the Russian Foundation for Basic Research
and the grant MD-8390.2010.1 of the Russian President.

## Place

Location: Bled, Slovenia

Address: Best Western Hotel Kompas Bled