| 1. |
- Eriksen, Niklas, 1974-, et al.
(författare)
-
Diagonal checker-jumping and Eulerian numbers for color-signed permutations
- 2000
-
Ingår i: The Electronic Journal of Combinatorics. - Clemson, USA : Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 7
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce color-signed permutations to obtain a very explicit combinatorial interpretation of the q-Eulerian identities of Brenti and some generalizations. In particular, we prove an identity involving the golden ratio, which allows us to compute upper bounds on how high a checker can reach in a classical checker-jumping problem, when the rules are relaxed to allow also diagonal jumps.
|
|
| 2. |
- Eriksson, Henrik, et al.
(författare)
-
Conjugacy of Coxeter elements
- 2009
-
Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 16:2
-
Tidskriftsartikel (refereegranskat)abstract
- For a Coxeter group (W, S), a permutation of the set S is called a Coxeter word and the group element represented by the product is called a Coxeter element. Moving the first letter to the end of the word is called a rotation and two Coxeter elements are rotation equivalent if their words can be transformed into each other through a sequence of rotations and legal commutations. We prove that Coxeter elements are conjugate if and only if they are rotation equivalent. This was known for some special cases but not for Coxeter groups in general.
|
|
| 3. |
- Eriksson, Henrik, et al.
(författare)
-
Conjugacy of Coxeter elements
- 2009
-
Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 16:2, s. R4-
-
Tidskriftsartikel (refereegranskat)
|
|
| 4. |
- Eriksson, Henrik, et al.
(författare)
-
Dense packing of patterns in a permutation
- 2007
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 11:3-4, s. 459-470
-
Tidskriftsartikel (refereegranskat)abstract
- We study the length L-k of the shortest permutation containing all patterns of length k. We establish the bounds e(-2)k(2) < L-k <= (2/3 + o(1))k(2). We also prove that as k there are permutations of length (1/4+o(1))k(2) containing almost all patterns of length k.
|
|
| 5. |
- Eriksson, Henrik, et al.
(författare)
-
Exact expectations for random graphs and assignments
- 2003
-
Ingår i: Combinatorics, probability & computing. - 0963-5483 .- 1469-2163. ; 12, s. 401-412
-
Tidskriftsartikel (refereegranskat)abstract
- 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 the expected length of the corresponding minimal spanning forest.For a random bipartite graph we give a formula for the expected time at which a k-assignment appears. This result has a bearing on the random assignment problem.
|
|
| 6. |
- Eriksson, Henrik, et al.
(författare)
-
Expected inversion number after k adjacent transpositions
- 2000
-
Ingår i: Formal Power Series and Algebraic Combinatorics. - 3540672478 ; , s. 677-685
-
Konferensbidrag (refereegranskat)abstract
- We give expressions for the expected number of inversions after t random adjacent transpositions have been performed on the identity permutation in Sn+1 The problem is a simplification of a problem motivated by genome evolution. For a fixed t and for all n greater than or equal to t, the expected number of inversions after t random adjacent transpositions isE-nt = t - 2/n ((t)(2)) + Sigma(r=2)(t) (-1)(r)/n(r) [2(r)C(r)((t)(r+1)) + 4d(r) ((t)(r))]where d(2) = 0, d(3) = 1, d(4) = 9, d(5) = 69,... is a certain integer sequence. An important part of the our method is the use of a heat. conduction analogy of the random walks, which guarantees certain properties of the solution.
|
|
| 7. |
- Eriksson, Henrik, et al.
(författare)
-
Note on the lamp lighting problem
- 2001
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 27:03-feb, s. 357-366
-
Tidskriftsartikel (refereegranskat)abstract
- We answer some questions concerning the so-called sigma -game of Sutner [Linear cellular automata and the Garden of Eden, Math. Intelligencer 11 (1989), 49-53]. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex with an edge directed to the lamp. For example, we show that every configuration of lamps can be lit if and only if the number of complete matchings in the graph is odd. In the special case of an orthogonal grid one gets a criterion for whether the number of monomer-dimer tilings of an m x n grid is odd or even.
|
|
| 8. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)abstract
- Sorting a permutation by block moves is a task that every bridge player has to solve every time she picks up a new hand of cards. It is also a problem for the computational biologist, for block moves are a fundamental type of mutation that can explain why genes common to two species do not occur in the same order in the chromosome, It is not known whether there exists an optimal sorting procedure running in polynomial time. Bafna and Pevzner gave a polynomial time algorithm that sorts any permutation of length n in at most 3n/4 moves. Our new algorithm improves this to [(2n - 2)/3] for n greater than or equal to 9. For the reverse permutation, we give an exact expression for the number of moves needed, namely [(n + 1)/2]. Computations of Bafha and Pevzner up to n = 10 seemed to suggest that this is the worst case; but as it turns out, a first counterexample occurs for n = 13, i.e. the bridge player's case. Professional card players never sort by rank, only by suit. For this case, we give a complete answer to the optimal sorting problem.
|
|
| 9. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand.
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)
|
|
| 10. |
- Eriksson, Henrik, et al.
(författare)
-
Words with intervening neighbours in infinite Coxeter groups are reduced
- 2010
-
Ingår i: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 17:1, s. N9-
-
Tidskriftsartikel (refereegranskat)abstract
- Consider a graph with vertex set S. A word in the alphabet S has the intervening neighbours property if any two occurrences of the same letter are separated by all its graph neighbours. For a Coxeter graph, words represent group elements. Speyer recently proved that words with the intervening neighbours property are reduced if the group is infinite and irreducible. We present a new and shorter proof using the root automaton for recognition of reduced words.
|
|
