Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces

Abstract

We prove the existence in rational spaces of distance graphs without short odd cycles whose chromatic number increases exponentially with the dimension of the space.

1. Introduction

The problem of finding the chromatic number $\chi(\mathbb R^n)$ of Euclidean space $\mathbb R^n$ was posed by E. Nelson and H. Hadwiger in the middle of the 20th century. This is the quantity whose value is equal to the smallest number of colors sufficient for coloring all points of $\mathbb R^n$ so that the distance between points of the same color does not equal $1$ (the distance $1$ is called forbidden). Note that the quantity $\chi(\mathbb R^n)$ does not depend on the value of the positive number taken as the forbidden distance. At present, this problem is one of the classical problems of combinatorial geometry. The main results for a real space are listed, for example, in [1]–[3]. In fact, this problem can also be formulated for the case of an arbitrary metric space $\mathbb X$ with metric $\rho$ and forbidden distance $d$. We denote such a chromatic number by $\chi((\mathbb X,\rho),d)$. In 1976, Benda and Perles (see [4]) proposed considering $\mathbb X=\mathbb Q^n$, $\rho=\ell_2$, where $\ell_2$ is the Euclidean metric. The value of the chromatic number of the space $\mathbb Q^n$ depends on the forbidden distance, which, for any two points with rational coordinates, is either a rational number or a quadratic irrationality. For the chromatic numbers of a rational space, many results were obtained. For small space dimensions, they are listed in [5]. For increasing dimension, the following is known.

For $d\in\mathbb Q$, the following bound was obtained by Raigorodskii in [6]:

$$\chi((\mathbb Q^n,\ell_1),d)\ge(\zeta_2+o(1))^n,\qquad \zeta_2=\frac{(1+\sqrt{3}\,)}{2}\mspace{2mu}.$$

It was proved in that paper that, for any $u\in\mathbb N$ and $d\in\mathbb Q$, there exists an $\varepsilon=\varepsilon (u)>0$, such that the following estimate holds:

$$\chi((\mathbb Q^n,\ell_u),d)\ge(1+\varepsilon+o(1))^n.$$

The following bounds are also known:

$$(1.199+o (1))^n\le\chi((\mathbb Q^n,\ell_2),1) \le\chi((\mathbb R^n,\ell_2),1)\le(3+o(1))^n.$$

The lower bound is due to Ponomarenko and Raigorodskii (see [7], [8]), while the upper bound is due to Larman and Rogers (see [9]).

In Demidovich’s paper [10], for some irrational values of $d$ and increasing $n$, a number of estimates were obtained for $\chi((\mathbb Q^n,\ell_u), d)$ in the case $u\ge 2$ and $d=\sqrt[u]{2p^\alpha}$, where $p$ is a prime and $\alpha\in\mathbb N$.

By a distance graph with forbidden distance $d\in\mathbb R_+$ in a metric space $(\mathbb X,\rho)$ we mean a graph $G=(V, E)$ whose vertex set $V$ satisfies $V\subseteq\mathbb X$, and the edge set $E$ satisfies

$$E=\{\{x,y\}:x,y\in V,\,\rho(x,y)=d\}. $$

(1.1)

The interest in the study of distance graphs is motivated by the fact that they arise naturally in relation to the problem of the chromatic number of a space. Indeed, take the graph $G=(V,E)$, which has, for example,

$$V=\mathbb R^n,\qquad E=\{\{\overline x,\overline y\}:\ell_2(\overline x,\overline y)=1\}.$$

Consider its chromatic number $\chi(G)$ (the minimum number of colors in which all the vertices of the graph can be colored so that it does not have edges with ends of the same color). It is clear that $\chi(\mathbb R^n)=\chi(G)$. By the Erdős–de Bruijn theorem, it suffices to limit ourselves to the study of finite distance graphs.

In 1959, Erdős obtained the following result (see [11]).

Theorem 1.

For any natural numbers $k\ge 2$ , $\ell\ge 2$ , there exists a graph whose chromatic number is greater than $k$ and the length of the minimal simple cycle is greater than $\ell$ .

The length of the shortest cycle is called the girth of the graph $G$ and is denoted by $g(G)$. In other words, the theorem states that there are graphs with an arbitrarily large chromatic number $\chi(G)$ and arbitrarily large girth.

We are interested in whether there are similar graphs (without short cycles but with large chromatic number) among distance graphs in $(\mathbb Q^n,\ell_2)$. We prove the existence of distance graphs in $(\mathbb Q^n,\ell_2)$ with chromatic number increasing exponentially with $n$ and without short odd cycles (in what follows, we will explain the reason for the prohibition of odd cycles). Let us give the necessary definitions.

Let $a'_1$ be a positive real number less than $1$. For each natural $n$, we put $a_1=\lfloor a_1'n\rfloor$, and let $q=q(n)$ be a sequence of natural numbers.

Definition.

Consider the sequence $\{G_n(a_1, q)\}_{n\in\mathbb N}=\{G_n\}_{n\in\mathbb N}$, where $G_n=(V_n, E_n)$ are graphs with vertex sets

$$V_n=\{\overline x=(x_1,\dots,x_n):x_i\in\{0,1\},\,|\{i: x_i=1\}|=a_1\}$$

and edge sets

$$E_n=\{\{\overline x,\overline y\}:\ell_2(\overline x,\overline y)=\sqrt{2q}\,\}.$$

Let $\mathbb X$ be either $\mathbb R$ or $\mathbb Q$. Let us set

$$\begin{aligned} \, \zeta^{\mathrm{girth}}_k(\mathbb X) =\sup\bigl\{&\zeta: \exists\mspace{1mu}\text{ a function }\delta =\delta(n)\text{ such that }\lim_{n\to\infty}\delta (n)=0 \\ &\text{and }\forall\mspace{1mu}n \exists \text{ a distance graph }G\text{ in }(\mathbb X^n,\ell_2), \\ &\text{ which has }g(G)>k,\,\chi(G)\ge(\zeta+\delta(n))^n\bigr\}. \end{aligned}$$

In [12]–[16], this quantity was already studied for the case of real space, i.e., for $\mathbb X=\mathbb R$. It was shown in [12] that the graphs $G_n$ do not help to find a bound for this quantity because of the following theorem.

Theorem 2.

Let $a_1'$ be such that, for $a_1$ , the following inequalities hold:

$$a_1\le\frac{n}{2}\mspace{2mu},\qquad a_1-q\ge 1.$$

Then, for any fixed natural $k$ satisfying the condition

$$2\le k\le q, $$

(1.2)

there is a cycle of length $2k$ in the graph $G_n(a_1, q)$ .

The condition $a_1\le n/2$ does not restrict generality, because, in the case $a_1\ge n/2$, we can consider the graph $G_n(n-a_1,q)$ isomorphic to $G_n(a_1,q)$. By Theorem 2, the graphs $G_n$ do not help to find a bound for $\zeta_k^{\mathrm{girth}}(\mathbb X)$ in all cases except, possibly, $a_1=q$, and also for $q=1$. In the latter case, the graph $G_n(a_1, q)$ always contains $C_4$. Indeed, it is formed by the vertices with coordinates

$$\begin{gathered} \, (1,\dots,1,0,\dots,0),\quad (0,1,\dots,1,0,\dots,0), \\ (0,0,1,\dots,1,0,\dots,0),\quad (1,0,1\dots,1,0,1,0,\dots,0). \end{gathered}$$

In the case $a_1=q$, we obtain a Kneser graph. If $a_1=q=\lfloor n/2\rfloor$, then the chromatic number of the graph is small and equal to $n-2\lfloor n/2\rfloor+2$. If $a_1=q\le n/2-1$, then there exists a subgraph in the graph which is isomorphic to $C_4$, the cycle of length $4$. Indeed, it is, for example, formed by the following vertices:

$$(1,\dots,1,0,\dots,0),\quad (0,\dots,0,1,\dots,1),\quad (0,1,\dots,1,0,\dots,0),\quad (0,\dots,0,1,\dots,1,0).$$

In the paper [12], the following lemma was proved.

Lemma 1.

Let $nk/(2k+1)<q$ , where $q$ is prime. Then the graph $G_n(a_1, q)$ has no odd cycles of length at most $2k+1$ .

Note that, in the paper, the lemma is formulated for a prime $q$ (since this is sufficient to use this lemma in the proof of the main result), but, in the proof, it is not required that $q$ be prime.

Theorem 2 and Lemma 1 motivate the consideration of the following quantity. Denote by $g_{\mathrm{odd}}(G)$ the length of the shortest odd cycle in $G$. For $k\in\mathbb N$, we put

$$\begin{aligned} \, \zeta^{\mathrm{girth}}_{k, \mathrm{odd}}(\mathbb X) =\sup\bigl\{&\zeta:\exists\mspace{1mu}\text{ is a function }\delta =\delta(n)\text{ such that} \lim_{n\to\infty}\delta (n) =0 \\ &\qquad \text{and }\forall\mspace{1mu}n\,\exists\mspace{1mu}\text{a distance graph }G\text{ in }(\mathbb X^n,\ell_2), \\ &\qquad \text{which }has\, g_{\mathrm{odd}}(G)>2k+1,\,\chi(G)\ge(\zeta+\delta(n))^n\bigr\}. \end{aligned}$$

It was proved in [12] that

$$\zeta_{k,\mathrm{odd}}^{\mathrm{girth}}(\mathbb R) \ge 2\biggl(\frac{k}{2k+1}\biggr)^{k/(2k+1)} \biggl(\frac{k+1}{2k+1}\biggr)^{(k+1)/(2k+1)}.$$

This statement follows from the fact that, with the right choice of the parameters, there are no small cycles of odd length in $G_n$, and the chromatic number is large for large $n$:

$$\chi(G_n)\ge\biggl(2\biggl(\frac{k}{2k+1}\biggr)^{k/(2k+1)} \biggl(\frac{k+1}{2k+1}\biggr)^{(k+1)/(2k+1)}+o(1)\biggr)^n.$$

Note that such a graph $G_n$ is also a distance graph in $\mathbb Q^n$, whence

$$\zeta_{k,\mathrm{odd}}^{\mathrm{girth}}(\mathbb Q) \ge 2\biggl(\frac{k}{2k+1}\biggr)^{k/(2k+1)} \biggl(\frac{k+1}{2k+1}\biggr)^{(k+1)/(2k+1)}.$$

However, in the case of rational spaces, such a problem admits nonequivalent statements for different values of $d$. If $\gamma\in\mathbb Q$, then any distance graph in $(\mathbb Q^n,\ell_2)$ with $d=\gamma$ in (1.1) is isomorphic to a distance graph in $(\mathbb Q^n,\ell_2)$ with $d=1$. Any distance graph with $d=\gamma\sqrt{p_1\cdot\dotsb\cdot p_r}$ is isomorphic to a distance graph with $d=\sqrt{p_1\cdot\dotsb\cdot p_r}$, where $p_1,\dots,p_r$ are primes, $r\in\mathbb N$. For $k\in\mathbb N$ and $d=\sqrt{D}$, where $D\in\mathbb Q$ is a positive number, we put

$$\begin{aligned} \, \zeta^{\mathrm{girth}}_{d,k}(\mathbb Q) =\sup\bigl\{&\zeta:\exists\mspace{1mu}\text{ is a function }\delta =\delta(n)\text{ such that }\lim_{n\to\infty}\delta(n) =0\text{ and }\forall\mspace{1mu}n\,\exists\mspace{1mu}G \text{ in }(\mathbb Q^n,\ell_2) \\ &\qquad\text{is a distance graph with forbidden distance }d, \\ &\qquad\text{for which }g_{\mathrm{odd}}(G)>2k+1,\,\ chi(G)\ge(\zeta+\delta(n))^n\bigr\}. \end{aligned}$$

In view of what has been said above, it suffices to confine ourselves to the case $d=\sqrt{p_1\cdot\dotsb\cdot p_r}$, where $p_1,\dots,p_r$ are primes. For convenience, the symbol $b:=\sqrt{p_1\cdot\dotsb\cdot p_r}$ will be used everywhere in what follows.

The main result of our paper is the following theorem.

Theorem 3.

The following bound holds:

$$\zeta^{\mathrm{girth}}_{1,k}(\mathbb Q) \ge\biggl(2 \cdot\biggl(\frac{\widetilde k}{2\widetilde k+1}\biggr)^{\widetilde k/(2\widetilde k+1)} \biggl(\frac{\widetilde k+1} {2\widetilde k+1}\biggr)^{(\widetilde k+1)/(2\widetilde k+1)}\biggr)^{1/4},$$

where $\widetilde k:=2^{\lfloor\log_2 k\rfloor+1}$ .

As a corollary, we obtain the following result, which will be proved in Sec. 3.

Corollary 1.

The following bound holds:

$$\zeta^{\mathrm{girth}}_{b,k}(\mathbb Q) \ge\biggl(2\cdot\biggl(\frac{\widetilde k}{2\widetilde k+1}\biggr)^{\widetilde k/(2\widetilde k+1)} \biggl(\frac{\widetilde k+1} {2\widetilde k+1}\biggr)^{(\widetilde k+1)/(2\widetilde k+1)}\biggr)^{1/4b^2},$$

where $\widetilde k:=2^{\lfloor\log_2 k\rfloor+1}$ .

Remark 1.

Such a formulation of Theorem 2 and Corollary 1 is chosen for simplicity and the reader’s convenience. In fact, the present paper proves a stronger statement.

Let $\widetilde k=2^{\lfloor\log_2k\rfloor+1}$, and let $n$ be large enough. We set

$$f(\widetilde k, n, b) =\frac{2\widetilde k+1}{\widetilde k}\mspace{2mu} 2^{2\Bigl\lfloor\log_2 \sqrt{\frac{\widetilde k\lfloor n/b^2\rfloor}{2(2\widetilde k+1)}}\Bigr\rfloor+1}.$$

Then, in $(\mathbb Q^n,\ell_2)$, there exists a distance graph with forbidden distance $b$ and with $g_{\mathrm{odd}}>2k+1$ whose chromatic number is at least

$$\biggl(2\cdot\biggl(\frac{\widetilde k} {2\widetilde k+1}\biggr)^{\widetilde k/(2\widetilde k+1)} \biggl(\frac{\widetilde k+1}{2\widetilde k+1}\biggr)^{(\widetilde k+1)/(2\widetilde k+1)} +o(1)\biggr)^{f(\widetilde k,n,b)}.$$

Thus, for example, if $n$ is of the form $(2\widetilde k+1)2^{2m+1}b^2/\widetilde k$, $m\in\mathbb N$, then, in the exponent, we obtain $n/b^2$, rather than $n/4b^2$.

To conclude the introduction, we note that if we allow a distance graph not to contain all of its edges between pairs of vertices at a given distance, then we can get rid of even cycles. In this case, we can use the probabilistic method, which, for the real space, was applied in [13], as well as in [17] and [18]. The history of the problem of chromatic numbers of spaces and various results concerning distance graphs can be found in [19]–[33] (this list includes surveys, books, and papers), which indicates the importance of this topic.

2. Proof of Theorem 3

For each $k$, let us find the power of two $\widetilde k=2^{\lfloor\log_2k\rfloor+1}$, which is nearest to $k$ among those strictly greater than $k$. Note that if there are no cycles of length at most $2\widetilde k+1$ in the graph, then there are no cycles of length at most $2k+1$.

For each $n$, we find a natural number $\widetilde n$ of the form $((2\widetilde k+1)/\widetilde k\,)2^{2m+1}$, $m\in\mathbb N$ nearest to $n$ but not exceeding it.

Note that $n$, $\widetilde n$, and hence $m$ are sufficiently large and, therefore, $2^{2m+1}$ is divisible by $\widetilde k$. Let us write the exact expression for $\widetilde n$:

$$\widetilde n=\frac{2\widetilde k+1}{\widetilde k}\mspace{2mu} 2^{2\Bigl\lfloor\log_2\sqrt{\frac{n\widetilde k}{2(2\widetilde k+1)}}\Bigr\rfloor+1}. $$

(2.1)

Putting $q$ equal to $2^{2m+1}$, we also define it in a unique way for every $n$. Note that, to find a bound for the quantity $\zeta^{\mathrm{girth}}_{1, k}$, for $d$ in $\zeta^{\mathrm{girth}}_{d,k}$ we can take any sequence of natural numbers. Let us put $d=\sqrt{2q}$.

Let $\widetilde a_1=\lfloor\widetilde n/2\rfloor$. Then $\widetilde a_1<2q$, because

$$\widetilde a_1=\biggl\lfloor\frac{\widetilde n}{2}\biggr\rfloor <2q=\frac{2\widetilde k}{2\widetilde k+1}\mspace{2mu}\widetilde n. $$

(2.2)

It is clear that $G_{\widetilde n}=G_{\widetilde n}(\widetilde a_1, q)$ is a distance graph in $(\mathbb Q^n,\ell_2)$. Thus, it suffices to prove that the graph $G_ {\widetilde n}$ has sufficiently large chromatic number and does not have short odd cycles.

Let us introduce the following condition for some real $t$:

$$\frac{\widetilde k}{4(2\widetilde k+1)}\le t<\frac{1}{8}\mspace{2mu}. $$

(2.3)

Note that then, for $q$, the following relations hold:

$$q =\frac{\widetilde k\widetilde n}{2\widetilde k+1} >\frac{k\widetilde n}{2k+1}\mspace{2mu},$$

(2.4)

$$q \le 4t\widetilde n<\frac{\widetilde n}{2}\mspace{2mu}.$$

(2.5)

The last inequality $\widetilde n/2-q>0$ guarantees the correct choice of $\widetilde a_1$ and $q$ in the following sense: pairs of vertices of the distance graph $G_{\widetilde n}$ as $\widetilde n$-dimensional vectors with coordinates from the set $\{0,1\}$ must have nonnegative inner product. Indeed, the inner product of two vectors joined by an edge is equal to $\widetilde a_1-q=\lfloor\widetilde n/2\rfloor-q$ and is nonnegative.

Let us now find a bound for the chromatic number of the graph $G_{\widetilde n}$.

By the independence number of a graph $G=(V,E)$ we will mean the maximum cardinality of the subset of vertices without edges. This quantity is usually denoted by $\alpha (G)$. The chromatic number of the graph $G$ obviously satisfies the inequality $\chi(G)\ge|V|/\alpha(G)$. Thus,

$$\chi(G_{\widetilde n}) \ge\frac{|V_{\widetilde n}|}{\alpha(G_{\widetilde n})} =\frac{C_{\widetilde n}^{\widetilde a_1}}{\alpha(G_{\widetilde n})}\mspace{2mu}.$$

Lemma 2.

The following bound holds:

$$\alpha(G_{\widetilde n}) \le\sum_{i=0}^{\lfloor 4t\widetilde n\rfloor}C_{\widetilde n}^i.$$

Proof.

Let $W=\{\overline x_1,\dots,\overline x_s\}\subset V_{\widetilde n}$ be an arbitrary set of vertices without edges, i.e., such that, for any distinct $i$ and $j$, we have $\ell_2(\overline x_i,\overline x_j)\ne\sqrt{2q}$. Note that $(\ell_2(\overline x_i,\overline x_j))^2$ is an even number.

Let $\theta$ be the exponent of $2$ in the prime factorization of the number $(q-1)!$. To each vector $\overline x_i\in W$ we assign the polynomial

$$\mathscr P_{\overline x_i}(\overline y) =\frac{1}{2^\theta}\prod_{\nu=1}^{q-1} \biggl(\nu-\frac{1}{2}(\ell_2(\overline x_i,\overline y))^2\biggr) =\frac{1}{2^\theta}\prod_{\nu=1}^{q-1} \biggl(\nu-\frac{1}{2}\sum_{j=1}^{\widetilde n}(x_{ij}-y_j)^2\biggr),\qquad \overline y=(y_1,\dots,y_{\widetilde n}), $$

(2.6)

from the space $\mathbb Q[y_1,\dots,y_{\widetilde n}]$.

Suppose that, in $\mathbb Q[y_1,\dots,y_{\widetilde n}]$, there exists a nontrivial linear combination of polynomials identically equal to $0$:

$$c_1\mathscr P_{\overline x_1}+\dotsb+c_s\mathscr P_{\overline x_s}=0,\qquad c_1,\dots,c_s\in\mathbb Q. $$

(2.7)

Then, for any $\overline x_i\in W$,

$$c_1\mathscr P_{\overline x_1}(\overline x_i)+\dotsb +c_s\mathscr P_{\overline x_s}(\overline x_i)=0.$$

It is not difficult to verify that, for all $i$ and $j$, we have $\mathscr P_{\overline x_j}(\overline x_i)\in\mathbb Z$. We can assume that all the coefficients in (2.7) are integers and that, moreover, one of these coefficients is not divisible by $2$. Further, on the one hand,

$$\mathscr P_{\overline x_i}(\overline x_i) =\frac{1}{2^\theta}\prod_{\nu=1}^{q-1} \biggl(\nu-\frac{1}{2}(\ell_2(\overline x_i,\overline x_i))^2\biggr) =\frac{1}{2^\theta}\prod_{\nu=1}^{q-1}\nu =\frac{(q-1)!} {2^\theta}\not\equiv 0\,(\operatorname{mod}2).$$

On the other hand, for $j\ne i$, we have

$$\begin{aligned} \, (1)&\quad \dfrac{1}{2}(\ell_2(\overline x_j,\overline x_i))^2\le\widetilde a_1; \\ (2)&\quad \dfrac{1}{2}(\ell_2(\overline x_j,\overline x_i))^2\ne q; \\ (3)&\quad \dfrac{1}{2}(\ell_2(\overline x_j,\overline x_i))^2>0, \end{aligned}$$

where, in view of the inequality $\widetilde a_1-2q<0$ (see (2.2)), $(\ell_2(\overline x_j,\overline x_i))^2/2\not\equiv 0\,(\operatorname{mod}q)$. And this, in turn, yields $\mathscr P_{\overline x_j}(\overline x_i)\equiv 0\,(\operatorname{mod}2)$. Indeed, the product of $(q-1)$ consecutive residues modulo $q$ contains more than $d$ factors $2$ in the cyclic shift by $(\ell_2(\overline x_j,\overline x_i))^2/2\not\equiv 0\,(\operatorname{mod}q)$. It turns out that $c_i\equiv 0\,(\operatorname{mod}2)$ for any $i$. We have obtained a contradiction to the oddness of one of the coefficients, and hence to the nontriviality of the linear combination (2.7); i.e., the polynomials $\mathscr P_{\overline x_1},\dots,\mathscr P_{\overline x_s}$ are linearly independent over $\mathbb Q$.

Let us transform each of the polynomials as follows. Multiplying all the brackets, we write the polynomial as a linear combination of monomials and, in each monomial, we replace the factors of the form $y_\nu^{\alpha_\nu}$, $\alpha_\nu\ge 1$, by the cofactors $y_\nu$, because $y_\nu\in\{0,1\}$. The new polynomials as functions of vectors from $W$ are identically equal to the original polynomials. Hence, the new polynomials are also linearly independent over $\mathbb Q$. We multiply $q-1$ brackets in $\widetilde n$ variables, and each variable is contained in them to the power $0$ or $1$. All such polynomials are known to be generated by the basis of $\sum_{i=0}^{q-1}C_{\widetilde n}^i$ elements. Thus, using (2.5), we obtain $|W|=s\le\sum_{i=0}^{q-1}C_{\widetilde n}^i \le\sum_{i=0}^{\lfloor4t\widetilde n\rfloor}C_{\widetilde n}^i$. The lemma is proved.

From Lemma 2, we obtain

$$\chi(G_{\widetilde n}(\widetilde a_1,q)) \ge\frac{C_{\widetilde n}^{\widetilde a_1}} {\sum_{i=0}^{\lfloor 4t\widetilde n\rfloor}C_{\widetilde n}^i}\mspace{2mu}. $$

(2.8)

Denote

$$A=C_{\widetilde n}^{\widetilde a_1},\qquad B=\sum_{i=0}^{\lfloor 4t\widetilde n\rfloor}C_{\widetilde n}^i. $$

(2.9)

Using Stirling’s formula, we can write

$$A=(2+o(1))^{\widetilde n},\qquad B=\biggl(\frac{1}{(4t)^{4t}(1-4t)^{1-4t}}+o(1)\biggr)^{\widetilde n}. $$

(2.10)

Hence, in view of (2.8)–(2.10), $\chi(G_{\widetilde n}(\widetilde a_1,q)) \ge(2\cdot(4t)^{4t}(1-4t)^{1-4t}+o(1))^{\widetilde n}$.

It follows from (2.1) that $\widetilde n\ge n/4$. It follows from (2.3) that the base of the exponential is greater than $1$. Thus, $\chi(G_{\widetilde n}(\widetilde a_1,q)) \ge(2\cdot(4t)^{4t}(1-4t)^{1-4t}+o(1))^{n/4}$.

In the graph $G_{\widetilde n}$, there are no odd cycles of length at most $2k+1$ due to inequality (2.4) and Lemma 1.

Now let us use condition (2.3). We obtain

$$\begin{aligned} \, \widetilde{\zeta}_{k,\mathrm{odd}}^{\mathrm{girth}}(\mathbb Q) &\ge\max_{\widetilde k/(4(2\widetilde k+1))\le t<1/8} (2\cdot(4t)^{4t}(1-4t)^{1-4t})^{1/4} \\& =\biggl(2 \cdot\biggl(\frac{\widetilde k}{2\widetilde k+1}\biggr)^{\widetilde k/(2\widetilde k+1)} \biggl(\frac{\widetilde k+1} {2\widetilde k+1}\biggr)^{(\widetilde k+1)/(2\widetilde k+1)}\biggr)^{1/4}. \end{aligned}$$

Theorem 3 is proved.

3. Proof of Corollary 1

For each $n$, we put $n_0=\lfloor n/b^2\rfloor$. For each $k$, let us find $\widetilde k=2^{\lfloor\log_2k\rfloor+1}$, which is the power of $2$ nearest to $k$ among those strictly greater than $k$. As before, from the fact that there are no cycles of length at most $2\widetilde k+1$ in the graph, it follows that there are no cycles of length at most $2k+1$. In turn, for each $n_0$, let us find the natural number

$$\widetilde n_0=\frac{2\widetilde k+1}{\widetilde k}\mspace{2mu} 2^{2\Bigl\lfloor\log_2\sqrt{\frac{n_0\widetilde k}{2(2\widetilde k+1)}}\Bigr\rfloor+1}$$

nearest to it and not exceeding it. Define

$$q=2^{2\Bigl\lfloor\log_2\sqrt{\frac{n_0\widetilde k}{2(2\widetilde k+1)}}\Bigr\rfloor+1} =\frac{\widetilde k}{2\widetilde k+1}\mspace{2mu}\widetilde n_0.$$

Let $\widetilde a^{\mspace{2mu}0}_1=\lfloor\widetilde n_0/2\rfloor$, and let $t$ be a real number satisfying condition (2.3). Note that relations (2.2), (2.4), and (2.5) still hold for $\widetilde a^{\mspace{2mu}0}_1$, $q$, $\widetilde n_0$, and $t$ instead of $\widetilde a_1$, $q$, $\widetilde n$, and $t$, respectively. Let us put

$$\widetilde a_1=\widetilde a^{\mspace{2mu}0}_1\cdot b^2 =\biggl\lfloor \frac{\widetilde n_0}2\biggr\rfloor\cdot b^2,\qquad \widetilde n=\widetilde n_0\cdot b^2.$$

It is seen that relations (2.2), (2.3), (2.4), and (2.5) hold for $\widetilde a_1$, $q\cdot b^2$, $\widetilde n$, and $t$ instead of $\widetilde a_1$, $q$, $\widetilde n$, and $t$, respectively. Consider the graph $G_{\widetilde n}(\widetilde a_1, q\cdot b^2)$ and note that it is embedded in $\mathbb Q^n$. In view of inequality (2.4) with the new parameters, the requirements of Lemma 1 will hold for this graph, and there are no odd cycles of length at most $2k+1$.

Consider the induced subgraph of the graph $G_{\widetilde n}(\widetilde a_1, q\cdot b^2)$ on all those vertices whose coordinates $x_1,\dots,x_{\widetilde n}$ are the concatenation of the $b^2$ identical sets of coordinates of $\widetilde a_1$ 1’s and $\widetilde n_0-\widetilde a_1$ 0’s. Note that this induced subgraph is isomorphic to $G_{\widetilde n_0}(\widetilde a^{\mspace{2mu}0}_1,q)$. Thus, the following lower bound on the chromatic number $\chi(G_{\widetilde n}(\widetilde a_1,q\cdot b^2))$ holds: $\chi(G_{\widetilde n}(\widetilde a_1,q\cdot b^2)) \ge\chi(G_{\widetilde n_0}(\widetilde a^{\mspace{2mu}0}_1,q))$.

In turn, by Theorem 3, we have

$$\chi(G_{\widetilde n_0}(\widetilde a^{\mspace{2mu}0}_1,q)) \ge (2\cdot(4t)^{4t}(1-4t)^{1-4t}+o(1))^{n_0/4} =(2\cdot(4t)^{4t}(1-4t)^{1-4t}+o(1))^{\lfloor n/b^2\rfloor/4}.$$

Thus,

$$\zeta^{\mathrm{girth}}_{b,k}(\mathbb Q) \ge\biggl(2 \cdot\biggl(\frac{\widetilde k}{2\widetilde k+1}\biggr)^{\widetilde k/(2\widetilde k+1)} \biggl(\frac{\widetilde k+1}{2\widetilde k+1}\biggr)^{(\widetilde k+1)/(2\widetilde k+1)}\biggr)^{1/4b^2}.$$

Corollary 1 is proved.

Funding

The proof of Theorem 3 was supported by the Russian Foundation for Basic Research (science grant no. 18-01-00355) and by the program “Leading Scientific Schools” (grant no. NSh-2540.2020.1). The proof of Corollary 1 was supported by the Grant of the Government of the Russian Federation for the state support of scientific research supervised by leading scientists (agreement no. 075-15-2019-1926).