$C_4$-free subgraphs of high degree with geometric applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909667397992448 |
|---|---|
| author | Hunter, Zach Milojević, Aleksa Tomon, Istvan Sudakov, Benny |
| author_facet | Hunter, Zach Milojević, Aleksa Tomon, Istvan Sudakov, Benny |
| contents | The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$-vertex graph that does not contain the complete bipartite graph $K_{s,s}$. While the problem remains widely open in the case of general graphs, the past two decades have seen significant progress on this problem for various restricted graph classes -- particularly those arising from geometric settings -- leading to a deeper understanding of their structure.
In this paper, we develop a new structural tool for addressing Zarankiewicz-type problems. More specifically, we show that for any positive integer $k$, every graph with average degree $d$ either contains an induced $C_4$-free subgraph with average degree at least $k$, or it contains a $d$-vertex subgraph with $Ω_k(d^2)$ edges. As an application of this dichotomy, we propose a unified approach to a large number of Zarankiewicz-type problems in geometry, obtaining optimal bounds in each case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23942 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $C_4$-free subgraphs of high degree with geometric applications Hunter, Zach Milojević, Aleksa Tomon, Istvan Sudakov, Benny Combinatorics Computational Geometry The Zarankiewicz problem, a cornerstone problem in extremal graph theory, asks for the maximum number of edges in an $n$-vertex graph that does not contain the complete bipartite graph $K_{s,s}$. While the problem remains widely open in the case of general graphs, the past two decades have seen significant progress on this problem for various restricted graph classes -- particularly those arising from geometric settings -- leading to a deeper understanding of their structure. In this paper, we develop a new structural tool for addressing Zarankiewicz-type problems. More specifically, we show that for any positive integer $k$, every graph with average degree $d$ either contains an induced $C_4$-free subgraph with average degree at least $k$, or it contains a $d$-vertex subgraph with $Ω_k(d^2)$ edges. As an application of this dichotomy, we propose a unified approach to a large number of Zarankiewicz-type problems in geometry, obtaining optimal bounds in each case. |
| title | $C_4$-free subgraphs of high degree with geometric applications |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2506.23942 |