Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Таблицы чисел Ван дер Вардена [ править ]

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

к \ г2 цвета3 цвета4 цвета5 цветов6 цветов
39 [2]27 [2]  76 [3]  > 170  > 223  
435 [2]293 [4]  > 1048  > 2254  > 9 778  
5178 [5]> 2 173  > 17 705  > 98 740  > 98 748  
61,132 [6]> 11 191  > 157 209 [7]  > 786 740 [7]  > 1 555 549 [7]  
7> 3703  > 48 811  > 2 284 751 [7]  > 15 993 257 [7]  > 111 952 799 [7]  
8> 11 495  > 238 400  > 12 288 155 [7]  > 86 017 085 [7]  > 602 119 595 [7]  
9> 41 265  > 932 745  > 139 847 085 [7]  > 978 929 595 [7]  > 6 852 507 165 [7]  
10> 103 474  > 4 173 724  > 1,189,640,578 [7]  > 8 327 484 046 [7]  > 58 292 388 322 [7]  
11> 193 941  > 18 603 731  > 3 464 368 083 [7]  > 38 108 048 913 [7]  > 419 188 538 043 [7]  

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

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

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

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

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

Известные числа Ван дер Вардена
w (r; k 1 , k 2 ,…, k r )ЗначениеСправка

ш (2; 3,3)

9

Chvátal [2]

ш (2; 3,4)18Chvátal [2]
ш (2; 3,5)22Chvátal [2]
ш (2; 3,6)32Chvátal [2]
ш (2; 3,7)46Chvá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)55Chvátal [2]
ш (2; 4,6)73Билер и О'Нил [3]
ш (2; 4,7)109Билер [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)27Chvá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] в том , что он доказал , что они (по большей части ) на пятом уровне в иерархии Гжегорчика .

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Рабунг, Джон; Лотц, Марк (2012). «Улучшение использования циклических застежек-молний при поиске нижних границ для чисел Ван-дер-Вардена» . Электрон. J. Combin. 19 (2). Руководство по ремонту  2928650 .
  2. ^ a b c d e f g h i j k Chvátal, Vašek (1970). «Некоторые неизвестные числа Ван дер Вардена». В Гай, Ричард; Ханани, Хаим; Зауэр, Норберт; и другие. (ред.). Комбинаторные структуры и их приложения . Нью-Йорк: Гордон и Брич. С. 31–33. Руководство по ремонту 0266891 . 
  3. ^ a b c d e f g Билер, Майкл Д.; О'Нил, Патрик Э. (1979). «Некоторые новые числа Ван дер Вардена». Дискретная математика . 28 (2): 135–146. DOI : 10.1016 / 0012-365x (79) 90090-6 . Руководство по ремонту 0546646 . 
  4. ^ a b c d e f g h Курил, Михал (2012). «Вычисление числа Ван дер Вардена W (3,4) = 293». Целые числа . 12 : A46. Руководство по ремонту 3083419 . 
  5. ^ a b Стивенс, Ричард С .; Шантарам Р. (1978). "Компьютерные перегородки Ван дер Вардена" . Математика. Комп. 32 (142): 635–636. DOI : 10.1090 / s0025-5718-1978-0491468-х . Руководство по ремонту 0491468 .  
  6. ^ a b Курил, Михал; Пол, Джером Л. (2008). «Число Ван дер Вардена W (2,6) равно 1132». Экспериментальная математика . 17 (1): 53–61. DOI : 10.1080 / 10586458.2008.10129025 . Руководство по ремонту 2410115 . 
  7. ^ Б с д е е г ч я J к л м п о р д р Монро, Daniel (2019). «Новые нижние границы для чисел Ван-дер-Вардена с использованием распределенных вычислений». arXiv : 1603.03301 .
  8. ^ Гауэрс, Тимоти (2001). «Новое доказательство теоремы Семереди» . Геом. Функц. Анальный. 11 (3): 465–588. DOI : 10.1007 / s00039-001-0332-9 . Руководство по ремонту 1844079 .  
  9. Перейти ↑ Berlekamp, ​​E. (1968). «Конструкция перегородок, исключающая длинные арифметические прогрессии». Канадский математический бюллетень . 11 (3): 409–414. DOI : 10,4153 / CMB-1968-047-7 . Руководство по ремонту 0232743 . 
  10. ^ Б с д е е г ч я J K L Ландман, Брюс; Робертсон, Аарон; Калвер, Клей (2005). «Некоторые новые точные числа Ван дер Вардена» (PDF) . Целые числа . 5 (2): A10. Руководство по ремонту 2192088 .  
  11. ^ a b c d e f g Курил, Михал (2006). Структура обратного отслеживания для кластеров Беовульфа с расширением для многокластерных вычислений и реализация контрольной задачи Sat (кандидатская диссертация). Университет Цинциннати.
  12. ^ a b Ахмед, Танбир (2010). «Два новых числа Ван дер Вардена w (2; 3,17) и w (2; 3,18)». Целые числа . 10 (4): 369–377. DOI : 10.1515 / integ.2010.032 . Руководство по ремонту 2684128 . 
  13. ^ а б Ахмед, Танбир; Куллманн, Оливер; Сневилы, Охотник (2014). «О числах Ван дер Вардена w (2; 3, t)». Дискретное приложение Математика . 174 (2014): 27–51. arXiv : 1102,5433 . DOI : 10.1016 / j.dam.2014.05.007 . Руководство по ремонту 3215454 . 
  14. ^ a b c d Курил, Михал (2015). «Использование кластеров FPGA для вычислений SAT». Параллельные вычисления: на пути к Exascale : 525–532.
  15. ^ Билер, Майкл Д. (1983). «Новое число Ван дер Вардена». Дискретная прикладная математика . 6 (2): 207. DOI : 10.1016 / 0166-218x (83) 90073-2 . Руководство по ремонту 0707027 . 
  16. ^ a b c d Ахмед, Танбир (2012). «О вычислении точных чисел Ван дер Вардена». Целые числа . 12 (3): 417–425. DOI : 10.1515 / integ.2011.112 . Руководство по ремонту 2955523 . 
  17. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa Ахмед, Танбир (2013). «Еще несколько чисел Ван дер Вардена». Журнал целочисленных последовательностей . 16 (4): 13.4.4. Руководство по ремонту 3056628 . 
  18. ^ a b c d e f g h i j k Brown, TC (1974). «Некоторые новые числа Ван дер Вардена (предварительный отчет)». Уведомления Американского математического общества . 21 : А-432.
  19. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad Ахмед, Танбир (2009). «Некоторые новые числа Ван дер Вардена и некоторые числа типа Ван дер Вардена». Целые числа . 9 : A6. DOI : 10.1515 / integ.2009.007 . Руководство по ремонту 2506138 . 
  20. ^ Швейцер, Паскаль (2009). Проблемы неизвестной сложности, изоморфизма графов и теоретических чисел Рамсея (кандидатская диссертация). U. des Saarlandes.
  21. ^ Шелах, Сахарон (1988). «Примитивные рекурсивные оценки для чисел Ван дер Вардена» . J. Amer. Математика. Soc. 1 (3): 683–697. DOI : 10.2307 / 1990952 . JSTOR 1990952 . Руководство по ремонту 0929498 .   

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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