Ramseyeva števila in njihove posplošitve : magistrsko delo

Hočevar, Mitja (author), Šparl, Primož (mentor)

Magistrsko delo govori o teoriji, ki v splošnem sodi na področje kombinatorike. Po Ramseyevem izreku iz leta 1930 za poljubna tri naravna števila r, , n obstaja neko najmanjše naravno število m0, za katero velja, da lahko vsaki množici moči m  m0 najprej njene r-elementne podmnožice poljubno razdelimo v  disjunktnih razredov, pa bomo v osnovni množici zagotovo našli podmnožico velikosti n, tako da so vse njene r-elementne podmnožice iz istega razreda. Pripadajoča teorija se v primeru, ko je r = 2, zelo dobro prevede iz množic na polne grafe. Pri tem nam osnovno množico predstavlja množica vozlišč polnega grafa, 2-elementne podmnožice pa so povezave med vozlišči. Število razredov  predstavlja število barv, s katerimi barvamo povezave grafa. V celotnem grafu tedaj iščemo poln podgraf določenega reda n, v katerem so vse povezave iste barve oziroma pripadajo istemu razredu. Pripadajoča števila m0 so klasična Ramseyeva števila. Klasična Ramseyeva števila za polne grafe so sicer še vedno zelo živa in zanimiva tema, vendar so mnogi avtorji osnovni koncept posplošili, iz česar se je rodilo mnogo različnih izpeljank in posplošitev Ramseyevih števil. Kot rečeno obravnavamo pri klasičnih Ramseyevih številih barvanja povezav polnih grafov, prav tako pa v njih iščemo polne podgrafe s povezavami iste barve. Prva smiselna posplošitev je torej iskanje drugih standardnih podgrafov v barvanjih povezav polnega grafa in v barvanjih povezav drugih standardnih grafov. V magistrskem delu najprej zapišemo osnovne pojme teorije grafov, potrebne za razumevanje nadaljevanja dela. Na kratko povzamemo in pregledamo osnove Ramseyeve teorije, obravnavane v avtorjevem diplomskem delu. Nato opravimo naiven poskus iskanja klasičnih Ramseyevih števil s pomočjo računalniškega algoritma, brez posebnega ozira na optimizacijo ali matematično ozadje problema. Glavni del magistrskega dela predstavlja kronološki pregled raziskovanja in odkrivanja klasičnih Ramseyevih števil za dve barvi, kjer so predstavljene tudi različne metode, ki so se pri tem uporabljale. V zadnjem delu magistrskega dela navedemo še nekaj rezultatov za klasična Ramseyeva števila za več barv in predstavimo nekaj zanimivih posplošitev Ramseyevih števil.

• Language: Slovenian
• Keywords: teorija grafov, Ramseyeva teorija, Ramseyevo število, posplošena Ramseyeva števila
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: PEF - Faculty of Education
• Publisher: [M. Hočevar]
• Year: 2018
• Number of pages: 57 str.
• PID: 20.500.12556/RUL-104328
• UDC: 519.1(043.2)
• COBISS.SI-ID: 12148809
• Publication date in RUL: 09.10.2018

Secondary language

• Language: English
• Title: Ramsey numbers and their generalizations

Abstract

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.

• Keywords: mathematics, matematika