Coverings of planar and three-dimensional sets with subsets of smaller diameter A. D. Tolmachev D. S. Protasov V. A. Voronov

2025-05-06 0 0 746.58KB 19 页 10玖币

侵权投诉

Coverings of planar and three-dimensional sets

with subsets of smaller diameter ∗

A. D. Tolmachev†

, D. S. Protasov‡

, V. A. Voronov§

v-vor@yandex.ru

October 25, 2022

Abstract

Quantitative estimates related to the classical Borsuk problem of split-

ting set in Euclidean space into subsets of smaller diameter are considered.

For a given kthere is a minimal diameter of subsets at which there exists

a covering with ksubsets of any planar set of unit diameter. In order to

ﬁnd an upper estimate of the minimal diameter we propose an algorithm

for ﬁnding sub-optimal partitions. In the cases 10 6k617 some upper

and lower estimates of the minimal diameter are improved. Another result

is that any set M⊂R3of a unit diameter can be partitioned into four

subsets of a diameter not greater than 0.966.

1. Introduction

This paper presents some results related to the classical Borsuk problem on

partitioning of sets in Rninto parts of smaller diameter [1, 2, 3, 4], and also

to the Nelson–Erd˝os–Hadwiger problem on the chromatic number of Euclidean

space [5, 6, 7, 8, 9, 10, 11]. Most of the article is devoted to the planar case.

Let Fbe a bounded set in the plane, and k∈N. We denote by dk(F) the

greatest lower bound of the set of positive real numbers xwith the property

that Fcan be covered by ksets F1, F2, . . . , Fkwhose diameters are at most x,

that is,

dk(F) = inf{x∈R+:∃F1, . . . , Fk:F⊆F1∪. . . ∪Fk,∀idiam(Fi)6x}.

In other words, we want to choose optimal coverings consisting of the smallest

possible diameter sets among all possible coverings of the set F. In addition,

∗The work was supported by the program “Leading Scientiﬁc Schools” under grant NSh-

775.2022.1.1.

†Graduate student, Moscow Institute of Physics and Technology

‡Graduate student, Moscow Institute of Physics and Technology

§PhD, Researcher, Caucasus Mathematical Center of Adyghe State University, Maikop;

Moscow Institute of Physics and Technology

arXiv:2210.12394v1 [math.MG] 22 Oct 2022

the value dk(F) does not change, if, without loss of generality, we require the

sets to be convex and closed. Indeed, it is easy to see that the diameter of the

closure of the convex hull for any set Fifrom the covering coincides with the

diameter of Fi.

For every positive number kwe consider the values dk= sup dk(F), where

the suprema are taken over all sets Fof unit diameter on the plane. It follows

from the remark above that the sequence dkis nonincreasing.

Motivated by the classical Borsuk problem [1, 2, 3, 4], many specialists have

evaluated elements of this sequence. Over the years, H. Lenz (see [12]), M.

Dembinski and M. Lassak (see [13]), V. Filimonov (see [14]), D. Belov and

N. Aleksandrov (see [15]), V. Koval (see [16]) estimated values dkfor various

values of k. A theoretically feasible, but extremely time-consuming approach

to this problem and its generalizations was proposed in [17]. Moreover, Yanlu

Lian and Senlin Wu explored such values for some Banach spaces (see [18]). In

our previous work (see [19]) we signiﬁcantly improved some of previous upper

bounds of the quantities dk. In this paper we prove new lower and upper bounds

for the elements in the sequence dk. Moreover, we proposed new approach to

improving upper bounds of the values dk.

We present our new results in the following sections, but here we suggest

additional important deﬁnitions for these theorems and their proofs. In this

paper, using techniques to construct universal covering sets and systems, we

prove some upper bounds for the elements of the sequence dk.

Note that both inﬁnitesimal local improvements to these partitions are pos-

sible, as well as improvements based on the extension of the covering system.

Of course, this approach does not allow us to obtain exact values of dk.

Deﬁnition 1. A set Ω⊂R2is called universal covering set if every planar set

Fof unit diameter can be completely covered by Ω(that is, there exists a planar

set Ω0congruent to Ωsuch that F⊂Ω0).

In 1920, in [20] J. Pal proved that a regular hexagon with edge length 1

√3is

a universal covering set. We denote this regular hexagon by Ω. Next, we deﬁne

a universal covering system.

Deﬁnition 2. System of sets S={Ωα}α∈Iis called a universal covering system

if every planar set Fof unit diameter can be completely covered by one of sets

Ωα. Here Iis a (possibly inﬁnite) set of indices.

2. Main results

In this part of the paper we show the table of improved results for the ﬁrst

17 elements of the sequence dk. In Table 1, the column titled as “comment”

indicates by how many percent the gap between the upper and lower bounds

has decreased as a result of the improvements proposed in this paper. The

column titled as “UCS” presents the universal covering system used to prove

the indicated upper bound on dkfor the corresponding value of k. Let us denote

by dold

k,dnew

k,dold

kand dnew

k, respectively, the previously known and the new

value of the lower bound, and similarly for the upper bound.

All constants in this table are speciﬁed with four decimal places.

Table 1: Old and new estimates

k dnew

kdold

kdnew

kComment UCS

1 - 1.0000 1.0000 - tight -

2 - 1.0000 1.0000 - tight -

3 - 0.8660 0.8660 - tight -

4 - 0.7071 0.7071 - tight -

5 - 0.5877 0.5953 - - -

6 - 0.5051 0.5343 - - -

7 - 0.5000 0.5000 - tight -

8 - 0.4338 0.4456 - - -

9 - 0.3826 0.4047 - - -

10 0.3665 0.3420 0.4012 0.3896 61% S10

11 0.3535 0.3333 0.3942 0.3732 68% S10

12 0.3420 0.3333 0.3660 0.3532 66% S10

13 - 0.3333 0.3550 0.3419 60% S10

14 - 0.3090 0.3324 0.3263 26% S10

15 - 0.2928 0.3226 0.3130 32% S10

16 - 0.2817 0.3191 0.3035 42% S10

17 - 0.2701 0.3010 0.2967 14% S10

3. Upper bounds

3.1 Improvements to the upper estimates and the con-

struction of the UCS

To prove that dk6ρ, where ρis some ﬁxed number, we consider some universal

covering system Sand divide each of the covering sets into kparts. The diameter

of each part does not exceed ρ.

From the introduction, we know that any set of diameter 1 can be covered

by a Ω, i.e regular hexagon with a unit distance between the opposite sides.

Lemma 1. Let σbe a covering system. Suppose that there exists a set M∈σ

and points A, B ∈Msuch that the length of segment AB is greater than 1.

Denote by δ=|AB|−1

2. Perpendicular lines drawn to the segment AB at a

distance of δ

2from its ends divide the set Minto three sets m1,m2,m3(in

Figure 1, the perpendiculars are drawn at points Cand D). We will refer the

Figure 1: The set Mand its division into the sets m1,m2,m3

perpendiculars themselves only to the set m2, so sets m1and m3will not contain

them. Denote by M1=m1∪m2,M2=m2∪m3.

Then σ\{M}∪{M1, M2}will also be a covering system.

Proof: We want to show that if a set Fcan be covered by the set M, then F

can be covered by the set M1or the set M2. Let’s assume that when a certain set

Nis covered by the set M, there is at least one point of the set Nin m1. Then

m3cannot have points from N, because the distance between any point from

m1and a point from m3is strictly greater than 1. So we get a contradiction

with the diameter of the set Nis not more than 1. This contradiction proves

that the set M1will cover the set N. If m1does not contain points from N,

then M2will cover N. This statement proves the Lemma 1.

Now, using the lemma, we pass from one set Ω to a system of two covering

sets. Each of the main diagonals of Ω has length 2

√3, which is greater than one,

so according to the lemma from the hexagon, you can cut oﬀ the corresponding

parts (in this case, triangles) on each of the three diagonals of the hexagon.

Figure 2: Ω1,Ω2(the dotted line marks the parts cut oﬀ from Ω)

After eliminating the congruent ones, we get a universal covering system

containing two sets. In the ﬁrst case, the vertices from which the triangles are

cut oﬀ go through one (let’s call it Ω1). In the second case, the vertices from

which the triangles are cut oﬀ go in a row (let’s call it Ω2).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Coveringsofplanarandthree-dimensionalsetswithsubsetsofsmallerdiameter*A.D.Tolmachev,D.S.Protasov,V.A.Voronov§v-vor@yandex.ruOctober25,2022AbstractQuantitativeestimatesrelatedtotheclassicalBorsukproblemofsplit-tingsetinEuclideanspaceintosubsetsofsmallerdiameterareconsidered.Foragivenkthereisaminima...

展开>> 收起<<

Coverings of planar and three-dimensional sets with subsets of smaller diameter A. D. Tolmachev D. S. Protasov V. A. Voronov.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Coverings of planar and three-dimensional sets with subsets of smaller diameter A. D. Tolmachev D. S. Protasov V. A. Voronov

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: