Onstwedder, Marit (2020) Cycle-Complete Graph Ramsey Numbers. Bachelor's Thesis, Mathematics.
|
Text
bMATH_2020_OnstwedderMJ.pdf Download (598kB) | Preview |
|
![]() |
Text
toestemming.pdf Restricted to Registered users only Download (92kB) |
Abstract
Given two graphs G and H, the Ramsey number R(G,H) is the smallest natural number N such that every red/blue coloring of the edges of the complete graph K_N contains a red copy of G or a blue copy of H. The proofs for the following results will be given. The upper and lower bounds of the symmetric Ramsey numbers are: 2^(k/2) < R(k,k) < 4^(k-1) for k >= 3. The main result is the upper bound of R(C_m,K_n): For all m >= 3 and n >= 2, the cycle-complete graph Ramsey number R(C_m,K_n) satisfies R(C_m,K_n) <= ⌈(m-2)(n^(1/k)+2)+1⌉ (n-1), where k = ⌊(m-1)/2⌋. Specifically for cycles of order 4 there is an upper bound: R(C_4,K_n) < c ((n log(log(n)))/log(n))^2, where n goes to infinity. Finally, there is an exact result: R(C_9,K_8)=57.
Item Type: | Thesis (Bachelor's Thesis) |
---|---|
Supervisor name: | Muller, T. and Hirsch, C.P. |
Degree programme: | Mathematics |
Thesis type: | Bachelor's Thesis |
Language: | English |
Date Deposited: | 13 Jul 2020 13:44 |
Last Modified: | 13 Jul 2020 13:44 |
URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/22629 |
Actions (login required)
![]() |
View Item |