On polynomials that vanish to high order on most of the hypercube

29-Jan-2021, 14:00-15:00 (3 years ago)

Abstract: Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed k and n large with respect to $k$, what is the minimum possible degree of a polynomial $P$ in $R[x_1,...,x_n]$ such that $P(0,…,0)$ is non-zero and such that P has zeroes of multiplicity at least $k$ at all points in $\{0,1\}^n$ except the origin? For $k=1$, a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals $n$. We solve the problem for all $k>1$, proving that the answer is $n+2k−3$. Joint work with Yuval Wigderson.

combinatorics

Audience: researchers in the topic


Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.

Organizers: Jan Grebik, Oleg Pikhurko
Curator: Hong Liu*
*contact for this listing

Export talk to