Skip to content
Preprint

Sharper Zarankiewicz and Diagonal Bipartite Ramsey Bounds

Sep 2026 · 0 citations · 9 references
Mathematics

Abstract

We prove that there is an absolute positive constant $c$ such that every bipartite graph with $N$ vertices in each part and at least $N^2/2$ edges contains a complete bipartite graph $K_{t,t}$ whenever $N\ge c\, 2^{t}$. This improves the classical K\H{o}v\'ari-S\'os-Tur\'an bound requiring $N$ of order $t\,2^t $. As a consequence, the diagonal bipartite Ramsey number has upper bound $b(t,t)=O(2^t)$, improving the previous best bound $b(t,t) = O(2^t\, \log t )$ due to Conlon. The proof was found by GPT-6 Astra, and the method will probably have further applications.

View source

Similar papers

Preprint Sep 2026

Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs

We prove the following two upper bounds for ordered Ramsey numbers: (1) Every ordered forest $F$ on $n$ vertices satisfies $R_{<}(F,F)=O(n^{1+\lceil\log\chi_{<}(F)\rceil})$. This in particular answers a question of Geneson, Holmes, Liu, Neidinger, Pehova and Wass. (2) There is a function $f$ such that, for every fixed...

Lior Gishboliner, Xiang-Yu Li · 0 citations
Preprint Oct 2026

Sharp bounds for off-diagonal and tripartite canonical Ramsey numbers

The canonical Ramsey theorem establishes that for every positive integer $t$, there is a sufficiently large $n$ such that every edge-colouring of a complete graph $K_n$ contains a copy of $K_t$ that is canonically coloured, i.e. monochromatic, rainbow, or lexicographic. In this paper we investigate two variations of th...

Strahinja Gvozdic, Zach Hunter, Aleksa Milojević et al. · 0 citations
Preprint Oct 2026

Optimal Bounds on Spanning Tree Embeddings

We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....

Csongor Beke, V. Boskovic, Nina Kamčev et al. · 0 citations
Preprint Oct 2026

A sharp upper bound on the number of spanning forests of regular graphs

Let $G$ be a simple graph on $n$ vertices, and let $F(G)$ denote the number of its spanning forests. Bencs and Csikv\'ari [Upper bound for the number of spanning forests of regular graphs, European J. Combin. 110 (2023) 103677] proved that every $r$-regular graph $G$ with $r\geq 2$ satisfies $F(G) \leq r^{n}$. They fur...

Ting-Zeng Wu, S. Lu, Xiang-Shuai Dong · 0 citations
Preprint Oct 2026

On Colorful Kruskal--Katona Theorems

What is the maximum number of rainbow triangles in an edge-colored graph with $m$ edges and $r$ colors? Using entropic techniques, we prove an upper bound of $C_rm^{3/2}$ rainbow triangles with $C_r=\sqrt{\frac{2(r-2)}{9r}}$; this constant is best possible whenever there exists an affine plane of order $r-1$. We also s...

Ting-Wei Chao, M. Sankar, Hung-Hsun Hans Yu · 0 citations
Preprint Sep 2026

Extremal hypergraphs without generalized 4-cycles

In 1977, Erd\H{o}s posed the problem of determining the maximum number $f_r(n)$ of edges in an $n$-vertex $r$-uniform hypergraph in which all disjoint pairs of edges have distinct unions. F\"uredi later conjectured that, for every fixed $r\ge 4$ and all sufficiently large $n$, $f_r(n)=\binom{n-1}{r-1}+\lfloor \frac{n-1...

Hao-Wei Huang, Jie Ma, Tian-Chi Yang · 2 citations · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.