From: Robin Chapman Subject: Re: Ramsey and computational complexity theory Date: Mon, 19 Jan 1998 10:01:13 -0600 Newsgroups: sci.math,comp.theory In article <34BFE9C6.15D5@wxs.nl>, P_R_van_Emburg@wxs.nl wrote: > > Could someone tell me if there exists literature in which Ramsey theory > and computational complexity theory are discussed in connection with > each other? I want to solve what may be called a celebrity variant of > the birthday party problem in which three relations are possible instead > of just two (in other words, I want to know how to computer Ramsey > number R_3,3,3). Thanks for any info! This is one of the few Ramsey numbers which is known exactly. SPOILER ALERT! This Ramsey number is exactly 17. If we have a 3-colouring of the edges of the complete graph on 17 vertices, pick any vertex v. There is a colour, blue say, with at least 6 edges of that colour issuing from v. Take 6 vertices attached to v via blue edges. If any edge joining them is blue then we have a blue triangle. Otherwise these 6 vertices are joined by only red and green edges, and by the usual argument there's a red or green triangle. I need an example to show that 16 doesn't suffice. Label 16 vertices with the elements of the finite field F_16. If a and b are distinct vertices then (a-b)^5 is a cube root of unity in F_16. Colour the edge from a to b red, blue or green according to which cube root of unity it is. Then one can show this graph has no monochrome triangles. Robin Chapman "256 256 256. Department of Mathematics O hel, ol rite; 256; whot's University of Exeter, EX4 4QE, UK 12 tyms 256? Bugird if I no. rjc@maths.exeter.ac.uk 2 dificult 2 work out." http://www.maths.ex.ac.uk/~rjc/rjc.html Iain M. Banks - Feersum Endjinn -------------------==== Posted via Deja News ====----------------------- http://www.dejanews.com/ Search, Read, Post to Usenet