2019/04/29 by Alexander Clifton, Hao Huang, Clifton, Alexander +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1904.12885
openalex publication_date 2019/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we consider the following problem: what is the minimum number of affine hyperplanes in ℝn, such that all the vertices of \0, 1\n ∖ \0\ are covered at least k times, and 0 is uncovered? The k=1 case is the well-known Alon-Füredi theorem which says a minimum of n affine hyperplanes is required, proved by the Combinatorial Nullstellensatz. We develop an analogue of the Lubell-Yamamoto-Meshalkin inequality for subset sums, and completely solve the fractional version of this problem, which also provides an asymptotic answer to the integral version for fixed n and k → ∞. We also use a Punctured Combinatorial Nullstellensatz developed by Ball and Serra, to show that a minimum of n+3 affine hyperplanes is needed for k=3, and pose a conjecture for arbitrary k and large n.