University of Idaho
Department of Mathematics Colloquia

Thursday, February 14, 2008

3:30 p.m. in TLC 031
Refreshments in Brink 330 at 3:00

Recent Progress Applying Alon's Combinatorial Nullstellensatz

by

Andre Kezdy
Department of Mathematics
University of Louisville

Abstract:

To apply successfully the "combinatorial nullstellensatz" technique, one must find a nonzero coefficient in the expansion of a multivariate polynomial a nontrivial task typically (NP-hard actually). These coefficients can be viewed as frequencies to which one can listen for the presence of a combinatorial object. To hone this method, my recent work with several collaborators has focused on several benchmark problems, some easy and several hard, that embody different combinatorial characteristics that we hope will reveal deeper applications. I will give a brief introduction to Alon's combinatorial nullstellensatz and then describe progress applying the technique on these fronts.

As an example of an "easy" problem, we chose the problem of detecting a perfect matching in a bipartite graph via this technique. I will describe joint work with Hunter Snevily and my graduate student, Tim Brauch, that links the nullstellensatz method, in this case, to matroid intersection, the discrete Fourier transform, and a discrete version of the Wronskian known as the Casorati determinant.

As an example of "hard" problems, we chose several open problems, two of which I will mention in this talk. These problems remain open, but our nullstellensatz approach has opened new frontiers, with a plethora of open problems. The first problem is an old conjecture of Kotzig that states that every tree on n edges cyclically decomposes the complete graph on 2n+1 vertices. The second problem is also an old conjecture stating that the middle levels of the boolean lattice have a hamiltonian cycle.