Tags » Polynomial Method

The Erdős-Ginzburg-Ziv theorem

Let be  a sequence of integers (not necessarily distinct). Then there exists a subsequence of the sum of whose elements is divisible by . 

This is one of the first problems I saw when learning the… 658 more words

Combinatorics

Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization

In the post Balls in Bins I wrote about a combinatorial function which denotes the minimum value of the product among all distributions of balls (so ) in bins with the constraints . 728 more words

Combinatorics

A timeline of the polynomial method up-to combinatorial nullstellensatz

Over the past 30-40 years, the so-called polynomial method has developed into a powerful tool in combinatorics and (additive) number theory. There has been a lot of recent interest in it after Dvir’s  … 685 more words

Combinatorics

On Zeros of a Polynomial in a Finite Grid: the Alon-Furedi bound

My joint paper with Aditya Potukuchi, Pete L. Clark and John R. Schmitt is now up on arXiv: arXiv:1508.06020.

This work started a few months back when I emailed Pete and John, pointing out an easy generalization of Chevalley-Warning theorem using something known as the… 244 more words

Combinatorics

Chevalley-Warning Theorem and Blocking Sets

The classical Chevalley-Warning theorem gives us a sufficient condition for a system of polynomial equations over a finite field to have common solutions. Affine blocking sets… 668 more words

Polynomial Method

Balls in Bins

When I was learning combinatorics for the first time (I was probably 16) there was this problem about distributing balls in bins (or urns) that I came across. 535 more words

Combinatorics

The Kakeya problem

The original Kakeya needle problem  is to  find the least amount of area required to continuously rotate a unit line segment in the (Euclidean) plane by a full rotation… 978 more words

Finite Geometry