3 papers
math.CO2004
Note on the lamp lighting problem
Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand
We answer some questions concerning the so called sigma-game of Sutner. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex w…
math.CO2004
Exact expectations for random graphs and assignments
Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand
For a random graph on n vertices where the edges appear with individual rates, we give exact formulas for the expected time at which the number of components has gone down to k and…
math.CO2004
Expected number of inversions after a sequence of random adjacent transpositions
Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand
In the evolution of a genome, the gene sequence is sometimes rearranged, for example by transposition of two adjacent gene blocks. In biocombinatorics, one tries to reconstruct the…