The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edge-colorings of complete graphs. For any graphs G, H1, ..., Hk, we write G → (H1, ..., Hk), or G → (H)k when H1 = ··· = Hk = H, if every k-edge-coloring of G contains a monochromatic Hi in color i for some i ∈ {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the minimum integer n such that Kn → (H1, ..., Hk), where Kn is the complete graph on n vertices. Computing rk(H1, ..., Hk) is a notoriously difficult problem in combinatorics. A weakening of this problem is to restrict ourselves to Gallai colorings, that is, edge-colorings with no rainbow triangles. From this we define the Gallai-Ramsey number grk(K3,G) as the minimum integer n such that either Kn contains a rainbow triangle, or Kn → (G)k . In this thesis, we determine the Gallai-Ramsey numbers for C7 with multiple colors. We believe the method we developed can be applied to find grk(K3, C2n+1) for any integer n ≥ 2, where C2n+1 denotes a cycle on 2n + 1 vertices.
Identifer | oai:union.ndltd.org:ucf.edu/oai:stars.library.ucf.edu:honorstheses-1198 |
Date | 01 January 2017 |
Creators | Bruce, Dylan |
Publisher | STARS |
Source Sets | University of Central Florida |
Language | English |
Detected Language | English |
Type | text |
Format | application/pdf |
Source | Honors Undergraduate Theses |
Page generated in 0.0018 seconds