Department of Mathematics,
University of California San Diego
****************************
Math 269 - Seminar in Combinatorics
Ji Zeng
Alfréd Rényi Institute of Mathematics, Budapest (jzeng@ucsd.edu)
Unbalanced Zarankiewicz problem for bipartite subdivisions
Abstract:
A real number $\sigma$ is called a \textit{linear threshold} of a bipartite graph $H$ if every bipartite graph $G = (U \sqcup V, E)$ with unbalanced parts $|V| \gtrsim |U|^\sigma$ and without a copy of $H$ must have a linear number of edges $|E| \lesssim |V|$. We prove that $\sigma_s = 2 - 1/s$ is a linear threshold of the \textit{complete bipartite subdivision} graph $K_{s,t}'$. Moreover, we show that any $\sigma < \sigma_s$ is not a linear threshold of $K_{s,t}'$ for sufficiently large $t$ (depending on $s$ and $\sigma$). Some applications of our result in incidence geometry are discussed.
Lutz Warnke
October 22, 2024
2:00 PM
AP&M 7321
Research Areas
Combinatorics****************************
