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

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
[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
[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