ファンデルワールデン数
ラムゼー理論における整数

ファン・デル・ヴェルデンの定理は、任意の正の整数 rとkに対して、ある正の整数Nが存在し、整数 {1, 2, ..., N } がそれぞれr種類の異なる色で彩色されている場合、等差数列で少なくともk個の整数がすべて同じ色になるという定理である。そのような最小のNはファン・デル・ヴェルデン数 W ( r , k ) である。

ファンデルワールデン数の表

ファンデルワールデン数W ( r , k ) が簡単に計算できるケースが 2 つあります。1 つ目は、色の数rが 1 に等しい場合で、任意の整数kに対してW (1, k ) = kとなります。これは、1 つの色では、自明な着色 RRRRR...RRR (R で示される単一の色に対して) のみが生成されるためです。2 つ目は、強制等差数列の長さkが 2 の場合で、 W ( r , 2) = r + 1 となります。これは、各色を最大で 1 回使用することで長さ 2 の等差数列を回避する着色を構成できますが、任意の色を 2 回使用すると、長さ 2 の等差数列が作成されるためです。(たとえば、r = 3 の場合、長さ 2 の等差数列を回避する最長の着色は RGB です。) 正確にわかっている他のファンデルワールデン数は 7 つだけです。以下の表はW ( r , k )の正確な値と境界値を示しています。値は特に断りのない限り、RabungとLottsから引用されています。[1]

k\r 2色 3色 4色 5色 6色
3 9 [2] 27 [2]   76 [3]   170以上   >225  
4 35 [2] 293 [4]   >1,048   >2,254   >9,778  
5 178 [5] >2,173   >17,705   >98,741 [6]   >98,748  
6 1,132 [7] >11,191   >157,209 [8]   >786,740 [8]   >1,555,549 [8]  
7 >3,703   >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]   >9億7892万9595 [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]  

Marijn JH Heule [6]によるSATアプローチを使用して計算されたいくつかの下限色分けは、githubプロジェクトページで見つけることができます。

r ≥ 2 のファンデルワールデン数は、

W （ r 、 け ） ≤ 2 2 r 2 2 け + 9 {\displaystyle W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}}

ガワーズによって証明された。[9]

素数 pに対して、2色ファンデルワールデン数は以下のように下限が定められる。

p ⋅ 2 p ≤ W （ 2 、 p + 1 ） 、 {\displaystyle p\cdot 2^{p}\leq W(2,p+1),}

ベルレカンプによって証明された。[10]

また、w (r; k 1 , k 2 , ..., k r )と書くこともある。これは、整数 {1, 2, ..., w }をr色で彩色した際に、あるiに対して色iの長さk iの累乗が含まれるような最小の数wを意味する。このような数は非対角ファンデルヴェルデン数と呼ばれる。したがって、W ( r , k ) = w (r; k , k , ..., k ) となる。以下は、既知のファンデルヴェルデン数の一覧である。

既知のファンデルワールデン数
w(r;k 1 , k 2 , …, k r ) 価値 参照

w(2; 3,3)

9

クヴァタル[2]

w(2; 3,4) 18 クヴァタル[2]
w(2; 3,5) 22 クヴァタル[2]
w(2; 3,6) 32 クヴァタル[2]
w(2; 3,7) 46 クヴァタル[2]
w(2; 3,8) 58 ビーラーとオニール[3]
w(2; 3,9) 77 ビーラーとオニール[3]
w(2; 3,10) 97 ビーラーとオニール[3]
w(2; 3,11) 114 ランドマン、ロバートソン、カルバー[11]
w(2; 3,12) 135 ランドマン、ロバートソン、カルバー[11]
w(2; 3,13) 160 ランドマン、ロバートソン、カルバー[11]
w(2; 3,14) 186 クーリル[12]
w(2; 3,15) 218 クーリル[12]
w(2; 3,16) 238 クーリル[12]
w(2; 3,17) 279 アハメド[13]
w(2; 3,18) 312 アハメド[13]
w(2; 3,19) 349 アーメド、クルマン、スネヴィリー[14]
w(2; 3,20) 389 アハメド、クルマン、スネビリー[14]（推測）；クーリル[15]（検証済み）
w(2; 4,4) 35 クヴァタル[2]
w(2; 4,5) 55 クヴァタル[2]
w(2; 4,6) 73 ビーラーとオニール[3]
w(2; 4,7) 109 ビーラー[16]
w(2; 4,8) 146 クーリル[12]
w(2; 4,9) 309 アハメド[17]
w(2; 5,5) 178 スティーブンスとシャンタラム[5]
w(2; 5,6) 206 クーリル[12]
w(2; 5,7) 260 アハメド[18]
w(2; 6,6) 1132 クーリルとポール[7]
w(3; 2, 3, 3) 14 ブラウン[19]
w(3; 2, 3, 4) 21 ブラウン[19]
w(3; 2, 3, 5) 32 ブラウン[19]
w(3; 2, 3, 6) 40 ブラウン[19]
w(3; 2, 3, 7) 55 ランドマン、ロバートソン、カルバー[11]
w(3; 2, 3, 8) 72 クーリル[12]
w(3; 2, 3, 9) 90 アハメド[20]
w(3; 2, 3, 10) 108 アハメド[20]
w(3; 2, 3, 11) 129 アハメド[20]
w(3; 2, 3, 12) 150 アハメド[20]
w(3; 2, 3, 13) 171 アハメド[20]
w(3; 2, 3, 14) 202 クーリル[4]
w(3; 2, 4, 4) 40 ブラウン[19]
w(3; 2, 4, 5) 71 ブラウン[19]
w(3; 2, 4, 6) 83 ランドマン、ロバートソン、カルバー[11]
w(3; 2, 4, 7) 119 クーリル[12]
w(3; 2, 4, 8) 157 クーリル[4]
w(3; 2, 5, 5) 180 アハメド[20]
w(3; 2, 5, 6) 246 クーリル[4]
w(3; 3, 3, 3) 27 クヴァタル[2]
w(3; 3, 3, 4) 51 ビーラーとオニール[3]
w(3; 3, 3, 5) 80 ランドマン、ロバートソン、カルバー[11]
w(3; 3, 3, 6) 107 アハメド[17]
w(3; 3, 4, 4) 89 ランドマン、ロバートソン、カルバー[11]
w(3; 4, 4, 4) 293 クーリル[4]
w(4; 2, 2, 3, 3) 17 ブラウン[19]
w(4; 2, 2, 3, 4) 25 ブラウン[19]
w(4; 2, 2, 3, 5) 43 ブラウン[19]
w(4; 2, 2, 3, 6) 48 ランドマン、ロバートソン、カルバー[11]
w(4; 2, 2, 3, 7) 65 ランドマン、ロバートソン、カルバー[11]
w(4; 2, 2, 3, 8) 83 アハメド[20]
w(4; 2, 2, 3, 9) 99 アハメド[20]
w(4; 2, 2, 3, 10) 119 アハメド[20]
w(4; 2, 2, 3, 11) 141 シュバイツァー[21]
w(4; 2, 2, 3, 12) 163 クーリル[15]
w(4; 2, 2, 4, 4) 53 ブラウン[19]
w(4; 2, 2, 4, 5) 75 アハメド[20]
w(4; 2, 2, 4, 6) 93 アハメド[20]
w(4; 2, 2, 4, 7) 143 クーリル[4]
w(4; 2, 3, 3, 3) 40 ブラウン[19]
w(4; 2, 3, 3, 4) 60 ランドマン、ロバートソン、カルバー[11]
w(4; 2, 3, 3, 5) 86 アハメド[20]
w(4; 2, 3, 3, 6) 115 クーリル[15]
w(4; 3, 3, 3, 3) 76 ビーラーとオニール[3]
w(5; 2, 2, 2, 3, 3) 20 ランドマン、ロバートソン、カルバー[11]
w(5; 2, 2, 2, 3, 4) 29 アハメド[20]
w(5; 2, 2, 2, 3, 5) 44 アハメド[20]
w(5; 2, 2, 2, 3, 6) 56 アハメド[20]
w(5; 2, 2, 2, 3, 7) 72 アハメド[20]
w(5; 2, 2, 2, 3, 8) 88 アハメド[20]
w(5; 2, 2, 2, 3, 9) 107 クーリル[4]
w(5; 2, 2, 2, 4, 4) 54 アハメド[20]
w(5; 2, 2, 2, 4, 5) 79 アハメド[20]
w(5; 2, 2, 2, 4, 6) 101 クーリル[4]
w(5; 2, 2, 3, 3, 3) 41 ランドマン、ロバートソン、カルバー[11]
w(5; 2, 2, 3, 3, 4) 63 アハメド[20]
w(5; 2, 2, 3, 3, 5) 95 クーリル[15]
w(6; 2, 2, 2, 2, 3, 3) 21 アハメド[20]
w(6; 2, 2, 2, 2, 3, 4) 33 アハメド[20]
w(6; 2, 2, 2, 2, 3, 5) 50 アハメド[20]
w(6; 2, 2, 2, 2, 3, 6) 60 アハメド[20]
w(6; 2, 2, 2, 2, 4, 4) 56 アハメド[20]
w(6; 2, 2, 2, 3, 3, 3) 42 アハメド[20]
w(7; 2, 2, 2, 2, 2, 3, 3) 24 アハメド[20]
w(7; 2, 2, 2, 2, 2, 3, 4) 36 アハメド[20]
w(7; 2, 2, 2, 2, 2, 3, 5) 55 アハメド[17]
w(7; 2, 2, 2, 2, 2, 3, 6) 65 アハメド[18]
w(7; 2, 2, 2, 2, 2, 4, 4) 66 アハメド[18]
w(7; 2, 2, 2, 2, 3, 3, 3) 45 アハメド[18]
w(8; 2, 2, 2, 2, 2, 2, 3, 3) 25 アハメド[20]
w(8; 2, 2, 2, 2, 2, 2, 3, 4) 40 アハメド[17]
w(8; 2, 2, 2, 2, 2, 2, 3, 5) 61 アハメド[18]
w(8; 2, 2, 2, 2, 2, 2, 3, 6) 71 アハメド[18]
w(8; 2, 2, 2, 2, 2, 2, 4, 4) 67 アハメド[18]
w(8; 2, 2, 2, 2, 2, 3, 3, 3) 49 アハメド[18]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3) 28 アハメド[20]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 4) 42 アハメド[18]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 5) 65 アハメド[18]
w(9; 2, 2, 2, 2, 2, 2, 3, 3, 3) 52 アハメド[18]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 31 アハメド[18]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 45 アハメド[18]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5) 70 アハメド[18]
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 33 アハメド[18]
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 48 アハメド[18]
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 35 アハメド[18]
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 52 アハメド[18]
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 37 アハメド[18]
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 55 アハメド[18]
w(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 39 アハメド[18]
w(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]
w(21; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 52 カルキ[22]

ファンデルワールデン数は原始再帰的であり、シェラ[23]によって証明されている。実際、彼はファンデルワールデン数が（最大で）グジェゴルチク階層の第5レベルにあることを証明した。 E 5 {\displaystyle {\mathcal {E}}^{5}}

参照

参考文献

  1. ^ Rabung, John; Lotts, Mark (2012). 「ファン・デル・ワールデン数の下限値を求めるための巡回ジッパーの利用法の改善」Electron. J. Combin. 19 (2) P35. doi : 10.37236/2363 . MR  2928650.
  2. ^ abcdefghijk Chvátal, Vašek (1970). 「いくつかの未知のファン・デル・ワールデン数」. Guy, Richard; Hanani, Haim; Sauer, Norbert; et al. (eds.).組合せ構造とその応用. ニューヨーク: Gordon and Breach. pp.  31– 33. MR  0266891.
  3. ^ abcdefg Beeler, Michael D.; O'Neil, Patrick E. (1979). 「いくつかの新しいファンデルワールデン数」.離散数学. 28 (2): 135– 146. doi : 10.1016/0012-365x(79)90090-6 . MR  0546646.
  4. ^ abcdefgh Kouril, Michal (2012). 「ファン・デル・ヴェルデン数 W(3,4)=293 の計算」. Integers . 12 : A46. MR  3083419.
  5. ^ ab Stevens, Richard S.; Shantaram, R. (1978). 「コンピュータ生成のファンデルワールデン分割」.計算数学. 32 (142): 635– 636. doi : 10.1090/s0025-5718-1978-0491468-x . MR  0491468.
  6. ^ ab Heule, MarijnJ (2017). 「算術級数におけるトリプルの回避」(PDF) . Journal of Combinatorics . 8 (3): 391– 422. doi :10.4310/JOC.2017.v8.n3.a1.
  7. ^ ab Kouril, Michal; Paul, Jerome L. (2008). 「ファンデルワールデン数 W(2,6) は 1132 である」.実験数学. 17 (1): 53– 61. doi :10.1080/10586458.2008.10129025. MR  2410115. S2CID  1696473.
  8. ^ abcdefghijklmnopqr Monroe, Daniel (2019). 「分散コンピューティングを用いたファンデルワールデン数の新たな下限値」arXiv : 1603.03301 [math.CO].
  9. ^ Gowers, Timothy (2001). 「Szemerédiの定理の新たな証明」(PDF) . Geom. Funct. Anal. 11 (3): 465– 588. doi :10.1007/s00039-001-0332-9. MR  1844079. S2CID  124324198.
  10. ^ Berlekamp, E. (1968). 「長い算術級数を避けるための分割の構築」. Canadian Mathematical Bulletin . 11 (3): 409– 414. doi : 10.4153/CMB-1968-047-7 . MR  0232743.
  11. ^ abcdefghijkl ランドマン、ブルース;ロバートソン、アーロン。カルバー、クレイ (2005)。 「いくつかの新しい正確なファン デル ワールデン数」(PDF)。整数。５（２）：Ａ１０．arXiv : math/0507019。Bibcode :2005math....7019L。MR  2192088。
  12. ^ abcdefg Kouril, Michal (2006). Beowulfクラスターのためのバックトラッキングフレームワーク、マルチクラスター計算への拡張、およびSatベンチマーク問題の実装（博士論文）. シンシナティ大学.
  13. ^ ab Ahmed, Tanbir (2010). 「2つの新しいファンデルワールデン数 w(2;3,17) と w(2;3,18)」. Integers . 10 (4): 369– 377. doi :10.1515/integ.2010.032. MR  2684128. S2CID  124272560.
  14. ^ ab Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter (2014). 「ファン・デル・ヴェルデン数 w(2;3,t) について」.離散応用数学. 174 (2014): 27– 51. arXiv : 1102.5433 . doi : 10.1016/j.dam.2014.05.007 . MR  3215454.
  15. ^ abcd Kouril, Michal (2015). 「SAT計算におけるFPGAクラスターの活用」『並列コンピューティング：エクサスケールへの道』525–532ページ。
  16. ^ Beeler, Michael D. (1983). 「新しいファン・デル・ワールデン数」.離散応用数学. 6 (2): 207. doi : 10.1016/0166-218x(83)90073-2 . MR  0707027.
  17. ^ abcd Ahmed, Tanbir (2012). 「正確なファンデルワールデン数の計算について」. Integers . 12 (3): 417– 425. doi :10.1515/integ.2011.112. MR  2955523. S2CID  11811448.
  18. ^ abcdefghijklmnopqrstu vwxyz aa Ahmed, Tanbir (2013). 「Some More Van der Waerden numbers」. Journal of Integer Sequences . 16 (4): 13.4.4. MR  3056628.
  19. ^ abcdefghijk Brown, TC (1974). 「いくつかの新しいファン・デル・ワールデン数（予備報告）」.アメリカ数学会報21 : A-432.
  20. ^ abcdefghijklmnopqrstu vwxyz aa ab ac ad Ahmed, Tanbir (2009). 「いくつかの新しいファンデルワールデン数といくつかのファンデルワールデン型数」. Integers . 9 : A6. doi :10.1515/integ.2009.007. MR  2506138. S2CID  122129059.
  21. ^ Schweitzer, Pascal (2009).未知の計算量の問題、グラフ同型性、およびラムゼー理論的数（博士論文）. ザールランド大学.
  22. ^ カルキ、シキジ (2024). 「新しいファンデルワールデン番号」(PDF)。U(t)-マサジン(9): 34–39 .
  23. ^ Shelah, Saharon (1988). 「ファン・デル・ワールデン数の原始的再帰的境界」アメリカ数学会誌. 1 (3): 683– 697. doi : 10.2307/1990952 . JSTOR  1990952. MR  0929498.

さらに読む

  • ランドマン、ブルース・M.；ロバートソン、アーロン (2014).ラムゼーの整数理論. 学生数学図書館. 第73巻（第2版）. プロビデンス、ロードアイランド州：アメリカ数学会. doi :10.1090/stml/073. ISBN 978-0-8218-9867-3MR  3243507 。
  • Herwig, PR; Heule, MJH; van Lambalgen, PM; van Maaren, H. (2007). 「ファン・デル・ヴェルデン数の下限値を構成する新しい手法」. The Electronic Journal of Combinatorics . 14 (1) R6. doi : 10.37236/925 . MR  2285810.
「https://en.wikipedia.org/w/index.php?title=Van_der_Waerden_number&oldid=1317234263」より取得