Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper provides an independent proof that the 2-color bipartite Ramsey number $b_2(t)$ is bounded by $O(2^t)$, specifically $b_2(t) \le 128 \cdot 2^t$. This result extends to $q$ colors, showing $b_q(t) \le 128 \cdot q^t$, and also yields a uniform consequence for Zarankiewicz numbers. The proof establishes that any bipartite graph with edge density at least $p$ and class sizes $\ge 128 \cdot p^{-t}$ contains a $K_{t,t}$ subgraph.
A tight $O(2^t)$ upper bound for the 2-color bipartite Ramsey number $b_2(t)$ is independently proven, refining previous results.
For positive integers $t$ and $q$ let $b_q(t)$ be the smallest integer $n$ so that any coloring of the edges of the complete bipartite graph $K_{n,n}$ with $q$ colors yields a monochromatic copy of $K_{t,t}$. We give an independent proof that $b_2(t)\le 128\cdot 2^t$ for every positive integer $t$. More generally, for $0< p\le 1/2$, every bipartite graph of edge density at least $p$, with both classes of size at least $128\cdot p^{-t}$, contains $K_{t,t}$. This gives $b_q(t)\le 128\cdot q^t$ for every integer $q\ge 2$ and a uniform consequence for Zarankiewicz numbers.