The Price of Almost Navigability
This work proves a matching lower bound, establishing the optimality of their construction and giving a complete characterization of the sparsity achievable by almost-navigable graphs, and reveals a surprising connection between almost navigability and the classical Zarankiewicz problem of constructing dense graphs wit...