For graphs with no induced T (forest with broom components or any forest) and no induced H (complete multipartite or bipartite), χ(G) is at most C times R(α(H), ω(G)+1) for a constant C depending only on T and H.
$C_4$-free subgraphs of high degree with geometric applications
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
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 $\Omega_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.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 4years
2026 4roles
background 1polarities
background 1representative citing papers
Every K_{s,t}-free graph of average degree Ω(h^{2(s-1)} log^{7(s-1)} h) and every C_{2k}-free graph of average degree Ω(h log^5 h) contains an induced subdivision of K_h, both nearly optimal.
Proves a parity Erdős-Hajnal theorem for t-intersecting curves, recovering the t=1 case and yielding an n(log n)^{O_t(log k)} edge bound for topological graphs with no k edges that pairwise cross oddly.
The Zarankiewicz number for these box-intersection hypergraphs is either Θ_r(t n^{r-1}) or Ω(t n^{r-1} log n / log log n) according to whether the direction families (F1,...,Fr) are 2-coherent.
citing papers explorer
-
Ramsey-type $\chi$-bounds for $\chi$-bounded graph classes
For graphs with no induced T (forest with broom components or any forest) and no induced H (complete multipartite or bipartite), χ(G) is at most C times R(α(H), ω(G)+1) for a constant C depending only on T and H.
-
Nearly tight bounds for induced subdivisions
Every K_{s,t}-free graph of average degree Ω(h^{2(s-1)} log^{7(s-1)} h) and every C_{2k}-free graph of average degree Ω(h log^5 h) contains an induced subdivision of K_h, both nearly optimal.
-
A parity Erd\H{o}s-Hajnal theorem for $t$-intersecting curves
Proves a parity Erdős-Hajnal theorem for t-intersecting curves, recovering the t=1 case and yielding an n(log n)^{O_t(log k)} edge bound for topological graphs with no k edges that pairwise cross oddly.
-
A dichotomy for hypergraph Zarankiewicz problems on axis-parallel boxes
The Zarankiewicz number for these box-intersection hypergraphs is either Θ_r(t n^{r-1}) or Ω(t n^{r-1} log n / log log n) according to whether the direction families (F1,...,Fr) are 2-coherent.