Office: Room: EV011.139, Concordia University, 1515 Ste. Catherine St. West, Montreal, QC H3G 1M8 Phone: (514) 848-2424 Ext: 7199 Email: ta_ahmed AT cs DOT concordia DOT ca Supervisor: Prof. Clement Lam [HOMEPAGE]
According to van der Waerden's theorem: Given any positive integer r and positive integers k_1, k_2, ..., k_r, there is an integer m such that given any partition {1,2,...,m}=P_1 U P_2 U ... U P_r, there is always a class P_j containing an arithmetic progression of length k_j. Let us denote the least m with this property by w(r; k_1, k_2, ..., k_r). Van der Waerden numbers known so far:
w(r; k_1, k_2, ..., k_r)	=	Reference
w(2; 3, 3)	= 9	Chvátal [5]
w(2; 3, 4)	= 18	Chvátal [5]
w(2; 3, 5)	= 22	Chvátal [5]
w(2; 3, 6)	= 32	Chvátal [5]
w(2; 3, 7)	= 46	Chvátal [5]
w(2; 3, 8)	= 58	Beeler and O'Neil [3]
w(2; 3, 9)	= 77	Beeler and O'Neil [3]
w(2; 3, 10)	= 97	Beeler and O'Neil [3]
w(2; 3, 11)	= 114	Landman, Robertson and Culver [8]
w(2; 3, 12)	= 135	Landman, Robertson and Culver [8]
w(2; 3, 13)	= 160	Landman, Robertson and Culver [8]
w(2; 3, 14)	= 186	Kouril [6]
w(2; 3, 15)	= 218	Kouril [6]
w(2; 3, 16)	= 238	Kouril [6]
w(2; 3, 17)	= 279	Ahmed [1a]
w(2; 3, 18)	= 312	Ahmed [1a]
w(2; 3, 19)	= 349	Ahmed, Kullmann and Snevily [1d]
w(2; 4, 4)	= 35	Chvátal [5]
w(2; 4, 5)	= 55	Chvátal [5]
w(2; 4, 6)	= 73	Beeler and O'Neil [3]
w(2; 4, 7)	= 109	Beeler [2]
w(2; 4, 8)	= 146	Kouril [6]
w(2; 4, 9)	= 309	Ahmed [1b]
w(2; 5, 5)	= 178	Stevens and Shantaram [10]
w(2; 5, 6)	= 206	Kouril [6]
w(2; 5, 7)	= 260	Ahmed (Dec. 2011) (Double Checking...)
w(2; 5, 8)	>= 331	Ahmed [1c]
w(2; 5, 9)	>= 473	Ahmed [1c]
w(2; 5, 10)	> 557	Ahmed [1c]
w(2; 5, 11)	> 736	Ahmed [1c]
w(2; 6, 6)	= 1132	Kouril and Paul [7]
w(3; 2, 3, 3)	= 14	Brown [4]
w(3; 2, 3, 4)	= 21	Brown [4]
w(3; 2, 3, 5)	= 32	Brown [4]
w(3; 2, 3, 6)	= 40	Brown [4]
w(3; 2, 3, 7)	= 55	Landman, Robertson and Culver [8]
w(3; 2, 3, 8)	= 72	Kouril [6]
w(3; 2, 3, 9)	= 90	Ahmed [1]
w(3; 2, 3, 10)	= 108	Ahmed [1]
w(3; 2, 3, 11)	= 129	Ahmed [1]
w(3; 2, 3, 12)	= 150	Ahmed [1]
w(3; 2, 3, 13)	= 171	Ahmed [1]
w(3; 2, 3, 14)	= 202	Schweitzer [9]
w(3; 2, 4, 4)	= 40	Brown [4]
w(3; 2, 4, 5)	= 71	Brown [4]
w(3; 2, 4, 6)	= 83	Landman, Robertson and Culver [8]
w(3; 2, 4, 7)	= 119	Kouril [6]
w(3; 2, 4, 8)	> 155	Ahmed [1c]
w(3; 2, 5, 5)	= 180	Ahmed [1]
w(3; 3, 3, 3)	= 27	Chvátal [5]
w(3; 3, 3, 4)	= 51	Beeler and O'Neil [3]
w(3; 3, 3, 5)	= 80	Landman, Robertson and Culver [8]
w(3; 3, 3, 6)	= 107	Ahmed [1b]
w(3; 3, 3, 7)	> 149	Ahmed [1c]
w(3; 3, 3, 8)	> 185	Ahmed [1c]
w(3; 3, 3, 9)	> 221	Ahmed [1c]
w(3; 3, 3, 10)	> 265	Ahmed [1c]
w(3; 3, 4, 4)	= 89	Landman, Robertson and Culver [8]
w(3; 3, 4, 5)	> 163	Ahmed [1c]
w(3; 3, 5, 5)	> 243	Ahmed [1c]
w(4; 2, 2, 3, 3)	= 17	Brown [4]
w(4; 2, 2, 3, 4)	= 25	Brown [4]
w(4; 2, 2, 3, 5)	= 43	Brown [4]
w(4; 2, 2, 3, 6)	= 48	Landman, Robertson and Culver [8]
w(4; 2, 2, 3, 7)	= 65	Landman, Robertson and Culver [8]
w(4; 2, 2, 3, 8)	= 83	Ahmed [1]
w(4; 2, 2, 3, 9)	= 99	Ahmed [1]
w(4; 2, 2, 3, 10)	= 119	Ahmed [1]
w(4; 2, 2, 3, 11)	= 141	Schweitzer [9]
w(4; 2, 2, 4, 4)	= 53	Brown [4]
w(4; 2, 2, 4, 5)	= 75	Ahmed [1]
w(4; 2, 2, 4, 6)	= 93	Ahmed [1]
w(4; 2, 3, 3, 3)	= 40	Brown [4]
w(4; 2, 3, 3, 4)	= 60	Landman, Robertson and Culver [8]
w(4; 2, 3, 3, 5)	= 86	Ahmed [1]
w(4; 3, 3, 3, 3)	= 76	Beeler and O'Neil [3]
w(5; 2, 2, 2, 3, 3)	= 20	Landman, Robertson and Culver [8]
w(5; 2, 2, 2, 3, 4)	= 29	Ahmed [1]
w(5; 2, 2, 2, 3, 5)	= 44	Ahmed [1]
w(5; 2, 2, 2, 3, 6)	= 56	Ahmed [1]
w(5; 2, 2, 2, 3, 7)	= 72	Ahmed [1]
w(5; 2, 2, 2, 3, 8)	= 88	Ahmed [1]
w(5; 2, 2, 2, 4, 4)	= 54	Ahmed [1]
w(5; 2, 2, 2, 4, 5)	= 79	Ahmed [1]
w(5; 2, 2, 3, 3, 3)	= 41	Landman, Robertson and Culver [8]
w(5; 2, 2, 3, 3, 4)	= 63	Ahmed [1]
w(6; 2, 2, 2, 2, 3, 3)	= 21	Ahmed [1]
w(6; 2, 2, 2, 2, 3, 4)	= 33	Ahmed [1]
w(6; 2, 2, 2, 2, 3, 5)	= 50	Ahmed [1]
w(6; 2, 2, 2, 2, 3, 6)	= 60	Ahmed [1]
w(6; 2, 2, 2, 2, 4, 4)	= 56	Ahmed [1]
w(6; 2, 2, 2, 3, 3, 3)	= 42	Ahmed [1]
w(7; 2, 2, 2, 2, 2, 3, 3)	= 24	Ahmed [1]
w(7; 2, 2, 2, 2, 2, 3, 4)	= 36	Ahmed [1]
w(7; 2, 2, 2, 2, 2, 3, 5)	= 55	Ahmed [1b]
w(8; 2, 2, 2, 2, 2, 2, 3, 3)	= 25	Ahmed [1]
w(8; 2, 2, 2, 2, 2, 2, 3, 4)	= 40	Ahmed [1b]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3)	= 28	Ahmed [1]
[1] Ahmed T., Some new van der Waerden numbers and some van der Waerden-type numbers, INTEGERS: Electronic journal of Combinatorial Number Theory 9 (2009), A06, pp 65-76. [1a] Ahmed T., Two new van der Waerden numbers: w(2; 3, 17) and w(2; 3, 18), INTEGERS: Electronic journal of Combinatorial Number Theory 10 (2010), A32, pp 369-377. [1b] Ahmed T., On computation of exact van der Waerden numbers, INTEGERS: Electronic journal of Combinatorial Number Theory 11 (2011), A71. [1c] Ahmed T., Some new lower bounds of van der Waerden numbers [.pdf] [1d] Tanbir Ahmed, Oliver Kullmann, and Hunter Snevily, On the van der Waerden numbers w(2; 3, t), submitted. (arXiv:1102.5433v1 [math.CO]) [2] Beeler M., A new van der Waerden number, Discrete Applied Math. 6 (1983), 207. [3] Beeler M., O'Neil P., Some new van der Waerden numbers, Discrete Math. 28 (1979), 135-146 [4] Brown T. C., Some new van der Waerden numbers (preliminary report), Notices American Math. Society 21 (1974), A-432. [5] Chvátal V., Some unknown van der Waerden numbers, Combinatorial Structures and Their Applications (R.Guy et al.,eds.), Gordon and Breach, New York, (1970) [6] Kouril M., A Backtracking Framework for Beowulf Clusters with an Extension to Multi-Cluster Computation and Sat Benchmark Problem Implementation, Ph. D. Thesis, University of Cincinnati, Engineering : Computer Science and Engineering, 2006. [7] Kouril M., Paul J.L., The Van der Waerden Number W(2,6) is 1132, Experimental Mathematics [8] Landman B., Robertson A., Culver C., Some New Exact van der Waerden Numbers, Integers 5 (2005) 2 [9] Schweitzer P., Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers, Dissertation zur Erlangung des Grades des Doktors der Naturwissenschaften (Dr. rer. nat.), U. des Saarlandes, 2009. PDF [10] Stevens R., Shantaram R., Computer-generated van der Waerden partitions, Math. Computation 32 (1978), 635-636. Some van der Waerden type numbers. Return to HOMEPAGE.