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

Download

Share

COinS
 

Accessibility Statement

This item was created or digitized prior to April 24, 2027, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.

Rights Statement

In Copyright