Ramsey numbers and their generalizations

This MSc thesis deals with a theory, which comes from combinatorics. According to Ramsey's theorem from 1930 for any natural numbers r, , n there is a smallest natural number m0 such that for every set of size m m0 no matter how we partition its r-element subsets into disjoint classes, we can always find a subset of size n in the original set such that all its r-element subsets belong to the same class. In the case of r = 2 this theory naturally translates from set theory to graph theory. Here the original set is represented by the set of vertices of a complete graph and the 2-element subsets are the edges of the graph. The number of classes is the number of colours with which we colour the edges of the complete graph. In this complete graph we then search for complete subgraphs of defined size n, in which all edges have the same colour or belong to the same class. The numbers m0 are called classic Ramsey numbers. Determining classic Ramsey numbers for complete graphs is still a very intersting topic, but many authors have generalized this basic concept to obtain many different generalizations of Ramsey numbers. As stated, classic Ramsey numbers are sizes of complete graphs in which we colour edges and search for complete subgraphs in one colour. The first reasonable generalization is thus to investigate other standard subgraphs in colourings of edges of complete graphs and in colourings of edges of other standard graphs. In the MSc thesis we begin by introducing the terminology and writing down basics of graph theory needed for the understanding the rest of the thesis. We briefly summarize the basics of Ramsey theory discussed in the authors BSc thesis. We attempt to make our own computer assisted algorithm for discovering Ramsey numbers, with no real attention to optimization and mathematical background of the problem. The main part of the thesis consists of a chronological overview of the investigation and determination of classic Ramsey numbers for two colours, where the different methods that the authors used are also presented. In the last part of thesis we take a look at some results for the classical Ramsey numbers for more colours and present some of the interesting generalizations of Ramsey numbers