The Kernel Method

Description

The field of enumerative combinatorics is not only a great source of complicated expressions and functional equations, but also a great source of tricks, treatments, and transformations for simplifying complicated expressions or solving complicated functional equations. A particularly nice "trick" due to Knuth applies to a certain kind of functional equations that tends to arise in lattice path enumeration problems. The trick has proven so fruitful that it has been extended and generalized in several respects and is now commonly known as the kernel method. Together with Alin Bostan (INRIA), we have recently used the kernel method in combination with heavy computer algebra calculations for proving that a power series describing a certain lattice count (so-called Gessel walks) is algebraic. This result is interesting not only for combinatorial reasons but also from the viewpoint of symbolic computation, as it would have been impossible to do the job without the use of efficient implementations of efficient algorithms on efficient hardware. In the talk, we will explain the kernel method and discuss typical combinatorial situations in which it is applicable. Then we describe how computer algebra can prove combinatorial theorems based on the kernel method and point out which computational difficulties may arise in this context.

Period	10 Feb 2010
Event title	unbekannt/unknown
Event type	Other
Location	United StatesShow on map