Tag Archives: Alon-Furedi

A coding theoretic application of the Alon-Füredi theorem

The Alon-Füredi theorem is something that I have written a lot about in this blog. I spent a considerable amount of time on this theorem during my PhD. In fact, it’s generalisation that I obtained and it’s applications in finite … Continue reading

Posted in Coding Theory, Combinatorics, Extremal Combinatorics, Finite Geometry, Polynomial Method | Tagged , , , , , | 2 Comments

Covering the binary hypercube

A finite grid is a set , where is a field and each is a finite subset of . The minimum number of hyperplanes required to cover can easily be shown to be , with the hyperplanes defined by , … Continue reading

Posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Polynomial Method | Tagged , , , , , , , , , , | 1 Comment

The footprint bound

Studying the set of common zeros of systems of polynomial equations is a fundamental problem in algebra and geometry. In this post we will look at estimating the cardinality of the set of common zeros, when we already know that … Continue reading

Posted in Coding Theory, Combinatorics, Polynomial Method | Tagged , , , , , , , | 1 Comment

Applications of Alon-Furedi to finite geometry

In a previous post I discussed how the Alon-Furedi theorem serves as a common generalisation of the results of Schwartz, DeMillo, Lipton and Zippel. Here I will show some nice applications of this theorem to finite geometry (reference: Section 6 of my … Continue reading

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged , , | 1 Comment

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 pigeonhole principle. And it’s … Continue reading

Posted in Combinatorics, Polynomial Method | Tagged , , , | 8 Comments

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 . It turns out that this combinatorial function is linked … Continue reading

Posted in Combinatorics, Polynomial Method | Tagged , , , | 4 Comments

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 … Continue reading

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged , , , | 5 Comments