Mathematics desk | ||
---|---|---|
< May 10 | << Apr | May | Jun >> | May 12 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
I'm revising a few past papers on Ramsey theory and I've come across a question which I can do about half of, and was hoping someone could help get me the rest of the way. The question is as follows:
Let m be a positive integer. Show that, whenever the edges of are red-blue coloured, there exists either
(i) an m-term arithmetic progression M with all edges of M blue, or
(ii) disjoint m-term arithmetic progressions A and B with every edge from A to B red.
[Hint: Suppose that every m-term arithmetic progression has at least one of its edges red. This gives a colouring of N2 with colours, by colouring according to which edge of the arithmetic progression with first term a and common difference d is red, where represents the edge-set of . Now apply Gallai’s theorem.]
Firstly for anyone who isn't aware, Gallai's theorem states that whenever is finitely coloured (any d), then for any finite S there exists a monochromatic homothetic copy of S, meaning a monochromatic for some . So the question seems to want me to pick some S in for which a homothetic copy will correspond to a monochromatic arithmetic progression.
So I've tried to follow the hint, picking some "sensible set" S in , and then use that to get a pair of APs with all edges between them red. Suppose we take a horizontal line of m points for S: then Gallai's theorem states we can find a monochromatic horizontal sequence of m points in spaced at apart, where "monochromatic" here means that the arithmetic progression to which each point corresponds has its red edge between the same points in the AP, say the i-th and j-th points. (I am picturing this as m copies of overlaid to give, for each point, the corresponding AP going "down into the page".)
So then if we now consider new APs, corresponding to the horizontal sequences of points which Gallai produced, spaced apart and in the i-th and j-th copies of , then we now have 2 APs for which there is a red edge going between every corresponding term in the sequence: a red edge between the first terms in the 2 sequences, a red edge between the second terms and so on. We can also ensure that we get disjoint APs as required by the question: instead of taking a horizontal line for Gallai's theorem, take a stack of lots of these lines on top of each other (so essentially a rectangle). Then by the time we get to the top of the rectangle produced by Gallai, the common differences will be enormous and there will be no way the start of one AP can overlap the end of another. So that solves that issue.
Obviously my remaining problem is that the questions wants all edges between the 2 APs red: that is, all edges, rather than just the m edges between corresponding terms in the APs. I have tried all the ways I can think of to fix this problem, such as applying Gallai to a much larger set so that once we get a mono copy of it, we can take a smaller set which is still very large inside it, and maybe reapply Gallai or something like that. However, this doesn't work: once we have started down the road I suggested above, you have chosen your APs and all you can really do is make them as long as you want: I can't see a way to finish the problem, given that the colouring suggested only induces red edges between a small number of the vertices in each AP, not all of them. This problem is meant to be doable in half an hour at most, so I'm not sure if I'm doing the right thing and missing something, or I've misunderstood the hint in the question. Your help would be greatly appreciated - Staytime101 (talk) 11:49, 11 May 2012 (UTC)
I'm trying to calculate the coordinates (x,y) of evenly spaced points around a circle. Googling "points on a circle" I found these equations:
I've tried working out what I'm supposed to do with these but haven't got anywhere. Could someone please work though an example calculation so I can see what I need to do? If possible, use r=500 and theta=0.261 (the circle split into 24). Cheers SmartSE (talk) 23:18, 11 May 2012 (UTC)
The root of unity is the coordinates of evenly spaced points around a circle. Bo Jacoby (talk) 05:18, 12 May 2012 (UTC).