The Combinatorial Nullstellensatz and DFT on Perfect Matchings in Bipartite Graphs

Abstract

The paper begins with a simple circular lock problem that shows how the Combinatorial Nullstellensatz relates to the discrete Fourier Transform.Specifically, the lock shows a relationship between detecting perfect matchings in bipartite graphs using the Combinatorial Nullstellensatz and detecting a maximum rank independent set in the intersection of two matroids in the Fourier transform of a specially chosen function. Finally, an application of the uncertainity principle computes a lower bound for the product of perfect matchings and the number of independent sets.