Ilse Fischer's Research interests:


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.