Covering grids with multiplicity

DOI10.5070/C63362787MaRDI QIDQ6204684zbMATH OpenFDO

Authors Anurag Bishnoi, Simona Boyadzhiyska, Shagnik Das

Publication date 2 April 2024

Published in Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.00825

zbMATH Keywords

Alon-Füredi theoremcombinatorial geometrygrid coveringlinear programming

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Abstract: Given a finite grid in $mathbb{R}^2$, how many lines are needed to cover all but one point at least $k$ times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball--Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball--Serra and provide an asymptotic answer for almost all grids. For the standard grid $0,ldots,n-1imes0,ldots,n-1$, we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments.

Recommendations

• Economical coverings of sets of lattice points
• On a problem about covering lines by squares
• Covering lattice points by subspaces and counting point-hyperplane incidences
• Covering lattice points by subspaces and counting point-hyperplane incidences
• Sets of rich lines in general position

Cites work

• Combinatorial Nullstellensatz
• Covering all points except one
• Covering finite fields with cosets of subspaces
• Covering the cube by affine hyperplanes
• Graph polynomials and group coloring of graphs
• scientific article; zbMATH DE number 6603592 (Why is no real title available?)
• Intersection sets in AG(n,q) and a characterization of the hyperbolic quadric in PG(3,q)
• On almost \(k\)-covers of hypercubes
• On the sharpness of Bruen's bound for intersection sets in Desarguesian affine spaces
• On zeros of a polynomial in a finite grid
• Partitions of vector spaces
• Polynomial multiplicities over finite fields and intersection sets
• Polynomials that vanish to high order on most of the hypercube
• Punctured combinatorial Nullstellensätze
• The \(n\)-queens completion problem
• Three combinatorial perspectives on minimal codes
• Understanding and using linear programming

Cited in

(2)

• Minimal number of points on a grid forming line segments of equal length
• Simple proofs for lattice coverings and sparse tensors

This page was built for publication: Covering grids with multiplicity

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