Applications of Sparse Hypergraph Colorings

Many problems in extremal combinatorics can be reduced to determining the independence number of a specific auxiliary hypergraph. We present two such problems, one from discrete geometry and one from hypergraph Tur\'an theory. Using results on hypergraph colorings by Cooper-Mubayi and Li-Postle, we demonstrate that for those two problems the trivial lower bound on the independence number can be improved upon: Erd{o}s, Graham, Ruzsa and Taylor asked to determine the largest size, denoted by $g(n)$, of a subset P of the grid [n]² such that every pair of points in P span a different slope. Improving on a lower bound by Zhang from 1993, we show that g(n)=Ω ( n2/3 (log log n)1/3 log1/3n ). Let Hʳ₃ denote an r-graph with $r+1$ vertices and $3$ edges. Recently, Sidorenko proved the following lower bounds for the Tur\'an density of this r-graph: π(Hʳ₃)≥ r⁻² for every r, and π(Hʳ₃)≥ (1.7215 - o(1)) r⁻². We present an improved asymptotic bound: π(Hʳ₃)=Ω(r⁻² log1/2 r ).