| Currently I am focusing on
two projects in my mathematical research.
Polynomial enumeration
formulas:You may
have observed that many enumeration formulas are polynomials in a certain
parameter. For example the number of subsets of {1,2,...,n} with k elements is
given by the binomial coefficient, which can be seen as a polynomial in n
for fixed k. Many of these polynomial enumeration formulas factorise
totally into linear factors over Z, such as the binomial coefficient
n*(n-1)*...*(n-k+1)/k!. Combinatorialists like such formulas, especially when the
reason for such a nice polynomial formula is not so obvious. My approach to
prove such a formula is the following. It is divided into three steps.
1. Extension of the
combinatorial interpretation: Suppose
we are given combinatorial objects we want to enumerate which
depend on an integer parameter n and we suspect that there
exists an enumeration formula of these objects which is
polynomial in n and factorises into distinct linear factors over
Z. Typically the admissible domain of n is a set S of
non-negative integers. In the first step of our method we have
to find (most likely new) combinatorial objects indexed by an
arbitrary integer n which are in bijection
with the original objects for n in S.
|
2. The extending objects
are enumerated by a polynomial: The
extension of the combinatorial interpretation in the previous
step has to be chosen such that we are able to prove that the
new objects are enumerated by a polynomial in n. Moreover the
degree of this polynomial has to be
computed.
|
| 3. Exploring 'natural'
linear factors: Finally one has to
find the n's for which there exist none of these objects, i.e.
one has to compute the (integer) zeros of the polynomial.
Typically these zeros will not lie in S, which made the
extension in Step 1 necessary. Moreover one has to find a
non-zero evaluation of the polynomial which is easy to compute, and
together with the zeros the polynomial is finally computable. |
Of course such a method is worth nothing without
application! I have applied this method to
give a refinement of the Bender-Knuth (ex-)Conjecture
and with this an elementary proof of the Bender-Knuth (ex-)Conjecture,
see math.CO/0301103.
And now I have some fun while working on other applications of
this method...
Pfaffian graphs:
The enumeration of perfect matchings in a vertex-edge graph is
known to be an NP-hard problem. In the middle of the 20th century the Physicist
Kasteleyn has developed an elegant method for the enumeration of perfect
matchings in planar graphs which (roughly) reduces the problem to the computation
of a determinant. However, his method can be extended to certain non-planar
graphs. The aim of this project is a characterisation of the graphs to
which Kasteleyn's method can be extended. Such graphs are said to be
Pfaffian.
I am working on this project together with Charles
Little.
So far we have succeeded in giving a characterisation of
Pfaffian near bipartite graphs in terms of forbidden subgraphs, see math.CO/9909026 and math.CO/0002062. And in math.CO/0203281 we were able to
solve a related, but easier problem.
See
also my papers.
|