Articles

13.3: Ramsey Theory


13.3: Ramsey Theory

Ramsey's theorem

In combinatorial mathematics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. [1] Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)

Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. This initiated the combinatorial theory now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of monochromatic subsets, that is, subsets of connected edges of just one colour.

An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colours, c, and any given integers n1, . nc, there is a number, R(n1, . nc), such that if the edges of a complete graph of order R(n1, . nc) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour i. The special case above has c = 2 (and n1 = r and n2 = s).


A typical result in Ramsey theory starts with some mathematical structure that is then cut into pieces. How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property? This idea can be defined as partition regularity.

For example, consider a complete graph of order n that is, there are n vertices and each vertex is connected to every other vertex by an edge. A complete graph of order 3 is called a triangle. Now colour each edge either red or blue. How large must n be in order to ensure that there is either a blue triangle or a red triangle? It turns out that the answer is 6. See the article on Ramsey's theorem for a rigorous proof.

Another way to express this result is as follows: at any party with at least six people, there are three people who are all either mutual acquaintances (each one knows the other two) or mutual strangers (each one does not know either of the other two). See theorem on friends and strangers.

This also is a special case of Ramsey's theorem, which says that for any given integer c, any given integers n1. nc, there is a number, R(n1. nc), such that if the edges of a complete graph of order R(n1. nc) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour i. The special case above has c = 2 and n1 = n2 = 3.

Two key theorems of Ramsey theory are:

    : For any given c and n, there is a number V, such that if V consecutive numbers are coloured with c different colours, then it must contain an arithmetic progression of length n whose elements are all the same colour. : For any given n and c, there is a number H such that if the cells of an H-dimensional n×n×n×. ×n cube are coloured with c colours, there must be one row, column, etc. of length n all of whose cells are the same colour. That is: a multi-player n-in-a-row tic-tac-toe cannot end in a draw, no matter how large n is, and no matter how many people are playing, if you play on a board with sufficiently many dimensions. The Hales–Jewett theorem implies Van der Waerden's theorem.

A theorem similar to van der Waerden's theorem is Schur's theorem: for any given c there is a number N such that if the numbers 1, 2, . N are coloured with c different colours, then there must be a pair of integers x, y such that x, y, and x+y are all the same colour. Many generalizations of this theorem exist, including Rado's theorem, Rado–Folkman–Sanders theorem, Hindman's theorem, and the Milliken–Taylor theorem. A classic reference for these and many other results in Ramsey theory is Graham, Rothschild, Spencer and Solymosi, updated and expanded in 2015 to its first new edition in 25 years. [2]

Results in Ramsey theory typically have two primary characteristics. Firstly, they are non-constructive: they may show that some structure exists, but they give no process for finding this structure (other than brute-force search). For instance, the pigeonhole principle is of this form. Secondly, while Ramsey theory results do say that sufficiently large objects must necessarily contain a given structure, often the proof of these results requires these objects to be enormously large – bounds that grow exponentially, or even as fast as the Ackermann function are not uncommon. In some small niche cases, upper and lower bounds are improved, but not in general. In many cases these bounds are artifacts of the proof, and it is not known whether they can be substantially improved. In other cases it is known that any bound must be extraordinarily large, sometimes even greater than any primitive recursive function see the Paris–Harrington theorem for an example. Graham's number, one of the largest numbers ever used in serious mathematical proof, is an upper bound for a problem related to Ramsey theory. Another large example is the Boolean Pythagorean triples problem. [3]

Theorems in Ramsey theory are generally one of the following two types. Many such theorems, which are modeled after Ramsey's theorem itself, assert that in every partition of a large structured object, one of the classes necessarily contains a large structured subobject, but give no information about which class this is. In other cases, the reason behind a Ramsey-type result is that the largest partition class always contains the desired substructure. The results of this latter kind are called either density results or Turán-type result, after Turán's theorem. Notable examples include Szemerédi's theorem, which is such a strengthening of van der Waerden's theorem, and the density version of the Hales-Jewett theorem. [4]


13.3: Ramsey Theory

What if you are trying to get a different graph? Say a complete graph on four vertices in your color, or a cycle of four edges?

Ramsey theory has also proved that no matter which graph you pick for each player to try to color to win (or even if there are different graphs for different players!) there is some number of vertices which will guarantee there is a winner. However, what this number is is not known in most cases! We will write R(k,l) for the smallest number of vertices such that if we colored all the edges red and blue, there is either a red complete graph on k vertices or a blue complete graph on l vertices. We will write Kn for the complete graph on n vertices. (So K3 is a triangle.)

Above we proved that R(3,3)=6. Also note that R(k,1) = R(l,k) because if we can find either a red Kk or a blue Kl no matter how we color the edges, we could just switch all the colors on the edges and have either a red Kl or a blue Kk.

If you needed to win by coloring the edges of a K4, then to guarantee a winner we need at least R(4,4) vertices. Let's try to find an estimate for R(4,4). If we can find a number of vertices n that guarantees either a red K4 or a blue K4 then we'll know either R(4,4)=n or R(4,4)

But what if we don't have enough red edges for this to happen? Then we want there to be enough blue edges so that there is either a red K4 or a blue K3. This is just the same as the last question, except with colors switched! So if we don't have R(3,4) red edges, we need R(4,3)=R(3,4) blue edges! If there are 2R(3,4) - 1 edges from v, then there must be either R(3,4) red edges or R(3,4) blue edges by the pigeon hole principle. So if we have 2R(3,4) vertices, then we know we have a winner in the game when each player is trying to make a K4. (We showed either R(4,4)=2R(3,4) or R(4,4) 8, so with R(3,4)=9 or R(3,4) 8.

Now, let's put the pieces together! R(3,4)=9 and we know that R(4,4)=2R(3,4) or R(4,4) < 2R(3,4) = 18. In fact, it can be proved that R(4,4) = 18. (Can you find a coloring of K17 such that there is no red K4 and no blue K4?) So if we have at least 18 vertices, then there must be a winner.

If you are playing that you need a cycle of 4 edges to win, 6 vertices still works to guarantee a winner. Can you figure out why?


Mini-course in Finite Geometry and Ramsey Theory

This is an intensive two-week online mini-course where we will learn some applications of finite geometry in Ramsey theory. We will cover some of the recent breakthroughs in graph Ramsey theory and discuss how finite geometry can play a role in further progress.

No prior background in finite geometry or Ramsey theory is required. The algebraic background that we will need is reviewed here and the common asymptotic approximations that we will use is reviewed here.

There will be 6 lectures (1.5 hours each), 2 exercise sessions and 2 open problem sessions.

Dates: 11-01-2021 to 22-01-2021.

Time: 15:30 – 17:15 UTC

First Week, 11th Jan to 15th Jan:

Monday, Lecture 1: introduction, affine spaces, projective spaces and generalized quadrangles. Video.

Tuesday, Lecture 2: generalized quadrangles and spectral graph theory. Video.

Wednesday, Exercise Session 1. Sheet 1, Solutions.

Thursday, Lecture 3: Ramsey numbers, explicit constructions for r(3, t). Video.

Friday, Lecture 4: lower bounds via graphs with few independent sets, polar spaces, Video.

Second Week, 18th Jan to 22nd Jan:

Monday, Lecture + Exercise Session: polar spaces, Sheet 2. Video.

Tuesday, Lecture 5: clique-free optimally pseudorandom graphs from quadratic forms. Video.

Wednesday, Lecture 6: multicolour diagonal Ramsey numbers, Video.

Thursday, Open Problem Session 1.

Friday, Open Problem Session 2.

The lecture notes can be found here.

  1. Simeon Ball, Finite Geometry and Combinatorial Applications
  2. Bart De Bruyn, An introduction to Incidence Geometry
  3. Chris Godsil and Gordon Royle, Algebraic Graph Theory
  4. Luca Trevisan, Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory
  5. Akihiro Munemasa, The geometry of orthogonal groups over finite fields.
  6. Yuval Wigderson, Multicolor Ramsey numbers.
  7. David Conlon, Graph Ramsey theory.
  8. Michael Krivelevich and Benny Sudakov, Pseudo-random graphs.
  9. Jacques Verstraete, Pseudorandom Ramsey graphs.
  1. N. Alon. Explicit Ramsey graphs and orthonormal labelings.Electron J Comb, page #R12, 1994
  2. N. Alon and M. Krivelevich. Constructive bounds for a Ramsey-type problem.Graphs Comb, 13(3):217–225,1997
  3. J. Bamberg, A. Bishnoi, and T. Lesgourgues. The minimum degree of minimal Ramsey graphs for cliques.arXiv:2008.02474, 2020
  4. A. Bishnoi, F. Ihringer, and V. Pepe. A construction for clique-free pseudorandom graphs.Combinatorica,40:307–314, 2020.
  5. D. Conlon. A sequence of triangle-free pseudorandom graphs. Combin. Probab. Comput., 26:195–200, 2017.
  6. D. Conlon and A. Ferber. Lower bounds for multicolor Ramsey numbers. Adv. Math., accepted, arXiv:2009.10458, 2020 (Blog).
  7. X. He and Y. Wigderson. Multicolor Ramsey numbers via pseudorandom graphs. arXiv:1910.06287, 2019.
  8. S. Kopparty. Cayley Graphs. 2011. (Blog)
  9. A. Kostochka, P. Pudlák, & V. Rödl. Some constructive bounds on Ramsey numbers. Journal of Combinatorial Theory, Series B, 100(5), 439-445, 2010.
  10. Patrick Morris, Clique factors in pseudorandom graphs, arXiv:2101.05092, 2021.
  11. D. Mubayi and J. Verstraëte. A note on Pseudorandom Ramsey graphs. arXiv:1909.01461, 2019.
  12. A. Sah. Diagonal Ramsey via effective quasirandomness. arXiv:2005.09251, 2020.
  13. Y. Wigderson. An improved lower bound on multicolor Ramsey numbers.arXiv:2009.12020, 2020.

Lecturer: Anurag Bishnoi

Organizers: Anurag Bishnoi (TU Delft) and Jozef Skokan (LSE)

The course is open to everyone. Please sign up using the following link: https://forms.gle/oxdDo19Pgbdz7iVU8

The zoom link will be emailed to those who register.

Sponsored by the research in pairs grant of the London Mathematical Society.


Institutional Login
Log in to Wiley Online Library

If you have previously obtained access with your personal account, please log in.

Purchase single chapter
  • Unlimited viewing of the article/chapter PDF and any associated supplements and figures.
  • Article/chapter can be printed.
  • Article/chapter can be downloaded.
  • Article/chapter can not be redistributed.

Summary

Generalizations of Ramsey's Theorem

Ramsey Numbers, Bounds, and Asymptotics


Math 497A - Introduction to Ramsey Theory

Course blog: Links to supplementary material, hints to homework problems etc will be posted on http://massramsey2011.wordpress.com.

Content

The course will cover some central results of Ramsey Theory. The basic paradigm of Ramsey theory is that if a structure is sufficiently large, it will have very regular substructures of a certain size. We will illustrate this principle by means of a number of results from graph theory, number theory, and combinatorial geometry. Along the way, we will encounter a phenomenon typical of Ramsey theory -- sufficiently large often means really large. We will investigate this phenomenon and see that it has some interesting consequences concerning the foundations of mathematics.

Lecture Notes

Recommended Reading

  • Graham, Rothschild, and Spencer – Ramsey Theory, 1990
  • Nesetril – Ramsey Theory, in: Handbook of Combinatorics, 1995

Homework

Homework will be assigned each Monday and will be due in class the following Monday in class. Homework will be graded and the two lowest scores will be dropped. Late homework will not be accepted. There will be no exception to this rule. Of course it may happen that you cannot turn in homework because you were ill or for some other valid reason. This is why the two lowest scores will be dropped.


Homework 1, due August 29, 2011 (Solutions)
Homework 2, due September 7, 2011 (Solutions)
Homework 3, due September 12, 2011 (Solutions)
Homework 4, due September 19, 2011 (Solutions)
Homework 5, due September 26, 2011 (Solutions)
Homework 6, due October 3, 2011 (Solutions)
Homework 7, due October 24, 2011
Homework 8, due October 31, 2011
Homework 9, due November 7, 2011
Homework 10, due November 14, 2011 (Solutions)
Homework 11, due December 5, 2011

Research Project

Each participant is required to complete a research project on a specific topic. This will usually include reading original research papers. As part of the final exam, each participant will give a 20 minute representation on his/her project. Furthermore, participants are required to prepare a 5-10 page written report.

I will make available a list of possible projects in October. However, I welcome suggestions from students. So, look around, read a bit, maybe you will find a topic that interests you particularly.

Exams

There will be a midterm: Monday, Oct 10, 10:10-12.
Midterm preparation sheet (Oct 5, 2011)
This exam will be a closed book exams. No cheat sheets! Bring blue books.


The final exam will, according to MASS tradition, be an individual 1 hour oral exam for each participant.

Grading Policy

The final grade will take into account the homework scores, the midterm, the research project, and the final oral exam.

Academic Integrity

Collaboration: Collaboration among students to solve homework assignments is welcome. This is a good way to learn mathematics. So is the consultation of other sources such as other textbooks. However, every student has to hand in his/her own set of solutions, and if you use other people's work or ideas you have to indicate the source in your solutions.
(In any case, complete and correct homework receives full credit.)

However, from time to time there will be "controlled" problems, in which every student should work out his/her own solutions.


A stochastic Ramsey theorem

We establish a stochastic extension of Ramsey's theorem. Any Markov chain generates a filtration relative to which one may define a notion of stopping times. A stochastic colouring is any k-valued ( k < ∞ ) colour function defined on all pairs consisting of a bounded stopping time and a finite partial history of the chain truncated before this stopping time. For any bounded stopping time θ and any infinite history ω of the Markov chain, let ω | θ denote the finite partial history up to and including the time θ ( ω ) . Given k = 2 , for every ϵ > 0 , we prove that there is an increasing sequence θ 1 < θ 2 < ⋯ of bounded stopping times having the property that, with probability greater than 1 − ϵ , the history ω is such that the values assigned to all pairs ( ω | θ i , θ j ) , with i < j , are the same. Just as with the classical Ramsey theorem, we also obtain an analogous finitary stochastic Ramsey theorem. Furthermore, with appropriate finiteness assumptions, the time one must wait for the last stopping time (in the finitary case) is uniformly bounded, independently of the probability transitions. We generalise the results to any finite number k of colours.


Ahlswede R., Cai N., Zhang Z.: Rich colorings with local constraints. J. Combin. Inform. Syst. Sci. 17(3–4), 203–216 (1992)

Albert, M., Frieze, A., Reed, B.: Comments on: “Multicoloured Hamilton cycles” [Electron. J. Combin. 2 (1995), Research Paper 10, 13 pp. (electronic) MR1327570 (96b:05058)]. Electron. J. Combin., 2:Research Paper 10, Comment 1, 1 HTML document (electronic) (1995)

Alon N.: On a conjecture of Erdős, Simonovits, and Sós concerning anti-Ramsey theorems. J. Graph Theory 7(1), 91–94 (1983)

Alon N., Caro Y., Tuza Z.: Sub-Ramsey numbers for arithmetic progressions. Graphs Combin. 5(4), 307–314 (1989)

Alon N., Jiang T., Miller Z., Pritikin D.: Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints. Random Struct. Algorithms 23(4), 409–433 (2003)

Alon, N., Krech, A., Szabó, T.: Turán’s theorem in the hypercube. SIAM J. Discret. Math. 21(1):66–72 (2007) (electronic)

Alon, N., Lefmann, H., Rödl, V.: On an anti-Ramsey type result. In: Sets, Graphs and Numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, vol. 60, pp. 9–22. North-Holland, Amsterdam (1992)

Alspach B., Gerson M., Hahn G., Hell P.: On sub-Ramsey numbers. Ars Combin. 22, 199–206 (1986)

Axenovich M.: A generalized Ramsey problem. Discret. Math. 222(1–3), 247–249 (2000)

Axenovich, M., Choi, J.: On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph. Manuscript

Axenovich, M., Fon-Der-Flaass, D.: On rainbow arithmetic progressions. Electron. J. Combin. 11(1):Research Paper 1, 7 (2004) (electronic)

Axenovich M., Füredi Z., Mubayi D.: On generalized Ramsey theory: the bipartite case. J. Combin. Theory Ser. B 79(1), 66–86 (2000)

Axenovich M., Harborth H., Kemnitz A., Möller M., Schiermeyer I.: Rainbows in the hypercube. Graphs Combin. 23(2), 123–133 (2007)

Axenovich M., Iverson P.: Edge-colorings avoiding rainbow and monochromatic subgraphs. Discret. Math. 308(20), 4710–4723 (2008)

Axenovich M., Jamison R.E.: Canonical pattern Ramsey numbers. Graphs Combin. 21(2), 145–160 (2005)

Axenovich M., Jiang T.: Anti-Ramsey numbers for small complete bipartite graphs. Ars Combin. 73, 311–318 (2004)

Axenovich M., Jiang T., Kündgen A.: Bipartite anti-Ramsey numbers of cycles. J. Graph Theory 47(1), 9–28 (2004)

Axenovich, M., Jiang, T., Tuza,Z.: Local anti-Ramsey numbers of graphs. Combin. Probab. Comput. 12(5–6):495–511 (2003). Special issue on Ramsey theory

Axenovich M., Kündgen A.: On a generalized anti-Ramsey problem. Combinatorica 21(3), 335–349 (2001)

Axenovich M., Martin R.: Sub-Ramsey numbers for arithmetic progressions. Graphs Combin. 22(3), 297–309 (2006)

Balandraud É.: Coloured solutions of equations in finite groups. J. Combin. Theory Ser. A 114(5), 854–866 (2007)

Balister P.N., Gyárfás A., Lehel J., Schelp R.H.: Mono-multi bipartite Ramsey numbers, designs, and matrices. J. Combin. Theory Ser. A 113(1), 101–112 (2006)

Ball R.N., Pultr A., Vojtěchovský P.: Colored graphs without colorful cycles. Combinatorica 27(4), 407–427 (2007)

Bialostocki, A., Dierker, P., Voxman, W.: Either a graph or its complement is connected: a continuing saga. Manuscript

Bialostocki A., Voxman W.: Generalizations of some Ramsey-type theorems for matchings. Discret. Math. 239(1-3), 101–107 (2001)

Bialostocki A., Voxman W.: On monochromatic-rainbow generalizations of two Ramsey type theorems. Ars Combin. 68, 131–142 (2003)

Blokhuis A., Faudree R., Gyárfás A., Ruszinkó M.: Anti-Ramsey colorings in several rounds. J. Combin. Theory Ser. B 82(1), 1–18 (2001)

Burr, S.A.: Either a graph or its complement contains a spanning broom. Manuscript

Burr S.A., Erdős P., Graham R.L., Sós V.T.: Maximal anti-Ramsey graphs and the strong chromatic number. J. Graph Theory 13(3), 263–282 (1989)

Cameron K., Edmonds J.: Lambda composition. J. Graph Theory 26(1), 9–16 (1997)

Cameron K., Edmonds J., Lovász L.: A note on perfect graphs. Period. Math. Hung. 17(3), 173–175 (1986)

Chartrand, G., Lesniak, L.: Graphs & Digraphs, 4th edn. Chapman & Hall/CRC, Boca Raton (2005)

Chartrand, G., Zhang, P.: Chromatic Graph Theory. Chapman & Hall/CRC, Boca Raton (2009)

Chen, H., Li, X.: Long heterochromatic paths in heterochromatic triangle free graphs. Manuscript

Chen, H., Li, X., Tu, J.: Complete solution for the rainbow number of matchings. arXiv:math.CO/0611490

Chudnovsky M., Robertson N., Seymour P., Thomas R.: The strong perfect graph theorem. Ann. Math. (2) 164(1), 51–229 (2006)

Chung F.R.K., Graham R.L.: Edge-colored complete graphs with precisely colored subgraphs. Combinatorica 3(3–4), 315–324 (1983)

Erdős, P.: Solved and unsolved problems in combinatorics and combinatorial number theory. In: Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981), vol. 32, pp. 49–62 (1981)

Erdős P., Fowler T.: Finding large p-colored diameter two subgraphs. Graphs Combin. 15(1), 21–27 (1999)

Erdős, P., Gallai, T.: On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hung. 10: 337–356 (1959) (unbound insert)

Erdős P., Gyárfás A.: A variant of the classical Ramsey problem. Combinatorica 17(4), 459–467 (1997)

Erdős P., Rado R.: A combinatorial theorem. J. Lond. Math. Soc. 25, 249–255 (1950)

Erdős P., Rado R.: Combinatorial theorems on classifications of subsets of a given set. Proc. Lond. Math. Soc. (3) 2, 417–439 (1952)

Erdős P., Simonovits M.: A limit theorem in graph theory. Stud. Sci. Math. Hungar 1, 51–57 (1966)

Erdős, P., Simonovits, M., Sós, V.T.: Anti-Ramsey theorems. In: Infinite and finite sets (Colloq., Keszthely, 1973 dedicated to P. Erdős on his 60th birthday), vol. II, pp. 633–643. Colloq. Math. Soc. János Bolyai, vol. 10. North-Holland, Amsterdam (1975)

Erdős, P., Spencer, J.: Probabilistic methods in combinatorics, vol. 17. Probability and Mathematical Statistics. Academic Press (A subsidiary of Harcourt Brace Jovanovich, Publishers), New York-London (1974)

Eroh L.: Constrained Ramsey numbers of matchings. J. Combin. Math. Combin. Comput. 51, 175–190 (2004)

Eroh L.: Rainbow Ramsey numbers of stars and matchings. Bull. Inst. Combin. Appl. 40, 91–99 (2004)

Eroh L., Oellermann O.R.: Bipartite rainbow Ramsey numbers. Discret. Math. 277(1–3), 57–72 (2004)

Faudree, R.J., Gould,R., Jacobson, M., Magnant, C.: On gallai-Ramsey numbers. Manuscript

Fraisse, P., Hahn, G., Sotteau, D.: Star sub-Ramsey numbers. In: Combinatorial Design Theory. North-Holland Math. Stud., vol. 149, pp. 153–163. North-Holland, Amsterdam (1987)

Frieze A., Reed B.: Polychromatic Hamilton cycles. Discret. Math. 118(1-3), 69–74 (1993)

Fujita, S., Kaneko, A., Schiermeyer, I., Suzuki, K.: A rainbow k-matching in the complete graph with r colors. Electron. J. Combin. 16(1):Research Paper 51 (2009) (electronic)

Fujita, S., Magnant, C.: Extensions of rainbow Ramsey results. Manuscript

Fujita, S., Magnant, C.: Gallai-Ramsey numbers for cycles. Manuscript

Fujita, S., Kaneko, A., Saito, A., Schiermeyer, I., Suzuki, K.: Manuscript

Füredi Z.: An upper bound on Zarankiewicz’ problem. Combin. Probab. Comput. 5(1), 29–33 (1996)

Gallai T.: Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hungar 18, 25–66 (1967)

Galvin F.: Advanced problem number 6034. Am. Math. Mon. 82, 529 (1975)

Gorgol I.: Rainbow numbers for cycles with pendant edges. Graphs Combin. 24(4), 327–331 (2008)

Gorgol, I., Łazuka, E.: Rainbow numbers for certain graphs. In: Fifth Cracow Conference on Graph Theory USTRON ’06. Electron. Notes Discrete Math., vol. 24, pp. 77–79. Elsevier, Amsterdam, (2006) (electronic)

Gyárfás, A.: Fruit salad. Electron. J. Combin. 4(1):Research Paper 8, 8 pp. (1997) (electronic)

Gyárfás A., Lehel J., Nešetřil J., Rödl V., Schelp R.H., Tuza Zs.: Local k-colorings of graphs and hypergraphs. J. Combin. Theory Ser. B 43(2), 127–139 (1987)

Gyárfás A., Lehel J., Schelp R.H.: Finding a monochromatic subgraph or a rainbow path. J. Graph Theory 54(1), 1–12 (2007)

Gyárfás A., Lehel J., Schelp R.H., Tuza Zs.: Ramsey numbers for local colorings. Graphs Combin. 3(3), 267–277 (1987)

Gyárfás, A., Sárközy, G., Sebő, A., Selkow, S.: Ramsey-type results for gallai colorings. Manuscript

Gyárfás A., Simonyi G.: Edge colorings of complete graphs without tricolored triangles. J. Graph Theory 46(3), 211–216 (2004)

Hahn G.: More star sub-Ramsey numbers. Discret. Math. 34(2), 131–139 (1981)

Hahn G., Thomassen C.: Path and cycle sub-Ramsey numbers and an edge-colouring conjecture. Discret. Math. 62(1), 29–33 (1986)

Harborth, H., Kemnitz, A., Krause,S.: Manuscript

Haxell P.E., Kohayakawa Y.: On an anti-Ramsey property of Ramanujan graphs. Random Struct. Algorithms 6(4), 417–431 (1995)

Hell P., Montellano-Ballesteros J.J.: Polychromatic cliques. Discret. Math. 285(1–3), 319–322 (2004)

Jamison R.E., Jiang T., Ling A.C.H.: Constrained Ramsey numbers of graphs. J. Graph Theory 42(1), 1–16 (2003)

Jamison R.E., West D.B.: On pattern Ramsey numbers of graphs. Graphs Combin. 20(3), 333–339 (2004)

Jiang T.: Anti-Ramsey numbers of subdivided graphs. J. Combin. Theory Ser. B 85(2), 361–366 (2002)

Jiang T.: Edge-colorings with no large polychromatic stars. Graphs Combin. 18(2), 303–308 (2002)

Jiang T., Mubayi D.: New upper bounds for a canonical Ramsey problem. Combinatorica 20(1), 141–146 (2000)

Jiang T., Pikhurko O.: Anti-Ramsey numbers of doubly edge-critical graphs. J. Graph Theory 61(3), 210–218 (2009)

Jiang, T., Schiermeyer, I., West, D.B.: The Erdős-Simonovits-Sós conjecture for k ≤ 7. Manuscript

Jiang, T., West, D.B.: Edge-colorings of complete graphs that avoid polychromatic trees. In: The Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications. Electron. Notes Discrete Math., pp. 10. Elsevier, Amsterdam (2002) (electronic)

Jiang, T., West, D.B.: On the Erdős–Simonovits-Sós conjecture about the anti-Ramsey number of a cycle. Combin. Probab. Comput. 12(5–6):585–598 (2003) (Special issue on Ramsey theory)

Jin, Z., Li, X: Anti-Ramsey numbers for graphs with independent cycles. Electron. J. Combin. 16:Research Paper 85 (2009)

Jungić V., Král D., Škrekovski R.: Colorings of plane graphs with no rainbow faces. Combinatorica 26(2), 169–182 (2006)

Jungić, V., Licht, J., Mahdian, M., Nešetřil, J., Radoičić, R.: Rainbow arithmetic progressions and anti-Ramsey results. Combin. Probab. Comput., 12(5-6):599–620, 2003. Special issue on Ramsey theory

Jungić, V., Nešetřil, J., Radoičić, R.: Rainbow Ramsey theory. Integers 5(2):A9, 13 (electronic), (2005)

Jungić, V., Radoičić, R.: Rainbow 3-term arithmetic progressions. Integers 3:A18, 8 (electronic), (2005)

Kano M., Li X: Monochromatic and heterochromatic subgraphs in edge-colored graphs—a survey. Graphs Combin. 24(4), 237–263 (2008)

Körner J., Simonyi G.: Trifference. Stud. Sci. Math. Hung. 30(1–2), 95–103 (1995)

Kündgen A., Pelsmajer M.J.: Nonrepetitive colorings of graphs of bounded tree-width. Discret. Math. 308(19), 4473–4478 (2008)

Lefmann H., Rödl V.: On canonical Ramsey numbers for complete graphs versus paths. J. Combin. Theory Ser. B 58(1), 1–13 (1993)

Lefmann H., Rödl V.: On Erdős-Rado numbers. Combinatorica 15(1), 85–104 (1995)

Lefmann H., Rödl V., Wysocka B.: Multicolored subsets in colored hypergraphs. J. Combin. Theory Ser. A 74(2), 209–248 (1996)

Li, X., Xu, Z.: Rainbow number of matchings in regular bipartite graphs. arXiv:math.CO/0711.2846

Li, X., Tu, J., Jin, Z.: Bipartite rainbow numbers of matchings. Discret. Math. 309(8):2575–2578 (2009)

Lovász L.: Normal hypergraphs and the perfect graph conjecture. Discret. Math. 2(3), 253–267 (1972)

Manoussakis Y., Spyratos M., Tuza Zs., Voigt M.: Minimal colorings for properly colored subgraphs. Graphs Combin. 12(4), 345–360 (1996)

Montellano-Ballesteros J.J.: An anti-Ramsey theorem on edge-cuts. Discuss. Math. Graph Theory 26(1), 19–21 (2006)

Montellano-Ballesteros J.J.: On totally multicolored stars. J. Graph Theory 51(3), 225–243 (2006)

Montellano-Ballesteros, J.J., Neumann-Lara,V.: Totally multicoloured cycles. In: 6th International Conference on Graph Theory (Marseille, 2000). Electron. Notes Discrete Math., vol. 5, p 4 (electronic). Elsevier, Amsterdam (2000)

Montellano-Ballesteros J.J., Neumann-Lara V.: An anti-Ramsey theorem. Combinatorica 22(3), 445–449 (2002)

Montellano-Ballesteros J.J., Neumann-Lara V.: A linear heterochromatic number of graphs. Graphs Combin. 19(4), 533–536 (2003)

Montellano-Ballesteros J.J., Neumann-Lara V.: An anti-Ramsey theorem on cycles. Graphs Combin. 21(3), 343–354 (2005)

Montellano-Ballesteros J.J., Neumann-Lara V., Rivera-Campo E.: On a heterochromatic number for hypercubes. Discret. Math. 308(16), 3441–3448 (2008)

Mubayi D.: Edge-coloring cliques with three colors on all 4-cliques. Combinatorica 18(2), 293–296 (1998)

Mubayi, D., West, D.B.: On restricted edge-colorings of bicliques. Discrete Math. 257(2–3):513–529, 2002. Kleitman and combinatorics: a celebration (Cambridge, MA, 1999)

Pula, K.: Gallai multigraphs. Manuscript

Radziszowski, S.P.: Small Ramsey numbers. Electron. J. Combin. 1 Dyn Surv 1, 30 (electronic), (1994)

Ramamurthi, R., West, D.B.: Maximum face-constrained coloring of plane graphs. In: The Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications. Electron. Notes Discrete Math., vol. 11, p. 8 (electronic). Elsevier, Amsterdam (2002)

Ramsey F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. 30, 264–286 (1930)

Rödl V.: On Ramsey families of sets. Graphs Combin. 6(2), 187–195 (1990)

Sárközy G.N., Selkow S.: On an anti-Ramsey problem of Burr, Erdős, Graham, and T Sós. J. Graph Theory 52(2), 147–156 (2006)

Schiermeyer I.: Rainbow numbers for matchings and complete graphs. Discret. Math. 286(1–2), 157–162 (2004)

Schiermeyer, I.: Rainbow colourings. 2007. Invited papers from RIMS, Kyoto University

Serra,O.: Some Ramsey and anti-Ramsey results in finite groups. In: 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. Electron. Notes Discrete Math., vol 28, pp 437–444. Elsevier, Amsterdam (2007)

Simonovits M., Sós V.T.: On restricted colourings of K n. Combinatorica 4(1), 101–110 (1984)

Turán P.: Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48, 436–452 (1941)


Ramsey Theory

Ramsey theory is a relatively &ldquonew,&rdquo approximately 100 year-old direction of fascinating mathematical thought that touches on many classic fields of mathematics such as combinatorics, number theory, geometry, ergodic theory, topology, combinatorial geometry, set theory, and measure theory. Ramsey theory possesses its own unifying ideas, and some of its results are among the most beautiful theorems of mathematics. The underlying theme of Ramsey theory can be formulated as: any finite coloring of a large enough system contains a monochromatic subsystem of higher degree of organization than the system itself, or as T.S. Motzkin famously put it, absolute disorder is impossible.

Ramsey Theory: Yesterday, Today, and Tomorrow explores the theory&rsquos history, recent developments, and some promising future directions through invited surveys written by prominent researchers in the field. The first three surveys provide historical background on the subject the last three address Euclidean Ramsey theory and related coloring problems. In addition, open problems posed throughout the volume and in the concluding open problem chapter will appeal to graduate students and mathematicians alike.


Contributors:
J. Burkert, A. Dudek, R.L. Graham, A. Gyárfás, P.D. Johnson, Jr., S.P. Radziszowski, V. Rödl, J.H. Spencer, A. Soifer, E. Tressler.

Alexander Soifer is a Russian born and educated American mathematician, a professor of mathematics at the University of Colorado, an author of some 200 articles on mathematics, history of mathematics, mathematics education, film reviews, etc. He is Senior Vice President of the World Federation of National Mathematics Competitions, which in 2006 awarded him The Paul Erdos Award. 26 years ago Soifer founded and has since chaired the Colorado Mathematical Olympiad, and served on both the USSR and USA Mathematical Olympiads committees. Soifer's Erdos number is 1.

“As we learn from the preface, [Ramsey Theory: Yesterday, Today and Tomorrow] grew out of an intentionally non-traditional conference on Ramsey theory. In accordance with that, the book itself is far from being a traditional textbook or reference book on the subject…We learn far more about the history of Ramsey theory than from other sources…the promise of discussing the future is fulfilled by a very extensive list of open problems contributed by numerous participants. Sometimes it is not even clear what the best way of asking a certain question is, and we are shown the raw form of the problem, just as we would if we participated at a conference…the book is undoubtedly a lot of fun. As one expects from a book on Ramsey theory, it is full of problems that are very easy to formulate, but terribly hard to solve…[the book] could well be used for a course using a seminar format, or for self-study by a graduate student familiarizing himself with the subject.” —MAA Reviews