Applications of Sparse Hypergraph Colorings

Abstract

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án 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ős, Graham, Ruzsa and Taylor asked to determine the largest size, denoted by $g(n)$, of a subset $P$ of the grid $[n{]}^2$ 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)=\Omega \left(\frac{n^{2/3}(\log \log n{)}^{1/3}}{{\log }^{1/3}n}\right).$$ Let $H_3^r$ denote an $r$-graph with $r+1$ vertices and $3$ edges. Recently, Sidorenko proved the following lower bounds for the Turán density of this $r$-graph: $\pi (H_3^r)\ge r^{-2}$ for every $r$, and $\pi (H_3^r)\ge (1.7215-o(1))r^{-2}$. We present an improved asymptotic bound: $\pi (H_3^r)=\Omega \left(r^{-2}{\log }^{1/2}r\right).$