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

Download

Share

COinS
 

Rights Statement

In Copyright