Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.10204 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915340990021632 |
|---|---|
| author | Ködmön, Lili Li, Anqi Zeng, Ji |
| author_facet | Ködmön, Lili Li, Anqi Zeng, Ji |
| contents | For a bipartite graph $H$, its linear threshold is the smallest real number $σ$ such that every bipartite graph $G = (U \sqcup V, E)$ with unbalanced parts $|V| \gtrsim |U|^σ$ and without a copy of $H$ must have a linear number of edges $|E| \lesssim |V|$. We prove that the linear threshold of the complete bipartite subdivision graph $K_{s,t}'$ is at most $σ_s = 2 - 1/s$. Moreover, we show that any $σ< σ_s$ is less than the linear threshold of $K_{s,t}'$ for sufficiently large $t$ (depending on $s$ and $σ$).
Some geometric applications of this result are given: we show that any $n$ points and $n$ lines in the complex plane without an $s$-by-$s$ grid determine $O(n^{4/3 - c})$ incidences for some constant $c > 0$ depending on $s$; and for certain pairs $(p,q)$, we establish nontrivial lower bounds on the number of distinct distances determined by $n$ points in the plane under the condition that every $p$ points determine at least $q$ distinct distances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10204 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unbalanced Zarankiewicz problem for bipartite subdivisions with applications to incidence geometry Ködmön, Lili Li, Anqi Zeng, Ji Combinatorics For a bipartite graph $H$, its linear threshold is the smallest real number $σ$ such that every bipartite graph $G = (U \sqcup V, E)$ with unbalanced parts $|V| \gtrsim |U|^σ$ and without a copy of $H$ must have a linear number of edges $|E| \lesssim |V|$. We prove that the linear threshold of the complete bipartite subdivision graph $K_{s,t}'$ is at most $σ_s = 2 - 1/s$. Moreover, we show that any $σ< σ_s$ is less than the linear threshold of $K_{s,t}'$ for sufficiently large $t$ (depending on $s$ and $σ$). Some geometric applications of this result are given: we show that any $n$ points and $n$ lines in the complex plane without an $s$-by-$s$ grid determine $O(n^{4/3 - c})$ incidences for some constant $c > 0$ depending on $s$; and for certain pairs $(p,q)$, we establish nontrivial lower bounds on the number of distinct distances determined by $n$ points in the plane under the condition that every $p$ points determine at least $q$ distinct distances. |
| title | Unbalanced Zarankiewicz problem for bipartite subdivisions with applications to incidence geometry |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.10204 |