Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников

Автор: Самиров Д.В., Райгородский А.М.

Журнал: Труды Московского физико-технического института @trudy-mipt

Статья в выпуске: 2 (26) т.7, 2015 года.

Бесплатный доступ

В настоящей работе предложена модификация линейно-алгебраического метода в комбинаторике, позволяющая получать новые экспоненциальные нижние оценки в задаче о минимальном числе цветов, в которые можно так покрасить пространство, чтобы точки одного цвета не могли образовать равнобедренный треугольник с длинами сторон из некоторого множества.

Хроматические числа, евклидова теория рамсея, дистанционный граф

Короткий адрес: https://sciup.org/142186070

IDR: 142186070

Текст научной статьи Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников

Задача о раскраске метрического пространства — это одна из самых важных и в то же время многогранных задач современной комбинаторной геометрии. С подробностями ее истории можно ознакомиться по обзорам и книгам [1] – [6]. Ниже мы расскажем лишь о тех моментах, которые непосредственно важны для нашего исследования.

Итак, впервые задача о раскраске пространства была предложена Нелсоном и Хадвигером в середине ХХ века (см. [6], [7]). Тогда речь зашла об отыскании хроматического числа пространства R ⁿ , обозначаемого x( R ” ) и равного минимальному количеству цветов, в которые можно так покрасить все точки евклидова пространства, чтобы между точками одного цвета не было расстояния 1:

X( R ” ) = min { y : 3 V 1 ,...,V _X R ⁿ = V 1 U ... U V _x , V г V x , y G V | x - y | = 1 } .

Из всего многообразия результатов, касающихся величины x( R ⁿ ), выделим лишь несколько наиболее значимых для нашей работы. Во-первых, наилучшая известная верхняя оценка хроматического числа была получена Ларманом и Роджерсом в 1972 году (см. [8]):

x( R ” ) 6 (3 + ₀ (1)) ^и .

Во-вторых, известны две экспоненциальные нижние оценки:

x( R ⁿ ) >

(1G......)

= (1.207... + o(1)F

(см. работу [9] Франкла и Уилсона, опубликованную в 1981 году) и x(Rn) > (1.239 ... + o(1))n

(см. работу [10] Райгородского, опубликованную в 2000 году). Подчеркнем, что функции o(1) в неравенствах, конечно, разные. Более того, при малых п оценки из первого неравенства сильнее оценок из второго неравенства.

Существует множество естественных обобщений величины x( R ” ). Так, вещественное евклидово пространство заменяют произвольным метрическим пространством (X, р), при этом расстояние а, которому запрещено достигаться между точками одного цвета, также выбирают произвольно (в евклидовом случае величина а не влияла на значение хроматического числа):

x((X, р), а) = min { x : 3 V i ,..., V R ⁿ = V i U ... U V X , V г V x , y G Vp( x , y ) = а } .

Здесь, в частности, много внимания уделялось случаям рационального евклидова пространства Q ⁿ (см. [2], [11] - [14]), пространствам R ⁿ и Q ⁿ с метриками 1 _Р (см. [2], [15] - [17]), сферам с евклидовой метрикой (см. [2], [18] – [21]).

Далее, вместо одного запрета берут множества запретов Л С R + (как конечные, так и бесконечные):

x((X, р), Л ) = min { x : 3 V i ,..., V x R ⁿ = V i U ... U V x , V г V x , y G V p( x , y ) G Л} .

Здесь среди прочего можно отметить работы [2], [22] – [27]. Также стоит отметить, что, как правило, в случае, когда |Л| < то , речь идет о величинах

^x((X,p⁾;^⁾ = “ax, x^((X,P⁾, ^Л ⁾. Л : |Л| =&

В то же время можно запрещать не несколько независимых расстояний, но более сложные точечные конфигурации. В этом случае пока рассматривают только евклидовы пространства. А именно, пусть дано множество S С R ^d , | S | > 2. Пусть п > d. Положим

X s ( R ⁿ ) = min { x : 3 V i ,..., V ^ R ⁿ = V i U .. . U V ^ , V г V p — движения пространства p(S) С V i }.

Множество S называется рамсеевским, если x s ( R ⁿ ) ^ то при п ^ то . Легко показать, что если множество S рамсеевское, то оно конечное и лежит на некоторой сфере (см. [28]). Обратное утверждение является открытой гипотезой, которая доказана в ряде случаев — например, для произвольных симплексов (подразумеваются множества вершин симплексов) и декартовых произведений любых рамсеевских множеств (см. [28], [29] – [34]). Для симплексов соответствующие хроматические числа растут экспоненциально, как и для двухточечных множеств, с которых начиналась вся проблематика. Правда, константы в основаниях экспонент очень близки к 1, и даже для треугольников, которые нам особенно интересны в контексте настоящей работы, наилучшая известная оценка имеет вид (см. [32] – [34])

X a ( R " ) > (1.052 ... + о(1)) ^п .

Вместе с тем, конечно, x s ( R ” ) 6 x( R ” ) 6 (3 + o(1)) ⁿ .

Запрещенных одноцветных конфигураций, как и запрещенных расстояний, можно брать целое множество. В недавних работах авторов этой статьи (см. [35] – [37]) была изучена величина x«,b(Rn) (при 0 < а < 1 < 5 < V2), равная минимальному количеству цветов, в которые можно так покрасить все точки евклидова пространства, чтобы никакие три точки одного цвета не образовывали равнобедренный треугольник с длинами боковых сторон 1 и длиной основания в пределах от а до Ь. Разумеется, если в данном определении единицу заменить каким-нибудь числом с, то получится некоторое новое хроматическое число Xa,b,c(R”). В настоящей работе мы рассмотрим, в частности, вопрос об отыскании величины

X a,b ( R ” ) = max X a,b,c ⁽ ^R ” ).

Наконец, пусть X a,b,c i ,...,c i ( R ”) — это минимальное количество цветов, в которые можно так покрасить все точки евклидова пространства, чтобы никакие три точки одного цвета не образовывали равнобедренный треугольник с длинами боковых сторон с и длиной основания в пределах от а до Ь, г = 1,..., Z. Положим

X a,b;Z ⁽ ^R ” ) = ^max X a,b,c i ,...,c _t ⁽ ^R ” ). c i ,...,c i

Понятно, что для любых а, Ь, I, п выполнено

X a,b;Z ( R ^ ) 6 X( R ” ; I).

Последняя величина, как нетрудно увидеть, не превосходит (3 + о(1)) ” . В следующем разделе мы сформулируем новую теорему о нижней оценке хроматического числа X _a b-z ( R ” ) и выведем из нее численные следствия при I 6 5.

2. Формулировка результата

Имеет место следующий результат.

Теорема 1. Пусть 0 < а < Ь < V2 , I € N . Возьмем любые числа к, а, удовлетворяющие ограничениям 0 < к < 2 , 0 < а < к. Положим

3 = к —

а2/ .

Ь 2 ^(к ^— ^а), 5 =

(Z + 1)(к — а) 3 — а

к — а а(к — а)

д , 1 + 2(а — к)

При ж € [3 — к + а + г, а + г] положим

С = (а + 2 г ) “ ^+2г • (а + г) ^-а-г • г ^- • (1 — а — 2г) ¹ ^-а- ² ^г • (к — а — гУ ^+а-к • (1 — к — г) ^г ⁺ ^к- ¹ , С- 2 (ж) = (а + г) “+ ^г -x^X • (а + г — ж) ²⁽ ^х-а-г ⁾ • г ^г • (ж — аУ ^^З

С ₃ (ж) = (к — а — г )^к-“^^г • (3 — ж) ^ж-/3 • (к + ж — а — 3 — г) ²(“+^+ ^г-к-х ) х х (1 — к — г) ¹ ^-к-г • (1 + а + 3 — ж — 2к) ^ж ⁺² ^к- ¹ ^-а-/3 , А = тахС ₂ (ж) • С з (ж).

Тогда

X ab^‘ ) > ( ^С 1 '^Ғ ^, '⁽_А¹ — ^Т ⁾ ¹ -‘ + 0(1) ) ” .

Для I < 5 были получены оптимальные оценки с помощью компьютера, но в данной работе мы приведем только три таблицы. Таблица с номером I построена именно для данного I из формулировки теоремы. По вертикали в таблице откладывается значение а с небольшим шагом, по горизонтали — Ь. В соответствующей клетке сверху вниз расположены 4 числа:

1) оптимальная константа в основании экспоненты, которая согласно утверждению теоремы служит нижней оценкой для изучаемого нами хроматического числа;
2) оптимальное значение параметра к;
3) оптимальное значение параметра а;
4) оптимальное значение параметра /3.
3. Доказательство теоремы 1

Можно заметить также, что при I = 1 константа 1) приближается к величине 1.207 из упомянутой в начале введения теоремы Франкла–Уилсона. К сожалению, метод, позволивший в асимптотике заменить 1.207 на 1.239, нам в текущей задаче примениить не удалось.

	0,2	0,3	0,4	0,5	0,6	0,7	0,8	0,9	1,0	1,1	1,2	1,3	1,4
0,1	1,001	1,033	1,072	1,102	1,124	1,139	1,151	1,160	1,167	1,172	1,177	1,180	1,183
	0,010	0,160	0,240	0,420	0,370	0,290	0,310	0,400	0,310	0,480	0,470	0,350	0,280
	0,003	0,080	0,096	0,236	0,160	0,063	0,070	0,151	0,054	0,219	0,204	0,081	0,008
	0,008	0,151	0,231	0,412	0,364	0,285	0,306	0,396	0,307	0,477	0,468	0,348	0,278
0,2			1,001	1,013	1,033	1,053	1,072	1,088	1,102	1,114	1,124	1,132	1,139
			0,010	0,040	0,160	0,120	0,200	0,170	0,200	0,200	0,370	0,320	0,290
			0,003	0,000	0,080	0,004	0,056	0,004	0,016	0,002	0,160	0,101	0,063
			0,008	0,033	0,151	0,110	0,191	0,161	0,192	0,193	0,364	0,314	0,285
0,3					1,001	1,008	1,020	1,033	1,047	1,060	1,072	1,083	1,093
					0,010	0,030	0,060	0,160	0,110	0,140	0,240	0,180	0,300
					0,003	0,003	0,006	0,080	0,005	0,014	0,096	0,021	0,128
					0,008	0,025	0,052	0,151	0,100	0,130	0,231	0,171	0,292
0,4							1,001	1,006	1,013	1,023	1,033	1,043	1,053
							0,010	0,030	0,040	0,070	0,080	0,100	0,120
							0,003	0,009	0,000	0,009	0,000	0,001	0,004
							0,008	0,025	0,033	0,062	0,071	0,090	0,110
0,5									1,001	1,005	1,010	1,017	1,025
									0,010	0,020	0,040	0,050	0,070
									0,003	0,002	0,008	0,002	0,005
									0,008	0,016	0,034	0,042	0,061
0,6											1,001	1,004	1,008
											0,010	0,020	0,030
											0,003	0,004	0,003
											0,008	0,016	0,025
0,7													1,001
													0,010
													0,003
													0,008

	0,2	0,3	0,4	0,5	0,6	0,7	0,8	0,9	1	1,1	1,2	1,3	1,4
0,1	1,040 0,410 0,333 0,390	1,094 0,220 0,072 0,203	1,155 0,430 0,222 0,417	1,197 0,280 0,037 0,270	1,227 0,460 0,195 0,452	1,248 0,490 0,211 0,484	1,263 0,430 0,141 0,425	1,274 0,470 0,173 0,466	1,283 0,350 0,047 0,346	1,290 0,330 0,023 0,327	1,296 0,490 0,179 0,487	1,300 0,360 0,046 0,358	1,304 0,440 0,124 0,438
0,2		1,007 0,050 0,028 0,040	1,040 0,410 0,333 0,390	1,056 0,450 0,348 0,433	1,094 0,220 0,072 0,203	1,127 0,260 0,078 0,245	1,155 0,250 0,042 0,237	1,178 0,320 0,092 0,308	1,197 0,280 0,037 0,270	1,213 0,380 0,125 0,371	1,227 0,500 0,235 0,492	1,238 0,370 0,097 0,363	1,248 0,490 0,211 0,484
0,3			1,002 0,010 0,002 0,005	1,011 0,030 0,000 0,019	1,040 0,410 0,333 0,390	1,043 0,090 0,006 0,074	1,069 0,120 0,001 0,103	1,094 0,370 0,222 0,353	1,116 0,180 0,008 0,164	1,137 0,370 0,178 0,355	1,155 0,210 0,002 0,197	1,171 0,320 0,098 0,308	1,185 0,440 0,207 0,429
0,4				1,001 0,010 0,003 0,005	1,007 0,040 0,018 0,030	1,017 0,070 0,028 0,056	1,040 0,120 0,043 0,100	1,036 0,080 0,005 0,065	1,056 0,450 0,348 0,433	1,075 0,130 0,003 0,113	1,094 0,170 0,022 0,153	1,111 0,210 0,043 0,194	1,127 0,260 0,078 0,245
0,5						1,005 0,020 0,003 0,011	1,007 0,030 0,008 0,021	1,021 0,050 0,001 0,035	1,040 0,410 0,333 0,390	1,033 0,070 0,000 0,055	1,048 0,110 0,018 0,094	1,063 0,200 0,087 0,183	1,079 0,140 0,009 0,123
0,6							1,002 0,010 0,001 0,005	1,007 0,030 0,008 0,020	1,011 0,030 0,000 0,019	1,024 0,060 0,006 0,044	1,040 0,410 0,333 0,390	1,030 0,070 0,005 0,056	1,043 0,110 0,025 0,094
0,7								1,001 0,010 0,002 0,005	1,003 0,040 0,027 0,033	1,012 0,080 0,048 0,067	1,015 0,040 0,004 0,027	1,026 0,060 0,003 0,043	1,040 0,080 0,003 0,060
0,8									1,001 0,010 0,003 0,005	1,003 0,110 0,097 0,103	1,007 0,030 0,008 0,020	1,009 0,030 0,005 0,020	1,017 0,050 0,008 0,036
0,9										1,001 0,010 0,004 0,006	1,002 0,010 0,002 0,005	1,004 0,020 0,005 0,013	1,011 0,030 0,000 0,017
1												1,002 0,010 0,001 0,004	1,005 0,020 0,003 0,011
1,1													1,001 0,010 0,004 0,006

	0,2	0,3	0,4	0,5	0,6	0,7	0,8	0,9	1	1,1	1,2	1,3	1,4
0,1	1,058 0,240 0,140 0,215	1,140 0,250 0,065 0,229	1,214 0,290 0,048 0,274	1,264 0,320 0,045 0,309	1,298 0,400 0,104 0,391	1,322 0,330 0,021 0,323	1,340 0,440 0,121 0,435	1,353 0,350 0,024 0,345	1,363 0,500 0,169 0,496	1,371 0,340 0,005 0,337	1,377 0,500 0,162 0,497	1,382 0,410 0,069 0,407	1,387 0,360 0,016 0,358
0,2		1,016 0,050 0,009 0,031	1,058 0,240 0,140 0,215	1,091 0,360 0,221 0,337	1,140 0,250 0,065 0,229	1,180 0,330 0,112 0,312	1,214 0,290 0,048 0,274	1,241 0,330 0,069 0,317	1,264 0,320 0,045 0,309	1,283 0,290 0,003 0,280	1,298 0,490 0,194 0,481	1,311 0,430 0,127 0,422	1,322 0,440 0,131 0,433
0,3			1,007 0,030 0,007 0,017	1,029 0,140 0,079 0,118	1,058 0,270 0,170 0,245	1,074 0,460 0,340 0,437	1,108 0,160 0,004 0,138	1,140 0,280 0,095 0,259	1,168 0,370 0,162 0,351	1,192 0,260 0,033 0,243	1,214 0,290 0,048 0,274	1,233 0,430 0,175 0,416	1,249 0,280 0,014 0,267
0,4				1,003 0,020 0,005 0,010	1,016 0,050 0,009 0,031	1,029 0,160 0,099 0,140	1,058 0,470 0,370 0,445	1,065 0,160 0,050 0,138	1,091 0,360 0,221 0,337	1,116 0,190 0,026 0,168	1,140 0,190 0,005 0,169	1,161 0,320 0,117 0,300	1,180 0,350 0,132 0,332
0,5					1,002 0,010 0,000 0,003	1,010 0,030 0,000 0,014	1,021 0,050 0,001 0,030	1,034 0,070 0,001 0,048	1,058 0,410 0,310 0,385	1,083 0,280 0,152 0,253	1,081 0,130 0,002 0,107	1,102 0,150 0,001 0,127	1,121 0,300 0,132 0,278
0,6						1,001 0,010 0,002 0,004	1,007 0,030 0,007 0,017	1,016 0,060 0,019 0,041	1,029 0,080 0,019 0,058	1,038 0,080 0,006 0,058	1,058 0,100 0,000 0,075	1,078 0,260 0,137 0,233	1,074 0,460 0,340 0,437
0,7								1,005 0,020 0,002 0,009	1,010 0,030 0,002 0,016	1,018 0,050 0,006 0,032	1,035 0,070 0,001 0,046	1,041 0,080 0,002 0,057	1,058 0,100 0,000 0,075
0,8									1,003 0,020 0,005 0,010	1,008 0,030 0,005 0,016	1,016 0,050 0,009 0,031	1,024 0,110 0,056 0,089	1,029 0,110 0,049 0,090
0,9										1,002 0,020 0,008 0,012	1,007 0,040 0,017 0,027	1,011 0,060 0,029 0,045	1,017 0,050 0,008 0,032
1											1,002 0,010 0,000 0,003	1,004 0,020 0,003 0,010	1,010 0,030 0,000 0,014
1,1												1,001 0,010 0,001 0,003	1,004 0,020 0,004 0,010
1,2													1,001 0,010 0,002 0,004

Доказательство нашей теоремы очень близко к доказательству теоремы 2 из статьи [36]. Однако выбор некоторых параметров будет по существу отличаться. Поэтому мы аккуратно введем необходимые обозначения и проверим, что стоящие за ними объекты обладают теми свойствами, которых хватит для ссылок на подходящие части доказательства упомянутой выше теоремы 2.

Итак, пусть заданы a, b, I, к, а, 3, 6, р, г, ас, А. Считаем, не ограничивая общности, что размерность п пространства достаточно велика. Пусть р і = р і (п) — минимальное простое число, большее, чем [рп] + 1. Хорошо известно, что тогда р 1 (п) = рп + р'(п), где р' = о(п) при п ^ то (см. [38], [39]). Положим

3 = \_3п — 6р ' (п) — 1 ] , а = [ап] +2, t = ^^[кП Ь 2 —

Ясно, что рі ~ рп, 3 ~ 3п, а ~ ап, п ^ то.

Рассмотрим (ср. начало п. 4.2 в статье [36]) совокупность векторов

X =

{x = (х і ,.

. ,Х п ) : X i G

{

|{ г : X i = 0 }| = [кп]}.

Как и в статье [36], проверим, что для любых векторов u , v G X из неравенства ( u , v ) > 3 2 следует оценка | u — v | ² 6 b ² , а из неравенства ( u , v ) 6 | 2 следует оценка | u — v | ² > a ² :

( u , v ) > а , u — v | 2 6 2M ² ^а = b ² , (2)

(u,v)6 3 =^|u—v|2>2И;2 = M—l.b2>' ■■ ■ • b2> t2 t2 [кп] — а кп — ап

>*3^1 . b ² = a ² . (3)

к — а

Как и в статье [36], выберем из X как можно большую по мощности подсовокупность М , в которой попарные расстояния между векторами лежат в пределах от а до b. В свете импликаций (2) и (3) достаточно добиться того, чтобы в известные границы попали скалярные произведения векторов из М . Но в точности такую же задачу мы решаем и в работе [36]: хотя значения функций а, 3 там немного другие и величина нормировки (аналог величины t) совсем иная, однако нормировка в итоге вовсе не важна (наша задача, очевидно, равносильна задаче о построении как можно большей совокупности (0,1)-векторов, в которой каждый вектор имеет ровно [кп] единиц и скалярное произведение любых двух векторов заключено между а и 3), а все, что нужно от функций а, 3, — это то, что они имеют асимптотики (1). В результате мы гарантируем существование подсовокупности М С X с мощность” . 1 = ( С + о^.

Положим

7 1 (п) = [кп] — (6 — 1)р і (п), 7 2 (п) = [кп] — (6 — 2)р і (п), ..., ₇ _/ (п) = [кп] — (6 — Г)р і (п).

Справедлива

Лемма 1. Пусть Q С М — произвольная свокупность векторов, у которых попарные скалярные произведения не равны ни одному из чисел 3 1 ,..., ^. Тогда

Р 1 (п) - 1

I Q I 6 £ с п =: . 2 .

i=0

Доказательство леммы 1. Домножим каждый вектор из совокупности М на t. Тогда возникнет совокупность М ‘ , состоящая из (0,1)-векторов (ср. [36]). А совокупность Q превратится в совокупность Q', в которой запрещены скалярные произведения 7 1 = 7 1 (п), ... ,7 l = 7 і (п). Далее, пользуемся, как и в работе [36], линейно-алгебраическим методом (см. также [40] - [42]). А именно, каждому вектору из совокупности Q' сопоставля- Р 1 (п) - 1

ем некоторый полином, лежащий в пространстве размерности ]7 С ^ , и доказываем, что .=0

сопоставленные полиномы линейно независимы, откуда и следует утверждение леммы. При этом полиномы буквально такие же, как в [36]. Но д л я доказательства их линейной независимости важно (см. [36]), чтобы на отрезке от а до 3 не было тех же вычетов по модулю р 1 = Р 1 (п), что и числа 7 1 ,..., 7 1 . Иными словами, остается проверить, что [кп] — 6р і (п) < а и [кп] — (5 — I — 1)р 1 (п) > /3. В самом деле,

[кп] — (5 — I — 1)р 1 > кп — 1 — 5рп — 5р + (I + 1)р 1 = кп — 1 — (к — а)п — 5р + (I + 1)р 1 = = ап — 1 — 5р + (I + 1)р 1 > ап — 1 — 5р + (/ + 1)рп > ап — 1 — 5р + (3 — а)п = 3п — 5р — 1 > 3;

[кп] — 5р 1 < кп — 5рп = кп — (к — а)п = ап < а.

Лемма доказана.

Положим

о. = ^^±рЕк , г = 1,...,/.

Ясно, что для любых x , y Е М утверждение “ | х — у | = с . ” равносильно утверждению “⁽ ^x , У ) = р ”.

Предположим, что X a,b,_C ₁ ,...,_C _l ( R ⁿ ) < (і+^)т₂ . Тогда и совокупность М допускает раскраску в указанное число цветов без троек точек одного цвета, образующих равнобедренный треугольник с длинами боковых сторон с . и длиной основания в пределах от а до Ь. Очевидно, найдется цвет, в который покрашены все точки из некоторой такой подсовокупности L С М , что | L | = (/ + 2)^ 2 . На множестве L как на множестве вершин построим граф с ребрами I типов, соединяя две вершины ребром г-го типа, коль скоро расстояние между ними равно с . . Пусть Q 1 С L — максимальная по мощности подсовокупность в L, свободная от каких-либо ребер. Тогда по лемме 1 имеем | Q 1 1 6 T ₂ . Следовательно, из каждой вершины в L \ Q 1 идет хотя бы одно ребро в Q 1 . Получаем не менее (/ + 1)7 2 разных ребер. Удаляем из L совокупность Q 1 и берем в оставшемся множестве максимальную по мощности совокупность Q 2 , свободную от ребер. Набираем еще хотя бы IT 2 ребер. И так далее. Суммируя возникающую арифметическую прогрессию, получаем в итоге не менее y+^yj+i) T 2 ребер. Предположим теперь, что из каждой вершины в L выходят только ребра разных типов. Тогда суммарное количество ребер не превосходит величины 2 (/ + 2)7 2 . Противоречие. Значит, в L есть вершина х , из которой выходят два ребра какого-то одного г-го типа. Пусть концы этих ребер суть у , х . Тогда треугольник с вершинами х , y , z равнобедренный, причем длины его боковых сторон равны с . , а длина основания лежит в пределах от а до Ь, т.к. L С М , а в М все длины находятся в этих пределах по построению. Таким образом, мы нашли одноцветный запрещенный треугольник, и это приводит нас к противоречию с исходным предположением, т.е.

(/ + 2)72 \ А / и теорема доказана.

Список литературы Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников

Райгородский A. M. Проблема Борсука и хроматические числа метрических пространств//Успехи матем. наук. 2001. Т. 56, вып. 1. С. 107-146
Raigorodskii A.M. Coloring Distance Graphs and Graphs of Diameters//Thirty Essays on Geometric Graph Theory, J. Pach ed. 2013. P. 429-460
Raigorodskii A.M. Cliques and cycles in distance graphs and graphs of diameters//Discrete Geometry and Algebraic Combinatorics, AMS, Contemporary Mathematics. 2014. N 625. P. 93-109
Brass P., Moser W., Pach. J. Research problems in discrete geometry//Springer. 2005
Sz´ekely L. A. Erd˝os on unit distances and the Szemer´edi-Trotter theorems//J. Bolyai Math. Soc. 2002. N 11. P. 649-666
Soifer A. The Mathematical Coloring Book. Springer, 2009
Hadwiger H. Ein ¨ ur den Euklidischen Raum//Portugaliae Math. 1944. Uberdeckungssatz f¨ N 4. P. 140-144
Larman D.G., Rogers C.A. The realization of distances within sets in Euclidean space//Mathematika. 1972. N 19. P. 1-24
Frankl P, Wilson R. Intersection theorems with geometric consequences//Combinatorica. 1981. N 1. P. 357-368
Райгородский A. M. О хроматическом числе пространства//Успехи матем. наук. 2000. Т. 55, вып. 2. С. 147-148
Benda M., Perles M. Colorings of metric spaces//Geombinatorics. 2000. N 9. P. 113-126
Пономаренко E.I., Райгородский A.M. Новая нижняя оценка хроматического числа рационального пространства с одним и двумя запрещенными расстояниями//Матем. заметки. 2015. Т. 97, вып. 2. С. 84-89
Пономаренко E.I., Райгородский A.M. Новая нижняя оценка хроматического числа рационального пространства//Успехи матем. наук. 2013. Т. 68, вып. 5. C. 183-184
Пономаренко E.I., Райгородский A.M. О хроматическом числе пространства Q𝑛//Труды МФТИ. 2012. Т. 4, вып. 1. C. 127-130
Райгородский A.M. О хроматическом числе пространства с 𝑙𝑞-нормой//Успехи матем. наук. 2004. Т. 59, вып. 5. C. 161-162
Kang J.-H., F¨uredi Z. Distance graphs on Z𝑛 with 𝑙1-norm//Theoretical Comp. Sci. 2004. V. 319, N 1-3. P. 357-366
Kupavskii A. Б. On the chromatic NUMBER. of R𝑛 with an arbitrary norm//Discrete Math. 2011. N 311. P. 437-440
Lova´sz L. Self-dual polytopes and the chromatic NUMBER. of distance graphs on the sphere//Acta Sci. Math. 1983. N 45. P. 317-323
Купавский A. Б. О раскрасках сфер, вложенных в R𝑛//Матем. сборник. 2011. Т. 202, вып. 6. С. 83-110
Райгородский A.M. О хроматических числах сфер в евклидовых пространствах//Доклады РАН. 2010. Т. 432, вып. 2. С. 174-177
Raigorodskii A. M. On the chromatic NUMBER.s of spheres in R𝑛//Combinbatorica. 2012. V. 32, N 1. P. 111-123
Купавский A.Б. Хроматическое число пространства R𝑛 с множеством запрещенных расстояний//Доклады РАН. 2010. -Т. 435, вып. 6. С. 740-743
Райгородский A.M. О хроматическом числе пространства с двумя запрещенными расстояниями//Доклады РАН. 2006. Т. 408, вып. 5. С. 601-604
Райгородский A.M., Шитова И.М. О хроматических числах вещественных и рациональных пространств с вещественными или рациональными запрещенными расстояниями//Матем. сборник. 2008. Т. 199, вып. 4. С. 107-142
Горская Е.С., Митричева И.М., Протасов В.Ю., Райгородский A.M. Оценка хроматических чисел евклидова пространства методами выпуклой минимизации//Матем. сборник. 2009. Т. 200, вып. 6. С. 3-22
Мощевитин Н.Г., Райгородский A.M. О раскрасках пространства R𝑛 с несколькими запрещенными расстояниями//Матем. заметки. 2007. Т. 81, вып. 5. С. 733-744
Бердников А.В., Райгородский A.M. Хроматические числа евклидова пространства с двумя запрещенными расстояниями//Матем. заметки. 2014. Т. 96, вып. 5. С. 790-793
Graham R.L., Rothschild B.L.,Spencer J.H. Ramsey theory//John Wily and Sons, NY, Second Edition. 1990
Frankl P., R¨odl V. All triangles are Ramsey//Transactions of the Amer. Math. Soc. 1986. V. 297, N 2. P. 777-779
Frankl P., R¨odl V. Forbidden intersections//Transactions of the Amer. Math. Soc. 1987. V. 300, N 1. P. 259-286
Frankl P., R¨odl V. A partition property of simplices in Euclidean space//J. Amer. Math. Soc. 1990. V. 3, N 1. P. 1-7
Райгородский A.M., Звонарев A.E., Самиров Д.В., Харламова А.А. Улучшение теоремы Франкла-Рёдля о числе ребер гиперграфа с запретами на пересечения//Доклады РАН. 2014. Т. 457, вып. 2. С. 144-146
Райгородский A.M., Звонарев A.E., Самиров Д.В., Харламова А.А. О хроматическом числе пространства с запрещенным равносторонним треугольником//Матем. сборник. 2014. Т. 205, вып. 9. С. 97-120
Райгородский A.M., Звонарев A.E. Улучшения теоремы Франкла-Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником//Труды Математического Института имени В.А. Стеклова. 2015. Т. 288. С. 109-119
Райгородский A.M., Самиров Д.В. Хроматические числа пространств с запрещенными одноцветными треугольниками//Матем. заметки. 2013. Т. 93, вып. 1. С. 134-143
Райгородский A.M., Самиров Д.В. Новые нижние оценки хроматического числа пространства с запрещенными равнобедренными треугольниками//Итоги науки и техники, Современная математика и ее приложения. 2013. Т. 125. С. 252-268
Райгородский A.M., Самиров Д.В. Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками//Доклады РАН. 2014. Т. 456, вып. 3. С. 280-283
Прахар К. Распределение простых чисел//М.: Мир, 1967
Baker R.C., Harman G., Printz J. The difference between consecutive primes, II//Proceedings of the London Mathematical Society. 2001. N 83. P. 532-562
Райгородский A.M. Линейно-алгебраический метод в комбинаторике//М.: МЦНМО, Второе издание. 2015
Babai L., Frankl P. Linear algebra methods in combinatorics//Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2. 1992
Alon N., Babai L., Suzuki H. Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems//J. Combin. Theory A. 1991. N 58. P. 165-180

Еще

Статья научная