Lecture: Special Topics algebra and discrete mathematics (368.159, S25)
The Polynomial Method for Combinatorial Problems
Course instructor:
John Schmitt, Middlebury College, VT, USA; during summer term 2025 visiting professor
and research fellow at JKU,
with assistance of
Schedule:
See KUSSS.
Contact for organisational issues:
E-mail
to E. Aichinger,
Science Park 2, Room SP2 0370,
e-mail
to the administration office of the Institute for Algebra.
Content:
Over the past few decades, the polynomial method has become a formidable tool for solving a wide range of problems coming from additive and extremal combinatorics, (combinatorial) number theory, graph coloring, incidence geometry, and more. While not alone in this method, the Combinatorial Nullstellensatz due to the prize-winning mathematician Noga Alon is a powerful one, with many generalizations of it. This theorem and many of its relatives state that a multivariate polynomial of bounded complexity - where complexity is usually measured in terms of its degree, though one may also the number of monomials it contains - cannot vanish on a `large enough’ grid. Quantitative versions of this type of statement are of particular interest. In particular, we will cover:
- Nullstellensätze, in particular Alon's Combinatorial
Nullstellensatz and its generalizations.
- Applications of CN where a generalization of it has been used, particularly Schmitt's recent work using Nica's generalization.
- The Alon-Furedi Theorem (which is a quantitative version of CN), its generalizations and applications to hyperplane coverings.
- The polynomial method in in finite geometry, in particular in
counting problems for incidence structures.
Relevant literature:
- N. Alon, Combinatorial Nullstellensatz,
Recent trends in combinatorics (Mátraháza, 1995).
Combin. Probab. Comput. 8 (1999), no. 1-2, 7–29.
[link]
- An introduction to the Combinatorial Nullstellensatz
(lecture on April 29, 2025)
[pdf].
- Lecture notes on Commutative Algebra and Gröbner bases
[pdf]
- Lecture on the "No 3 Queens in
a Line problem" by J. Schmitt.
- Paper on the "No 3 Queens in a Line problem"
by Alec S. Cooper, Oleg Pikhurko, John R. Schmitt, Gregory S. Warrington.
- Paper on the "No 3 Queens in a Line problem" by
Seunghwan Oh, John R. Schmitt, Xianzhi Wang.
- Structured and Punctured Nullstellensätze by Aichinger, Schmitt, Zhan.
- Talk on Nullstellensätze.
Prerequisites:
A course in abstract algebra so that polynomial rings is a familiar idea and an interest in combinatorial problems broadly construed.
Organisation:
A first meeting took place on Tuesday, 29.04.2025, 10:15-11:45 in
HS 11.
The lecture usually takes place on Thursday 10:15-11:45, but
there are exceptions. The exact schedule can be found
on KUSSS.
Page maintained by Erhard Aichinger.