Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: A 2-COLORING OF [1, N ] CAN HAVE (1/22)N 2 + O(N ) MONOCHROMATIC SCHUR TRIPLES, BUT NOT LESS! | A 2-COLORING OF 1 N CAN HAVE 1 22 N2 O N MONOCHROMATIC SCHUR TRIPLES BUT NOT LESS Aaron Robertson and Doron Zeilberger1 Department of Mathematics Temple University Philadelphia PA 19122 USA aaron@ zeilberg@ Submitted March 3 1998 Accepted March 25 1998 Abstract We prove the statement of the title THEREBy SOLVING A 100 PROBLEM OF Ron Graham. This was solved iNDEPENDENTLy By Tomasz Schoen. Tianjin June 29 1996 In a fascinating invited talk at the SOCA 96 combinatorics conference organized by Bill Chen Ron Graham proposed see also GRR p. 390 Problem 100 Find asymptotically the least number of monochromatic Schur triples i j i jg that may occur in a 2-coloring of the integers 1 2 . n. By naming the two colors 0 and 1 the above is equivalent to the following Discrete Calculus Problem Find the minimal value of F xi . Xn 2 xixjXi j 1 - Xi 1 - Xj 1 - Xi j 1 i j n i j n over the n-dimensional discrete unit cube x1 . xn xi 0 1g. We will determine all local minima with respect to the Hamming metric then determine the global minimum. Partial Derivatives For any function f x1 . xn on 0 1gn define the discrete partial derivatives dr f by dr f xi . . . xr . . . xn f xi . . . xr . . . xn - f xi . . . 1 - xr . . . xn . If z1 . zn is a local minimum of F then we have the n inequalities dr F zi . Zn 0 1 r n. A purely routine calculation shows that below y S is 1 0 if S is true false drF xi . xn n n-r I Vxi v xi - n- Ỉ - x r 77 - 2xr -1 xrx r 77 1 - x2 x2r y r 77 L2J 2 2 2 2 i 1 i 1 1 Since we are only interested in the asymptotic behavior we can modify F by any amount that is O n . In particular we can replace F x1 . xn by G xi . . . xn F xi . . . xn xi x2i - 1 - 2 2 xi i 1 z i 1 1 Supported in part by the NSF. Mathematics Classification Numbers Primary 05D10 05A16 Secondary 04A20 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 5 1998 R19 2 Noting that 2xr 1 2 1 and 2xr 1 xr xr on 0 1gn we see that for 1 r n n n-r 1 52 Xi 52 Xi n _2 J 2 ỵ r n 2 i 1 i 1 2 x r n
