Keywords
Graph theory, Bipartite Ramsey number, double star, Tur´an number
Abstract
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. For positive integers $n, m$, the double star $S(n,m)$ is the graph consisting of the disjoint union of two stars $K_{1,n}$ and $K_{1,m}$ together with an edge joining their centers. The $k$-color bipartite Ramsey number of $ S(n,m)$, denoted by $r_{bip}(S(n,m);k)$, is the smallest integer $N$ such that, in any $k$-coloring of the edges of the complete bipartite graph $K_{N,N}$, there is a monochromatic copy of $S(n,m)$. The study of bipartite Ramsey numbers was initiated in the early 1970s by Faudree and Schelp and, independently, by Gy\'arf\'as and Lehel. The exact value of $r_{bip}(S(n,m);k)$ is only known for $n=m=1$ and all $k\ge2$. Here we prove that if $k=2$ and $n\ge m$, or $k\ge3$ and $n\ge 2m$, then
\[ r_{bip}(S(n,m);k)=kn+1.\]
For $k \geq 3$ and $m \leq n < 2m$, we prove that,
\[\max\{kn + 1, (2k-4)m+1\} \leq r_{bip}(S(n,m) ; k) \leq \max\left\{ kn + 1, \left[2k - 1 - \frac{1}{2k} - O\left(\frac{1}{k^2}\right)\right]m + 1 \right \},\]
where the lower bound is due to DeBiasio, Gy\'arf\'as, Krueger, Ruszink\'o, and S\'ark\"ozy in 2019.
Thesis Completion Year
2024
Thesis Completion Semester
Spring
Thesis Chair
Song, Zi-Xia
College
College of Sciences
Department
Mathematics
Thesis Discipline
Mathematics
Language
English
Access Status
Open Access
Length of Campus Access
None
Campus Location
Orlando (Main) Campus
Subjects
Ramsey numbers; Bipartite graphs; Graph theory --Extremal problems; Double stars--Research; Ramsey theory
STARS Citation
DeCamillis, Gregory M., "Multicolor Bipartite Ramsey Number of Double Stars" (2024). Honors Undergraduate Theses. 99.
https://stars.library.ucf.edu/hut2024/99
Included in
Rights Statement
