Back to search

Rochester Institute of Technology

Bipartite Ramsey Numbers and Zarankiewicz Numbers

Abstract

dc:description.abstract

The bipartite Ramsey number b(m, n) is the minimum b such that any 2-coloring of Kb,b results in a monochromatic Km,m subgraph in the first color or a monochromatic Kn,n subgraph in the second color. The Zarankiewicz number z(m, n; s, t) is the maximum size among Ks,t-free subgraphs of Km,n. In this work, we discuss the intimate relationship between the two numbers as well as propose a new method for bounding the Zarankiewicz numbers. We use the better bounds to improve the upper bound on b(2, 5), in addition we improve the lower bound of b(2, 5) by construction. The new bounds are shown to be 17 ≤ b(2, 5) ≤ 18. Additionally, we apply the same methods to the multicolor case b(2, 2, 3) which has previously not been studied and determine bounds to be 16 ≤ b(2, 2, 3) ≤ 23.

Degree

thesis:*
Name thesis:degree_name
Applied and Computational Mathematics (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
School of Mathematical Sciences (COS)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Collins, Alex F
Contributors dc:contributor
  • Stanisław Radziszowski

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/8626

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Collins, Alex F. Bipartite Ramsey Numbers and Zarankiewicz Numbers. Thesis thesis, https://repository.rit.edu/theses/8626