REVIEW 2 cited by
A survey of Zarankiewicz problems in geometry
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
One of the central topics in extremal graph theory is the study of the function $ex(n,H)$, which represents the maximum number of edges a graph with $n$ vertices can have while avoiding a fixed graph $H$ as a subgraph. Tur{\'a}n provided a complete characterization for the case when $H$ is a complete graph on $r$ vertices. Erd{\H o}s, Stone, and Simonovits extended Tur{\'a}n's result to arbitrary graphs $H$ with $\chi(H) > 2$ (chromatic number greater than 2). However, determining the asymptotics of $ex(n, H)$ for bipartite graphs $H$ remains a widely open problem. A classical example of this is Zarankiewicz's problem, which asks for the asymptotics of $ex(n, K_{t,t})$. In this paper, we survey Zarankiewicz's problem, with a focus on graphs that arise from geometry. Incidence geometry, in particular, can be viewed as a manifestation of Zarankiewicz's problem in geometrically defined graphs.
Forward citations
Cited by 2 Pith papers
-
$C_4$-free subgraphs of high degree with geometric applications
A new dichotomy about C4-free induced subgraphs and dense patches yields optimal O(sn) bounds for geometric Zarankiewicz problems and a near-tight semilinear bound.
-
Compact Representation of Semilinear and Terrain-like Graphs
Semilinear and terrain-like graphs on n vertices have biclique covers of size O(n polylog n), while some unit disk graphs require Ω(n^{4/3}) size.
Discussion (0). Continue with ORCID to comment.