Subspace coverings with multiplicities

Journal Article (2023)
Author(s)

A. Bishnoi (TU Delft - Discrete Mathematics and Optimization)

Simona Boyadzhiyska (University of Birmingham)

Shagnik Das (National Taiwan University)

Tamás Mészáros (Freie Universität Berlin)

Research Group
Discrete Mathematics and Optimization
Copyright
© 2023 A. Bishnoi, Simona Boyadzhiyska, Shagnik Das, Tamás Mészáros
DOI related publication
https://doi.org/10.1017/S0963548323000123
More Info
expand_more
Publication Year
2023
Language
English
Copyright
© 2023 A. Bishnoi, Simona Boyadzhiyska, Shagnik Das, Tamás Mészáros
Research Group
Discrete Mathematics and Optimization
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

We study the problem of determining the minimum number of affine subspaces of codimension that are required to cover all points of at least times while covering the origin at most times. The case is a classic result of Jamison, which was independently obtained by Brouwer and Schrijver for. The value of also follows from a well-known theorem of Alon and FÜredi about coverings of finite grids in affine spaces over arbitrary fields. Here we determine the value of this function exactly in various ranges of the parameters. In particular, we prove that for we have, while for we have, and obtain asymptotic results between these two ranges. While previous work in this direction has primarily employed the polynomial method, we prove our results through more direct combinatorial and probabilistic arguments, and also exploit a connection to coding theory.