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.

May 11

Ramsey theory

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 $\mathbb {N}$ 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 $m \choose 2$ edges red. This gives a colouring of N2 with $m \choose 2$ colours, by colouring $(a,d)\in \mathbb {N} ^{(2)}$ according to which edge of the arithmetic progression with first term a and common difference d is red, where $\mathbb {N} ^{(2)}$ represents the edge-set of $\mathbb {N}$ . Now apply Gallai’s theorem.]

Firstly for anyone who isn't aware, Gallai's theorem states that whenever $\mathbb {N} ^{d}$ is finitely coloured (any d), then for any finite S $\subset \mathbb {N} ^{d}$ there exists a monochromatic homothetic copy of S, meaning a monochromatic $x_{0}+\lambda S$ for some $\lambda$ . So the question seems to want me to pick some S in $\mathbb {N} ^{d}$ 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 $\mathbb {N} ^{2}$ , 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 $\mathbb {N} ^{2}$ spaced at $\lambda$ 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 $\mathbb {N} ^{2}$ 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 $\lambda$ apart and in the i-th and j-th copies of $\mathbb {N} ^{2}$ , 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 $m^{2}$ 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)[reply]

~~Think about what it implies if (a, d) is colored by (i, j) in the coloring given in the hint. It means that the original coloring has (a + id, a + jd) red.~~

Use Gallai's theorem to find two long enough arithmetic sequences with the same difference and with each pairwise edge colored the same in the new coloring, say we have all edges (A + Cx, B + Cy) colored (i, j) for a large enough range of integers x, y.

~~From what we said about the new coloring, this means that edge~~

~~(A + iB + C(x + iy), A + jB + C (x + jy))~~

~~is red in the new coloring for all x and y in range. We want some of these edges to share their endpoints. The trick is to manipulate the terms so some of them cancel out.~~

~~Choose x := -iy + u(i - j); and y := v-u.~~

~~Here u and v will take values in a small range, say all integers up to O(m). Then x and y are integers that are still small, say O(m^2). Calculate what the edge becomes after this substitution.~~

PS. Kudos for the good question: well communicated and demonstrates that you tried to work on it before asking.

– b_jonas 18:28, 13 May 2012 (UTC)[reply]

Update: the above doesn't work as is, and I'm not sure yet whether it can be fixed. Sorry. – b_jonas 07:17, 14 May 2012 (UTC)[reply]

Coordinates of points on a circle

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:

(x?,y?)=(x+dcosα,y+dsinα) [1]
A point at angle theta on the circle whose centre is (x0,y0) and whose radius is r is (x0 + r cos theta, y0 + r sin theta). Now choose theta values evenly spaced between 0 and 2pi. [2]

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)[reply]

It's more usual to measure the angle counterclockwise from the rightward pointing ray from the center point. I suspect that your source intended theta to be measured that way, rather than the way you drew it. Then the point at angle theta is x = x₀ + r×cos(theta), y = y₀ + r×sin(theta). So if r=500 and theta=0.261 = 2×pi/24 = 360°/24 = 15°, then x = x₀ + 500×cos(15°) = x₀ + 482.9629, and y = y₀ + 500×sin(15°) = y₀ + 129.4095. Duoduoduo (talk) 02:55, 12 May 2012 (UTC)[reply]

Ah awesome! Just what I needed. SmartSE (talk) 10:18, 12 May 2012 (UTC)[reply]

And to back up a bit and describe the process, you want to find each point by varying theta in polar coordinates, then convert those into rectangular coordinates. This is what those formulae do. StuRat (talk) 03:07, 12 May 2012 (UTC)[reply]

The root of unity is the coordinates of evenly spaced points around a circle. Bo Jacoby (talk) 05:18, 12 May 2012 (UTC).[reply]

I wonder, though, whether the OP really wanted to know about √(-1). —Tamfang (talk) 07:00, 12 May 2012 (UTC)[reply]

I don't know that either, but it is worth while learning! Bo Jacoby (talk) 08:59, 12 May 2012 (UTC). [reply]

That looks interesting, but I don't really have any clue what it means! Thanks though. SmartSE (talk) 10:18, 12 May 2012 (UTC)[reply]

It certainly is interesting! Is there anything in particular you don't understand about it? Widener (talk) 10:22, 12 May 2012 (UTC)[reply]

I don't even understand the first sentence of the lead, so there's not much hope! SmartSE (talk) 13:15, 12 May 2012 (UTC)[reply]

Don't give up hope. Consider the coordinates to a point in the plane: a = (a₁,a₂). Then a can be written a = a₁(1,0)+a₂(0,1). The point (1,0) is called 1 and the point (0,1) is called i for convenience. So a = a₁+ia₂. With this notation the point is called a complex number. It is a bad name for two reasons: first, it is not complex, second, it is not a number. But it is probably too late to change the name - mathematicians are not adaptable regarding names. If the triangle (0,a,b) is congruent to the triangle (c,b,a), then a+b=c. If the triangle (1,0,a) is similar to the triangle (b,0,c) then c/a=b/1 and so ab=c. Note that the triangle (1,0,i) is similar to the triangle (i,0,−1), so i²=−1. Now the geometric problem of dividing the unit circle into N equal arcs can be translated into algebra. The N points of division are 1,x,x²,...,x^N−1 because the N triangles (1,0,x), (x,0,x²), ... , (x^N−1,0,1) are all similar. So the problem is reduced to solving the equation x^N = 1. The N solutions are called N^th roots of unity. Bo Jacoby (talk) 06:57, 13 May 2012 (UTC).[reply]