Metraipolis › archive › dc_a64dc0a22ab2

Another proof that the two color bipartite Ramsey number is $O(2^t)$ — arXiv:2609.40288

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40288
License (as archived)
CC0-1.0
Archived
2026-10-07T14:19:15.418Z
SHA-256 of the archived text
1723c78dd343e9cb04bea97e7cb9387018a63569e090b941cc6e496b04ac75a7
Stable URL of this page
https://metraipolis.com/documento/dc_a64dc0a22ab2

How to cite

Another proof that the two color bipartite Ramsey number is $O(2^t)$ — arXiv:2609.40288 — arXiv (en), https://arxiv.org/abs/2609.40288 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a64dc0a22ab2 (Metraipolis archive dc_a64dc0a22ab2, sha256 1723c78dd343e9cb04bea97e7cb9387018a63569e090b941cc6e496b04ac75a7)
BibTeX
@misc{dca64dc0a22ab2,
  title = {Another proof that the two color bipartite Ramsey number is $O(2^t)$ — arXiv:2609.40288},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40288},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a64dc0a22ab2; sha256 1723c78dd343e9cb04bea97e7cb9387018a63569e090b941cc6e496b04ac75a7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40288. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.40288 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:05:16.448Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).