Abstract
An important generalization of Borsuk’s classical problem of partitioning sets into parts of smaller diameter is studied. New upper and lower bounds for the Borsuk numbers are found.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
This paper deals with an important version of Borsuk’s classical problem of partitioning sets into parts of smaller diameter (see [1]).
Let \(b \in (0,\;1]\) and \(n \in \mathbb{N}\). Define \(\chi (n,b)\) as the minimum number of subsets of diameter strictly smaller than b into which an arbitrary set of diameter 1 can be partitioned in \({{\mathbb{R}}^{n}}\). For b = 1, we obtain exactly the classical Borsuk number, about which we know that \(\chi (1,\;1) = 2\), \(\chi (2,\;1) = 3\), \(\chi (3,\;1) = 4\), and
(see [1, 2]). For small n and various b, a variety of results and references can be found in [1, 3].
We are interested in the case when \(n \to \infty \) and \(b = b(n)\). In this case, all known upper bounds are exponential in n. For example, Rogers’s work concerning packings of spherical caps on the sphere (see [4]) implies the inequality
Here, \(\tfrac{{\sqrt 2 }}{b}\) can be reduced by applying the technique of [5].
The lower bounds are much subtler. Roughly speaking, below we will show that, if \(b(n) \leqslant c < 1\) for all \(n\), then these bounds are also exponential. If \(b(n) \to 1\) as \(n \to \infty \), then the bounds become subexponential, gradually decreasing (as the rate of convergence of b to unity increases) to the form given by the left-hand side of bound (1), i.e., to an asymptotic constant raised to power \(\sqrt n \). Rigorous formulations of the corresponding new results are given in the rest of this paper.
Theorem 1. Let \(k = k(n)\) be an arbitrary function with values in the set \(\left\{ {1, \ldots ,\tfrac{n}{2}} \right\}\). For every n, consider the maximum integer \(a = a(n)\) for which \(\sqrt {1 - \tfrac{{a(n)}}{{k(n)}}} \geqslant b(n)\). Let \(m(n,r,s)\) be the maximum cardinality of the collection of r-element subsets of the set \({{\mathcal{R}}_{n}} = {\text{\{ }}1,\; \ldots ,\;n{\text{\} }}\) such that each two subsets share at least s elements. Then
The value of \(m(n,r,s)\) has been found for all \(n\), r, and s. For completeness’ sake, we state the corresponding result (see [6]).
Theorem 2 (P. Frankl, R.M. Wilson, R. Ahlswede, L. Khachatrian). Suppose that \(2r - n < s\) and \(1 \leqslant s \leqslant r \leqslant n\). For \(0 \leqslant i \leqslant \tfrac{{n - s}}{2}\) and \(i \leqslant r - s\), define the collection
i.e., \({{\mathcal{M}}_{i}}(n,r,s)\) is the collection of all possible r-element subsets of the set \({{\mathcal{R}}_{n}}\) with at least s + i elements taken from \({\text{\{ }}1,\; \ldots ,\;s + 2i{\text{\} }} \subseteq {{\mathcal{R}}_{n}}\). If for some \(l \in \mathbb{N} \cup {\text{\{ }}0{\text{\} }}\)
then \(m(n,r,s) = \left| {{{\mathcal{M}}_{l}}(n,r,s)} \right|\) (we assume that \(\tfrac{{s - 1}}{l} = \infty \) whenever l = 0).
Theorem 1 can be refined as follows.
Theorem 3. Suppose that \({{k}_{{ - 1}}} = {{k}_{{ - 1}}}(n)\), \({{k}_{0}} = {{k}_{0}}(n)\), and \({{k}_{1}} = {{k}_{1}}(n)\) are arbitrary functions with values in \({{\mathcal{R}}_{n}}\) that satisfy the relations
For each \(n\), consider the maximum integer \(a = a(n)\) for which
Let \(f(n,{{k}_{{ - 1}}},{{k}_{0}},{{k}_{1}},s)\) be the maximum cardinality of a set of \(( - {\kern 1pt} 1,\;0,\;1)\)-vectors in \({{\mathbb{R}}^{n}}\) such that each vector has exactly ki coordinates equal to \(i\), \(i \in {\text{\{ }}{\kern 1pt} - {\kern 1pt} 1,0,1{\text{\} }}\), and the scalar product of any two vectors is at least s. Then
The idea of this refinement is that, for \({{k}_{{ - 1}}}(n)\) vanishing identically, we obtain exactly Theorem 1: when the vectors have only zero and unit coordinates, their scalar product is equal to the cardinality of the intersection of the sets of their unit coordinates. Of course, it would be possible to produce even bulkier generalizations by gradually adding new coordinate values. However, the matter is that even \(f(n,{{k}_{{ - 1}}},{{k}_{0}},{{k}_{1}},s)\) can hardly be estimated in the general case. Nevertheless, some bounds for it are available, and they can be used to refine Theorem 1 in a number of situations. For other similar quantities, the results are scarce, and it is no use considering them in the current context.
Concerning bounds for \(f(n,{{k}_{{ - 1}}},{{k}_{0}},{{k}_{1}},s)\), a conjecture about its exact value can be found in [7]. Additionally, there are more recent results of Frankl and Kupavskii (see [8]) and related results of other authors (see [9–15]). However, the linear-algebraic method remains one of the most effective tools in this case (see [1, 2, 12–15]). Specifically, the following theorem can be proved with the help of this method.
Theorem 4. Given all the parameters of Theorem 3, suppose that \(q = q(n)\) is the minimum number equal to a prime power such that \({{k}_{{ - 1}}}(n) + {{k}_{1}}(n) - q(n) \leqslant a(n)\). Then
where
A fairly standard asymptotic analysis can be applied to the bounds from Theorems 1 and 3. Accurate optimization is difficult, including because the bound in Theorem 4 depends on the prime number distribution. Nevertheless, it is relatively easy to see that, if \(b(n) \leqslant c < 1\), where c is a constant, then both theorems give bounds of the form \({{(C + o(1))}^{n}}\), where C > 1. On the contrary, both bounds become subexponential when \(b(n) \to 1\) as \(n \to \infty \). If \(b(n) = 1\), then both bounds, in fact, degenerate, becoming equal in order to n. However, inequality (1) suggests that Theorems 1 and 3 do not cover the situation entirely. Below, we present two new theorems that work in the case when b(n) tends rather rapidly to unity.
Theorem 5. Suppose that \(d = d(n)\) and \(a = a(n)\) are such that \(d = 4q\), where \(q = q(n)\) is a prime power and
Then
For example, if \(b(n) = 1 - \tfrac{1}{{\sqrt n }}\), then \(d(n) = \Theta (\sqrt n )\), \(a(n) = \Theta (\sqrt[4]{n})\), and the bound in Theorem 5 resembles the lower bound in (1). The closer the b(n) to the identical unity, the closer the a(n) to zero. For a(n) = 0, the bound in Theorem 5 coarsened in the style of inequality (1) taking into account the Stirling formula and the prime number density turns into the inequality
The constant under the subexponential sign is smaller than the constant in the lower bound in (1). An improvement leading to the same constant is given in the last theorem.
Theorem 6. Suppose that \(d = d(n)\), \(q = q(n)\), and \(a = a(n)\) are such that q is a prime power, \(q(n) \leqslant \tfrac{{d(n)}}{2}\), and
Then
where
REFERENCES
A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters,” in Discrete Geometry and Algebraic Combinatorics, AMS Contemporary Mathematics, Vol. 625 (Am. Math. Soc., Providence, 2014), pp. 93–109.
L. I. Bogolyubsky and A. M. Raigorodskii, Math. Notes 105 (1–2), 180–203 (2019).
V. P. Filimonov, Sb. Math. 205 (8), 1160–1200 (2014).
C. A. Rogers, Mathematika 10, 157–164 (1963).
J. Bourgain and J. Lindenstrauss, “On covering a set in by balls of the same diameter,” Geometric Aspects of Functional Analysis, Ed. by J. Lindenstrauss and V. Milman, Lecture Notes in Mathematics (Springer-Verlag, Berlin, 1991), Vol. 1469, pp. 138–144.
R. Ahlswede and L. H. Khachatrian, Eur. J. Comb. 18, 125–136 (1997).
A. M. Raigorodskii and A. A. Kharlamova, “On collections of (–1, 0, 1)-vectors with constraints on the values of pairwise inner products,” Studies in Vector and Tensor Analysis (Mosk. Gos. Univ., Moscow, 2013), Vol. 29, pp. 130–146 [in Russian].
P. Frankl and A. Kupavskii, J. Comb. Theory Ser. A 155, 157–179 (2018).
P. Frankl and A. Kupavskii, Combinatorica 39 (6), 1255–1266 (2019).
A. Kupavskii, J. Comb. Theory Ser. A 168, 272–287 (2019).
A. B. Kupavskii and A. A. Sagdeev, Russ. Math. Surv. 75 (5), 965–967 (2020).
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii, Math. Notes 107 (3), 392–403 (2020).
A. M. Raigorodskii and A. A. Sagdeev, Acta Math. Univ. Comenianae 88 (3), 1029–1033 (2019).
A. M. Raigorodskii and E. D. Shishunov, Dokl. Math. 99 (2), 165–166 (2019).
F. A. Pushnyakov and A. M. Raigorodskii, Math. Notes 107 (2), 322–332 (2020).
Funding
This work was supported by the Russian Foundation for Basic Research (project no. 18-01-00355) and by President’s grant NSh-2540.2020.1.
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated by I. Ruzanova
Rights and permissions
About this article
Cite this article
Raigorodskii, A.M. On Dividing Sets into Parts of Smaller Diameter. Dokl. Math. 102, 510–512 (2020). https://doi.org/10.1134/S1064562420060174
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1064562420060174