2020/09/30 by Sauermann, Lisa, Wigderson, Yuval · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2010.00077
Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed k≥ 1 and n large with respect to k, what is the minimum possible degree of a polynomial P∈ ℝ[x1,…,xn] with P(0,…,0)≠ 0 such that P has zeroes of multiplicity at least k at all points in \0,1\n∖ \(0,…,0)\? For k=1, a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals n. In this paper, we solve the problem for all k≥ 2, proving that the answer is n+2k-3. As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in ℝn such that each point in \0,1\n∖ \(0,…,0)\ is covered by at least k hyperplanes, but the point (0,…,0) is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.