Число Ван дер Вардена - Van der Waerden number

Теорема Ван дер Вардена заявляет, что для любого положительные целые числа р и k существует положительное целое число N такие, что если целые числа {1, 2, ..., N} раскрашены, каждый с одним из р разных цветов, то есть как минимум k целые числа в арифметическая прогрессия все одного цвета. Самый маленький такой N это число Ван дер Вардена W(р, k).

Таблицы чисел Ван дер Вардена

Есть два случая, когда число Ван дер Вардена W(р, k) легко вычислить: во-первых, когда количество цветов р равно 1, W(1, k) = k для любого целого k, поскольку один цвет дает только тривиальные раскраски RRRRR ... RRR (для одного цвета, обозначенного R). Во-вторых, когда длина k форсированной арифметической прогрессии - 2, один имеет W(р, 2) = р + 1, так как можно построить раскраску, которая избегает арифметических прогрессий длины 2, используя каждый цвет не более одного раза, но использование любого цвета дважды создает арифметическую прогрессию длины 2. (Например, для р = 3, самая длинная раскраска, которая позволяет избежать арифметической прогрессии длины 2, - это RGB.) Есть только семь других чисел Ван-дер-Вардена, которые точно известны. В таблице ниже приведены точные значения и границы значений W(р, k); значения взяты из Rabung и Lotts, если не указано иное.^[1]

к г	2 цвета	3 цвета	4 цвета	5 цветов	6 цветов
3	9[2]	27[2]	76[3]	>170	>223
4	35[2]	293[4]	>1,048	>2,254	>9,778
5	178[5]	>2,173	>17,705	>98,740	>98,748
6	1,132[6]	>11,191	>91,331	>540,025	>816,981
7	>3,703	>48,811	>420,217	>1,381,687	>7,465,909
8	>11,495	>238,400	>2,388,317	>10,743,258	>57,445,718
9	>41,265	>932,745	>10,898,729	>79,706,009	>458,062,329[7]
10	>103,474	>4,173,724	>76,049,218	>542,694,970[7]	>2,615,305,384[7]
11	>193,941	>18,603,731	>305,513,57[7]	>2,967,283,511[7]	>3,004,668,671[7]

Числа Ван дер Вардена с р ≥ 2 ограничены сверху

${\displaystyle W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}}$

как доказано Гауэрс.^[8]

Для простое число п, двухцветное число Ван дер Вардена ограничено снизу величиной

${\displaystyle p\cdot 2^{p}\leq W(2,p+1),}$

как доказано Берлекамп.^[9]

Иногда также пишут ш(р; k₁, k₂, ..., k_р) для обозначения наименьшего числа ш такая, что любая раскраска целых чисел {1, 2, ..., ш} с р цвета содержат прогрессию длины k_я цвета я, для некоторых я. Такие номера называются недиагональные числа Ван дер Вардена. Таким образом W(р, k) = ш(р; k, k, ..., kНиже приводится список некоторых известных чисел Ван дер Вардена:

Известные числа Ван дер Вардена

ш (г; к1, k2,…, Kр)	Ценить	Ссылка
ш (2; 3,3)	9	Chvátal [2]
ш (2; 3,4)	18	Chvátal [2]
ш (2; 3,5)	22	Chvátal [2]
ш (2; 3,6)	32	Chvátal [2]
ш (2; 3,7)	46	Chvátal [2]
ш (2; 3,8)	58	Билер и О'Нил [3]
ш (2; 3,9)	77	Билер и О'Нил [3]
ш (2; 3,10)	97	Билер и О'Нил [3]
ш (2; 3,11)	114	Лэндман, Робертсон и Калвер [10]
ш (2; 3,12)	135	Лэндман, Робертсон и Калвер [10]
ш (2; 3,13)	160	Лэндман, Робертсон и Калвер [10]
ш (2; 3,14)	186	Курил [11]
ш (2; 3,15)	218	Курил [11]
ш (2; 3,16)	238	Курил [11]
ш (2; 3,17)	279	Ахмед [12]
ш (2; 3,18)	312	Ахмед [12]
ш (2; 3,19)	349	Ахмед, Куллманн и Сневили [13]
ш (2; 3,20)	389	Ахмед, Куллманн и Сневили [13] (предположительно); Курил [14] (проверено)
ш (2; 4,4)	35	Chvátal [2]
ш (2; 4,5)	55	Chvátal [2]
ш (2; 4,6)	73	Билер и О'Нил [3]
ш (2; 4,7)	109	Beeler [15]
ш (2; 4,8)	146	Курил [11]
ш (2; 4,9)	309	Ахмед [16]
ш (2; 5,5)	178	Стивенс и Шантарам [5]
ш (2; 5,6)	206	Курил [11]
ш (2; 5,7)	260	Ахмед [17]
ш (2; 6,6)	1132	Курил и Пол [6]
ш (3; 2, 3, 3)	14	коричневый [18]
ш (3; 2, 3, 4)	21	коричневый [18]
ш (3; 2, 3, 5)	32	коричневый [18]
ш (3; 2, 3, 6)	40	коричневый [18]
ш (3; 2, 3, 7)	55	Лэндман, Робертсон и Калвер [10]
ш (3; 2, 3, 8)	72	Курил [11]
ш (3; 2, 3, 9)	90	Ахмед [19]
ш (3; 2, 3, 10)	108	Ахмед [19]
ш (3; 2, 3, 11)	129	Ахмед [19]
ш (3; 2, 3, 12)	150	Ахмед [19]
ш (3; 2, 3, 13)	171	Ахмед [19]
ш (3; 2, 3, 14)	202	Курил [4]
ш (3; 2, 4, 4)	40	коричневый [18]
ш (3; 2, 4, 5)	71	коричневый [18]
ш (3; 2, 4, 6)	83	Лэндман, Робертсон и Калвер [10]
ш (3; 2, 4, 7)	119	Курил [11]
ш (3; 2, 4, 8)	157	Курил [4]
ш (3; 2, 5, 5)	180	Ахмед [19]
ш (3; 2, 5, 6)	246	Курил [4]
ш (3; 3, 3, 3)	27	Chvátal [2]
ш (3; 3, 3, 4)	51	Билер и О'Нил [3]
ш (3; 3, 3, 5)	80	Лэндман, Робертсон и Калвер [10]
ш (3; 3, 3, 6)	107	Ахмед [16]
ш (3; 3, 4, 4)	89	Лэндман, Робертсон и Калвер [10]
ш (3; 4, 4, 4)	293	Курил [4]
ш (4; 2, 2, 3, 3)	17	коричневый [18]
ш (4; 2, 2, 3, 4)	25	коричневый [18]
ш (4; 2, 2, 3, 5)	43	коричневый [18]
ш (4; 2, 2, 3, 6)	48	Лэндман, Робертсон и Калвер [10]
ш (4; 2, 2, 3, 7)	65	Лэндман, Робертсон и Калвер [10]
ш (4; 2, 2, 3, 8)	83	Ахмед [19]
ш (4; 2, 2, 3, 9)	99	Ахмед [19]
ш (4; 2, 2, 3, 10)	119	Ахмед [19]
ш (4; 2, 2, 3, 11)	141	Швейцер [20]
ш (4; 2, 2, 3, 12)	163	Курил [14]
ш (4; 2, 2, 4, 4)	53	коричневый [18]
ш (4; 2, 2, 4, 5)	75	Ахмед [19]
ш (4; 2, 2, 4, 6)	93	Ахмед [19]
ш (4; 2, 2, 4, 7)	143	Курил [4]
ш (4; 2, 3, 3, 3)	40	коричневый [18]
ш (4; 2, 3, 3, 4)	60	Лэндман, Робертсон и Калвер [10]
ш (4; 2, 3, 3, 5)	86	Ахмед [19]
ш (4; 2, 3, 3, 6)	115	Курил [14]
ш (4; 3, 3, 3, 3)	76	Билер и О'Нил [3]
ш (5; 2, 2, 2, 3, 3)	20	Лэндман, Робертсон и Калвер [10]
ш (5; 2, 2, 2, 3, 4)	29	Ахмед [19]
ш (5; 2, 2, 2, 3, 5)	44	Ахмед [19]
ш (5; 2, 2, 2, 3, 6)	56	Ахмед [19]
ш (5; 2, 2, 2, 3, 7)	72	Ахмед [19]
ш (5; 2, 2, 2, 3, 8)	88	Ахмед [19]
ш (5; 2, 2, 2, 3, 9)	107	Курил [4]
ш (5; 2, 2, 2, 4, 4)	54	Ахмед [19]
ш (5; 2, 2, 2, 4, 5)	79	Ахмед [19]
ш (5; 2, 2, 2, 4, 6)	101	Курил [4]
ш (5; 2, 2, 3, 3, 3)	41	Лэндман, Робертсон и Калвер [10]
ш (5; 2, 2, 3, 3, 4)	63	Ахмед [19]
ш (5; 2, 2, 3, 3, 5)	95	Курил [14]
ш (6; 2, 2, 2, 2, 3, 3)	21	Ахмед [19]
ш (6; 2, 2, 2, 2, 3, 4)	33	Ахмед [19]
ш (6; 2, 2, 2, 2, 3, 5)	50	Ахмед [19]
ш (6; 2, 2, 2, 2, 3, 6)	60	Ахмед [19]
ш (6; 2, 2, 2, 2, 4, 4)	56	Ахмед [19]
ш (6; 2, 2, 2, 3, 3, 3)	42	Ахмед [19]
ш (7; 2, 2, 2, 2, 2, 3, 3)	24	Ахмед [19]
ш (7; 2, 2, 2, 2, 2, 3, 4)	36	Ахмед [19]
ш (7; 2, 2, 2, 2, 2, 3, 5)	55	Ахмед [16]
ш (7; 2, 2, 2, 2, 2, 3, 6)	65	Ахмед [17]
ш (7; 2, 2, 2, 2, 2, 4, 4)	66	Ахмед [17]
ш (7; 2, 2, 2, 2, 3, 3, 3)	45	Ахмед [17]
ш (8; 2, 2, 2, 2, 2, 2, 3, 3)	25	Ахмед [19]
ш (8; 2, 2, 2, 2, 2, 2, 3, 4)	40	Ахмед [16]
ш (8; 2, 2, 2, 2, 2, 2, 3, 5)	61	Ахмед [17]
ш (8; 2, 2, 2, 2, 2, 2, 3, 6)	71	Ахмед [17]
ш (8; 2, 2, 2, 2, 2, 2, 4, 4)	67	Ахмед [17]
ш (8; 2, 2, 2, 2, 2, 3, 3, 3)	49	Ахмед [17]
ш (9; 2, 2, 2, 2, 2, 2, 2, 3, 3)	28	Ахмед [19]
ш (9; 2, 2, 2, 2, 2, 2, 2, 3, 4)	42	Ахмед [17]
ш (9; 2, 2, 2, 2, 2, 2, 2, 3, 5)	65	Ахмед [17]
ш (9; 2, 2, 2, 2, 2, 2, 3, 3, 3)	52	Ахмед [17]
ш (10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	31	Ахмед [17]
ш (10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	45	Ахмед [17]
ш (10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5)	70	Ахмед [17]
ш (11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	33	Ахмед [17]
ш (11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	48	Ахмед [17]
ш (12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	35	Ахмед [17]
ш (12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	52	Ахмед [17]
ш (13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	37	Ахмед [17]
ш (13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4)	55	Ахмед [17]
ш (14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	39	Ахмед [17]
ш (15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	42	Ахмед [17]
ш (16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	44	Ахмед [17]
ш (17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	46	Ахмед [17]
ш (18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	48	Ахмед [17]
ш (19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	50	Ахмед [17]
ш (20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	51	Ахмед [17]

Числа Ван дер Вардена примитивно рекурсивный, как доказано Шела;^[21] на самом деле он доказал, что они (максимум) на пятом уровне ${\displaystyle {\mathcal {E}}^{5}}$ из Иерархия Гжегорчика.

Смотрите также

• Число Рамсея
• Раскраска графика

Рекомендации

1. Рабунг, Джон; Лотц, Марк (2012). «Улучшение использования циклических застежек-молний при нахождении нижних границ для чисел Ван-дер-Вардена». Электрон. J. Combin. 19 (2). МИСТЕР  2928650.
2. Chvátal, Вашек (1970). «Какие-то неизвестные числа ван дер Вардена». В Гай, Ричард; Ханани, Хаим; Зауэр, Норберт; и другие. (ред.). Комбинаторные структуры и их приложения.. Нью-Йорк: Гордон и Брич. С. 31–33. МИСТЕР  0266891.
3. Билер, Майкл Д .; О'Нил, Патрик Э. (1979). «Некоторые новые числа Ван дер Вардена». Дискретная математика. 28 (2): 135–146. Дои:10.1016 / 0012-365x (79) 90090-6. МИСТЕР  0546646.
4. Курил, Михал (2012). «Вычисление числа Ван дер Вардена W (3,4) = 293». Целые числа. 12: A46. МИСТЕР  3083419.
5. Стивенс, Ричард С .; Шантарам Р. (1978). «Компьютерные перегородки Ван дер Вардена». Математика. Комп. 32 (142): 635–636. Дои:10.1090 / с0025-5718-1978-0491468-х. МИСТЕР  0491468.
6. Курил, Михал; Пол, Джером Л. (2008). «Число Ван дер Вардена W (2,6) равно 1132». Экспериментальная математика. 17 (1): 53–61. Дои:10.1080/10586458.2008.10129025. МИСТЕР  2410115.
7. "Дэниел Монро, Ван дер Варден Числа". vdwnumbers.org. Получено 2015-09-19.
8. Гауэрс, Тимоти (2001). «Новое доказательство теоремы Семереди». Геом. Функц. Анальный. 11 (3): 465–588. Дои:10.1007 / s00039-001-0332-9. МИСТЕР  1844079.
9. Берлекамп, Э. (1968). «Конструкция перегородок, избегающая длинных арифметических прогрессий». Канадский математический бюллетень. 11 (3): 409–414. Дои:10.4153 / CMB-1968-047-7. МИСТЕР  0232743.
10. Ландман, Брюс; Робертсон, Аарон; Калвер, Клэй (2005). "Некоторые новые точные числа Ван дер Вардена" (PDF). Целые числа. 5 (2): A10. МИСТЕР  2192088.
11. Курил, Михал (2006). Структура обратного отслеживания для кластеров Беовульфа с расширением для многокластерных вычислений и реализация задачи эталонного теста Sat (Кандидатская диссертация). Университет Цинциннати.
12. Ахмед, Танбир (2010). «Два новых числа Ван дер Вардена w (2; 3,17) и w (2; 3,18)». Целые числа. 10 (4): 369–377. Дои:10.1515 / интег.2010.032. МИСТЕР  2684128.
13. Ахмед, Танбир; Куллманн, Оливер; Сневилы, Охотник (2014). «О числах Ван дер Вардена w (2; 3, t)». Дискретное приложение Математика. 174 (2014): 27–51. arXiv:1102.5433. Дои:10.1016 / j.dam.2014.05.007. МИСТЕР  3215454.
14. Курил, Михал (2015). «Использование кластеров FPGA для вычислений SAT». Параллельные вычисления: на пути к Exascale: 525–532.
15. Билер, Майкл Д. (1983). «Новое число Ван дер Вардена». Дискретная прикладная математика. 6 (2): 207. Дои:10.1016 / 0166-218x (83) 90073-2. МИСТЕР  0707027.
16. Ахмед, Танбир (2012). «О вычислении точных чисел Ван дер Вардена». Целые числа. 12 (3): 417–425. Дои:10.1515 / интег.2011.112. МИСТЕР  2955523.
17. Ахмед, Танбир (2013). «Еще несколько чисел Ван дер Вардена». Журнал целочисленных последовательностей. 16 (4): 13.4.4. МИСТЕР  3056628.
18. Браун, Т. К. (1974). «Некоторые новые числа Ван дер Вардена (предварительный отчет)». Уведомления Американского математического общества. 21: А-432.
19. Ахмед, Танбир (2009). «Некоторые новые числа Ван дер Вардена и некоторые числа типа Ван дер Вардена». Целые числа. 9: A6. Дои:10.1515 / интег.2009.007. МИСТЕР  2506138.
20. Швейцер, Паскаль (2009). Проблемы неизвестной сложности, изоморфизма графов и теоретических чисел Рамсея (Кандидатская диссертация). U. des Saarlandes.
21. Шелах, Сахарон (1988). "Примитивные рекурсивные оценки для чисел Ван дер Вардена". J. Amer. Математика. Soc. 1 (3): 683–697. Дои:10.2307/1990952. JSTOR  1990952. МИСТЕР  0929498.

дальнейшее чтение

• Ландман, Брюс М .; Робертсон, Аарон (2014). Теория Рамсея о целых числах. Студенческая математическая библиотека. 73 (Второе изд.). Провиденс, Род-Айленд: Американское математическое общество. Дои:10.1090 / stml / 073. ISBN  978-0-8218-9867-3. МИСТЕР  3243507.
• Herwig, P.R .; Heule, M. J. H .; van Lambalgen, P.M .; ван Маарен, Х. (2007). «Новый метод построения нижних оценок для чисел Ван дер Вардена». Электронный журнал комбинаторики. 14 (1). МИСТЕР  2285810.

внешняя ссылка

• О'Брайант, Кевин и Вайсштейн, Эрик В. «Число Ван дер Вардена». MathWorld.