This seminar by mark-t took place on 14th December 2008 15:00 UTC, in #mathematics channel of irc.freenode.net.

The timestamps displayed in the IRC text are UTC-4.

Any explanation or errors regarding this seminar should be recorded in the discussion page.

## Seminar Edit

[11:09] <_llll_> i suggest you start when ready mark-t [11:09] <mark-t> combinatorics [11:10] * ChanServ changes topic to 'Seminar in progress, if you want to speak, say ! and wait to be called.' [11:10] <mark-t> all righty then [11:12] <mark-t> so, ramsey theory is all about showing that sufficiently large mathematical objects have a given structure [11:12] <mark-t> since I've never really studied it in detail, I'll just give a few well-known results in the area [11:13] <mark-t> first of all, consider this problem: in any group of six people, show that there is either a set of three people who all know each other, or a set of three people who are complete strangers [11:14] <mark-t> use the obvious assumptions: if person A knows person B, then person B knows person A, and two people are either strangers or they know each other [11:15] <mark-t> this is a pretty common problem; you've probably come across it in #math, even if you don't know any ramsey theory [11:15] <mark-t> I'll omit the proof for the time being, in case you want to think about it [11:17] <mark-t> now, here's one way of rewording this problem: given K_6, the complete graph on 6 vertices, and an assignment of one of two colors to each edge in the graph, show that there are 3 vertices such that the edges between them are all the same color [11:20] <mark-t> it turns out that this problem is answered directly by Ramsey's theorem, which is what ramsey theory is named after; Ramsey's theorem is as follows: [11:22] <mark-t> given j colors, we'll call them c_1, c_2, ..., c_j, and j positive integers, we'll call them n_1, n_2, ..., n_j, then for sufficiently large n, any way you could color the vertices of K_n with colors c_1, ..., c_j will have at least one subgraph with n_i vertices, all of whose edges are color c_i, for some i [11:23] <mark-t> the smallest such n is called a Ramsey number, and it is denoted by R(n_1, n_2, ..., n_j) [11:24] <mark-t> for our example problem, we wish to show that R(3,3) <= 6 [11:25] <mark-t> it should be obvious that R(1,k) = R(k,1) = 1 and R(2,k) = R(k,2) = k for any k > 0 [11:25] <mark-t> we'll prove Ramsey's theorem by induction on n_1 + n_2 + ... + n_j [11:26] <maxote> ! [11:26] <mark-t> yes? [11:26] <maxote> why =k is k is not smallest? [11:27] <mark-t> for R(2,k)? [11:27] <maxote> yes [11:27] <mark-t> well, if you have less than k vertices, then all of the edges can be colored with c_2, which fails to have a set of two vertices colored with c_1 or a set of k vertices colored with c_2 [11:29] <mark-t> is that clear? [11:29] <maxote> can be k=3? [11:29] <mark-t> yes [11:29] <maxote> so, R(2,3)=R(3,2)=3? [11:30] <mark-t> so R(2,3) = 3 says that any coloring of K_3's edges will either have a set of two vertices such that all the edges between them are color c_1, or a set of 3 vertices such that all the edges between them are color c_2, and that this isn't true for K_2 [11:30] <mark-t> yes [11:31] <maxote> and why not =2? [11:31] <mark-t> because K_2 has one edge, which you can color with c_2 [11:32] <mark-t> that graph will not have two vertices connected by a c_1 edge, and it will not have three vertices connected by c_2 edges [11:33] <maxote> ok [11:33] <mark-t> so, I claim that R(n_1, n_2, ..., n_j) <= R(n_1 - 1, n_2, ..., n_j) + R(n_1, n_2 - 1, ..., n_j) + ... + R(n_1, n_2, ..., n_j - 1) [11:34] <mark-t> each term has 1 subtracted from exactly one of the n_i terms [11:35] <mark-t> let the RHS of that inequality be n, and consider any coloring of K_n's edges [11:36] <mark-t> pick any vertex in K_n, let's call it v, and split the remaining vertices of K_n into j sets A_1, A_2, ..., A_j, where the elements of A_i are the vertices connected to v by an edge with color c_i [11:39] <mark-t> now, since n = 1 + |A_1| + |A_2| + ... + |A_j| = R(n_1 - 1, ...) + R(n_1, n_2 - 1, ...) + ... + R(..., n_j - 1), it follows that R(..., n_i - 1, ...) >= |A_i| for at least one i [11:40] <mark-t> for if R(..., n_i - 1, ...) < |A_i| for all i, then the RHS would be <= |A_1| + |A_2| + ... + |A_j| - j, which can't be 1 + |A_1| + ... + |A_j| [11:41] <maxote> ! [11:41] <mark-t> yes? [11:41] <maxote> are there (n-1) * n / 2 edges? [11:41] <mark-t> yes [11:42] <mark-t> so, look at one of these A_i where R(..., n_i - 1, ...) >= |A_i|; then, either A_i contains n_j vertices connected by edges of color c_j for j != i, or it contains n_i - 1 vertices connected by edges of color c_i [11:43] <maxote> ! [11:43] <mark-t> in the former case, we're done; in the latter case, those n_i - 1 vertices along with the vertex v form a set of n_i vertices connected by edges of color c_i, as desired; so we're done [11:43] <mark-t> yes? [11:43] <maxote> is sum{i} n_i = (n-1)*n/2 ? [11:43] <mark-t> no [11:45] <mark-t> so, this proof gives an upper bound for R(n_1, n_2, ..., n_j); it's actually a considerable over-estimate, but that doesn't matter; it's just an existence proof [11:47] <mark-t> now, if we use our fact that R(2,3) = R(3,2) = 3, our proof told us that R(3,3) <= R(2,3) + R(3,2) = 6, so that proves the initial question as well [11:48] <mark-t> now I'd like to share a proof for a lower bound of Ramsey numbers [11:48] <maxote> ! [11:48] <mark-t> I'm only going to present it for the R(k,k) case, but it can easily be generalized; this result is due to Erdos [11:48] <mark-t> yes? [11:49] <maxote> can be the parameters of R rotated? [11:49] <mark-t> yes [11:49] <maxote> ! [11:49] <mark-t> yes? [11:50] <maxote> if R has M parameters then there is M! Ramseys that are the same? [11:50] <mark-t> assuming the parameters are different [11:50] <maxote> yes, assuming, of course. [11:51] <mark-t> it doesn't matter what order you list the numbers; there's nothing special about c_i and c_j that makes them somehow different [11:53] <mark-t> so, the idea for this proof is that we compute the expected number of single-color subgraphs of size k for a given n; if the expected number is less than 1, then there must be some coloring that has no single-color k-subgraphs, which means R(k,k) > n [11:56] <mark-t> for any choice of k vertices, the edges between them will be the same color in 2*2^{C(n,2)-C(k,2)} different colorings of K_n -- 2 is because there are two choices for what that same color will be, and 2^{C(n,2)-C(k,2)} is how many ways to color the remaining edges [11:56] <maxote> ! [11:56] <mark-t> yes? [11:56] <maxote> can exist non-colored edges? [11:56] <mark-t> no [11:58] <maxote> ! [11:58] <mark-t> now, since there are C(n,k) different sets of k vertices, there are a total of C(n,k) * 2 * 2^{C(n,2)-C(k,2)} single-color k-subgraphs in all the colorings of K_n, and there are 2^{C(n,2)} total colorings of K_n [11:58] <mark-t> yes? [11:58] <maxote> can be represented this graph by an upper triangular matrix modulo m-colors? [11:58] <mark-t> yes [12:00] <maxote> ! [12:00] <mark-t> the expected value is just the ratio between the two, so we want to know when C(n,k) * 2 * 2^{-C(k,2)} < 1 [12:00] <mark-t> yes? [12:00] <maxote> the total of combinations is m^{(n-1) * n / 2} ? [12:00] <mark-t> yes [12:00] <maxote> lol, continue [12:01] <mark-t> I don't want to bore you with algebra, but if you use some approximations, you can show that this means n > k/e * 2^{(k-1)/2} [12:02] <mark-t> er, n is less than that, R(k,k) is greater [12:04] <mark-t> of course, this proof isn't constructive; it just tells us that there has to be some coloring of K_n with no single-color k-subgraphs [12:04] <mark-t> constructive results are actually quite a bit behind this result [12:05] <mark-t> ok, so that's enough of ramsey numbers [12:05] <mark-t> here's another well-known result from ramsey theory, called Van der Waerden's theorem [12:07] <maxote> ! [12:07] <mark-t> if you assign every positive integer one of j colors, for any k and sufficiently large n, there will be an arithmetic sequence of integers of length k, each one smaller than n, that all have the same color [12:07] <mark-t> yes? [12:07] <maxote> inmho, i think that it can be better elaborated with algebra and prime numbers as colors, and some new operations [12:08] <mark-t> oh [12:08] <maxote> so, you can count the numbers of each prime, etc. [12:09] <maxote> that the primes don't divide each other [12:09] <mark-t> so, I'll give a quick proof for the case of two colors and an arithmetic sequence of length 3, then I'll describe how you can extend it to get the full theorem [12:12] <mark-t> look at numbers 1, 2, and 3; at least two of them must have the same color -- let's call them a_1 and a_2 and the color c_1; then, if a_1 + a_2 is colored c_1, we're done, so let's suppose it's colored with c_2 [12:12] <mark-t> note that, at the most, a_1 + a_2 = 5 [12:13] <mark-t> now, consider blocks of 5 consecutive numbers, that is {1,...,5}, {6,...,10}, {11,...,15}, and so on [12:13] <mark-t> there are 32 ways to color any given block, so by the time we've seen 33 blocks, we must have seen at least two with exactly the same coloring [12:14] <mark-t> let's call them {b_1 + 1, ..., b_1 + 5} and {b_2 + 1, ..., b_2 + 5} [12:15] <mark-t> from those blocks, we choose a_1 and a_2 such that b_1 + a_1 and b_1 + a_2 are the same color, with a_1 and a_2 chosen from {1,2,3} [12:17] <mark-t> and, if b_1 + a_1 is color c_1, then we have b_1 + a_1 + a_2 must be color c_2, and also b_2 + a_1 and b_2 + a_2 have color c_1 and b_2 + a_1 + a_2 have color c_2, since the {b_2 + 1, ..., b_2 + 5} block is colored exactly the same way [12:17] <mark-t> now, consider the number b_1 + b_2 + a_1 + a_2 [12:18] <mark-t> this number, along with b_1 + a_1 and b_2 + a_2 form an arithmetic progression, and b_1 + a_1 and b_2 + a_2 are both color c_1 [12:19] <mark-t> however, it also forms an arithmetic progression with b_1 + a_1 + a_2 and b_2 + a_1 + a_2, which are both colored c_2 [12:20] <mark-t> therefore, whatever color we assign to it, it will complete an arithmetic progression of length 3, all of the same color [12:21] <mark-t> er, those indices aren't right [12:21] <mark-t> replace b_1 + b_2 with 2b_2 - b_1 and a_1 + a_2 with 2a_2 - a_1 -- they're the indices needed to complete an arithmetic progression [12:21] <mark-t> I was thinking of a different theorem [12:22] <mark-t> ok, so, once you do that, the proof of this case is complete [12:23] <mark-t> to extend it to more colors, instead of being forced to complete a sequence at 2b_2 - b_1 + 2a_2 - a_1, you're forced to use a third color; then, you repeat the process to find a number where these must converge [12:24] <mark-t> to extend it to longer sequences, you take all the places where I forced there to be two of a kind and replace them with the number to force a sequence of length k-1 [12:24] <mark-t> ok, I'm done [12:26] <maxote> ! [12:26] <maxote> is known the formula of lower bound? [12:26] <mark-t> you can speak freely [12:27] <mark-t> I don't know; you can probably do something similar to Erdos's proof for Ramsey numbers [12:28] <mark-t> the exact formula is certainly unknown, but of course some lower bounds are known; I just don't know how good or bad they are [12:28] <HiLander> same order of magnitude off [12:28] <maxote> understood [12:29] <mark-t> and now I go to sleep