✖


Jump to content

Число Ван дер Вардена

Теорема Ван дер Вардена утверждает, что для любых целых положительных чисел 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 цветов
3 9 [2] 27 [2]  76 [3]  >170  >225 
4 35 [2] 293 [4]  >1048  >2254  >9778 
5 178 [5] >2173  >17 705  >98 741 [6]  >98 748 
6 1,132 [7] >11 191  >157 209 [8]  >786 740 [8]  >1 555 549 [8]  
7 >3703  >48 811  >2 284 751 [8]  >15 993 257 [8]  >111 952 799 [8]  
8 >11 495  >238 400  >12 288 155 [8]  >86 017 085 [8]  >602 119 595 [8]  
9 >41 265  >932 745  >139 847 085 [8]  >978 929 595 [8]  >6 852 507 165 [8]  
10 >103 474  >4 173 724  >1 189 640 578 [8]  >8 327 484 046 [8]  >58 292 388 322 [8]  
11 >193 941  >18 603 731  >3 464 368 083 [8]  >38 108 048 913 [8]  >419 188 538 043 [8]  

Некоторые раскраски нижней границы, вычисленные с использованием подхода SAT Мэрийном Дж. Хойле. [6] можно найти на странице проекта github .

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

как доказал Гауэрс . [9]

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

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

Иногда также пишут 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

Он хватался [2]

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

Числа Ван дер Вардена примитивно рекурсивны , как доказал Шелах ; [22] на самом деле он доказал, что они (максимум) на пятом уровне иерархии Гжегорчиков .

См. также

[ редактировать ]

Ссылки

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

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

[ редактировать ]
[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Van_der_Waerden_number&oldid=1233574311"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 5e471864acb4285ea23d9ba04a6198a4__1720555980
URL1:https://arc.ask3.ru/arc/aa/5e/a4/5e471864acb4285ea23d9ba04a6198a4.html
Заголовок, (Title) документа по адресу, URL1:
Van der Waerden number - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)