




I can do just what I wish [in my research] ... The king calls me his professor, and I think I am the happiest man in the world.
Leonhard Euler
Current active fields of research are
A placement of chess pieces on a chessboard is called dominating if each free square of the chessboard is under attack by at least one piece.
How many queens do you need to dominate the 8x8 board? How many queens for an m x n board?
Domination problems can be formulated for general graphs. A dominating subset of a graph is a subset S of the vertices V of a graph, such that each vertex v of the graph is either
element of S or adjacent to an element of S. The link to chess domination problems is given by the fact, that a chess piece defines a graph whose vertices are given by squares of the board, and two
vertices are linked by an edge if and only if they are connected by a legal move of the piece.
I solved the domination problem for rooks by computing the domination polynomial, i.e. the generating function for the dominating sets of the m x n rook graph. Cris Moore and I proved a surprising symmetry in the domination problem for kings. And I found a fast algorithm to compute domination polynomials for the grid, the cylnder, the torus and the king graph.
Click here to get the papers or download the data.
Percolation (from Latin percolare, "to filter" or "trickle through") refers to the movement and filtering of fluids through porous materials. In percolation theory, the porous material is modeled as a lattice or graph, on which the open pores are randomly selected vertices or edges at a given density. Percolation models are the simplest models in statistical physics that have a phase transition with universal critical exponents. My research on percolation so far focussed on numerical and rigorous results on the clusterdensity, i.e. the average number of connected clusters of pores per lattice site and on computing precise numerical values for the percolation threshold in hyperbolic lattices.
Click here to learn more, read the papers or download the data.
The stable matching problem is a prototype model in economics and social sciences where agents act selfishly to optimize their own satisfaction, subject to mutually conflicting constraints. A paradigmatic example is the stable roommates problem. Consider an even number n of participants. Each of the participants ranks all the others in strict order of preference. A matching is a set of n/2 disjoint pairs of participants. A matching is stable if there is no pair of unmatched participants who both prefer each other to their partner in the matching. Such a pair is said to block the matching. The stable roommates problem is to find a stable matching. The name originates from the problem to assign students to the double bedroomes of a dormitory. Another application is the formation of cockpit crews from a pool of pilots.
It is well known that not all instances of the stable roommates problem admit a solution. My research focuses on computing the probability p_{n} that a random instance with n participants admits a solution. For that I developped a sublinear algorithm to solve large random instances of the stable roommates problem. I also used a computer algebra system to compute p_{n} exactly for small instances.
Click here to learn more, read the papers or download the data.
A lattice animal is a finite set of connected vertices of a regular lattice. Lattice animals on the square lattice are better known as polyominoes. On the cubic lattice they are called polycubes. The figure on the left shows all polycubes of size n = 4.
The enumeration of lattice animals is a longstanding combinatorial problem that has some motivations in physics, for example in the study of branched polymers and percolation. For most lattices we don't know a formula for the number of lattice animals of a given size n, and all we can do is to count them one by one. Since the number of lattice animals grows exponentially with n, this counting is a demanding task, even with a fast computer.
We develop fast algorithms for the enumeration of lattice animals and we run these algorithms on parallel computers. We also work on combinatorial arguments that complement computer based enumerations.
Click here to learn more, read the papers or download the data.
Well, sometimes it doesn't work. Every now and then a well designed, well tested and well established random number generator fails to fake randomness in a simulation. A famous example is the Ferrenberg affair. Since a well designed and well tested random number generator has no obvious flaws, explaining the failure requires a forensic investigation. It took more than 10 years and various attempts before the Ferrenberg affair could finally be settled.
The theoretical background of the Ferrenberg affair was Heiko Bauke's and mine first contribution to the field. A second paper demonstrates the bias in some popular random number generators  pseudo random coins show more heads than tails. To our surprise, both papers receive considerable public attention.
A nice account of this interdisciplinary and highly active field of research
has been given by
Marc Mézard in Science 301, 1685 (2003), also
available online.
My contributions
to the field concentrate on the
number partitioning problem,
and recently on the
satisfiability problem.
The Bernasconi model is completely deterministic in a sense that there is no explicit or quenched disorder like in spinglasses. The energy of a configuration is the sum of the square of all correlation coefficients of the spin sequence. The ground states of the Bernasconi model are low autocorrelation binary sequences. As such, the ground states are by definition highly disordered, despite the absence of any explicit disorder. This selfinduced disorder resembles the situation in real glasses. In fact, the Bernasconi model exhibits features of a glass transition like a jump in the specific heat and slow dynamics and ageing.
The link to physics has not solved the problem of constructing binary sequences with minimal autocorrelations, however. Exhaustive enumeration of all 2^{N} sequences of length N still is the only means to get true ground states of the Bernasconi model. A clever branch and bound algorithm, running several days on our 160CPU Beowulf cluster solved the problem up to N=60, which still marks the world record.
For the Bernasconi model with periodic boundary conditions more can be done. The tight connection between the correlations of periodic binary sequences and mathematical objects called cyclic difference sets can be exploited to get some exact results on the ground states.





© by Stephan Mertens (Datenschutzerklärung)
updated on Sunday, July 28th 2024, 15:28:50 CET;