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: Erdos, 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) = (n^2/3 (n) ^{1/3 } ^{1/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^-2 for every r, and (Hʳ₃) (1. 7215 - o (1) ) r^-2. We present an improved asymptotic bound: (Hʳ₃) = (r^-2 ^1/2 r).