Irredundant hyperplane covers

MaRDI QIDQ6398455zbMATH OpenFDO

Authors János Nagy, Péter Pál Pach, István Tomon

Publication date 6 May 2022

Abstract: We prove that if $G$ is an abelian group and $H_1{x}_1,dots,H_k{x}_k$ is an irredundant (minimal) cover of $G$ with cosets, then ${\displaystyle }$|G:�igcap_{i=1}^{k}H_{i}|=2^{O(k)}.${\displaystyle }$ This bound is the best possible up to the constant hidden in the $O(cdot)$ notation, and it resolves conjectures of Pyber (1996) and Szegedy (2007). We further show that if $G$ is an elementary $p$-group for some large prime $p$, and $H_1,dots,H_k$ is a sequence of hyperplanes with many repetitions, then the bound above can be improved. As a consequence, we establish a substantial strengthening of the recently solved Alon-Jaeger-Tarsi conjecture: there exists $alpha>0$ such that for every invertible matrix $Minmathbb{F}_p^{nimesn}$ and any set of at most $p^{alpha}$ forbidden coordinates, one can find a vector $xinmathbb{F}_p^n$ such that neither $x$ nor $Mx$ have a forbidden coordinate.

This page was built for publication: Irredundant hyperplane covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398455)