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\'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\H{o}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^r_3$ 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: $\pi(H^r_3)\geq r^{-2}$ for every $r$, and $\pi(H^r_3)\geq (1.7215 - o(1)) r^{-2}$. We present an improved asymptotic bound: $\pi(H^r_3)=\Omega\left(r^{-2} \log^{1/2} r \right).$

Locations

• arXiv (Cornell University) - View - PDF