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: The Rectilinear Crossing Number of K10 is 62. | The Rectilinear Crossing Number of K10 is 62 Alex Brodsky Stephane Durocher Ellen Gethner Department of Computer Science University of British Columbia Canada abrodsky durocher egethner @ Submitted August 9 2000 Accepted April 9 2001. MR Subject Classifications 05C10 52C35 Oh what a tangled web we weave. Sir Walter Scott Abstract The rectilinear crossing number of a graph G is the minimum number of edge crossings that can occur in any drawing of G in which the edges are straight line segments and no three vertices are collinear. This number has been known for G Kn if n 9. Using a combinatorial argument we show that for n 10 the number is 62. 1 Introduction and History Mathematicians and Computer Scientists are well acquainted with the vast sea of crossing number problems whose 1944 origin lies in a scene described by Paul Turan. The following excerpt taken from Guy69 has appeared numerous times in the literature over the years and is now known as Turan s brick factory problem. sic. In 1944 our labor cambattation had the extreme luck to work thanks to some very rich comrades in a brick factory near Budapest. Our work was to bring out bricks from the ovens where they were made and carry them on small vehicles which run on rails in some of several open stores which happened to be empty. Since one could never be sure which store will be available each oven was connected by rail with each store. Since we had to settle a fixed amount of loaded cars daily it was our interest to finish it as soon as possible. After being loaded in the rather warm ovens the vehicles run smoothly with not much effort the only trouble arose at Supported by NSERC PGSB THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R23 1 the crossing of two rails. Here the cars jumped out the bricks fell down a lot of extra work and loss of time arose. Having this experience a number of times it occurred to me why on earth did they build the rail system so uneconomically minimizing the number of .