| 1. |
- Andrén, Daniel, 1973-
(författare)
-
On the Ising problem and some matrix operations
- 2007
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The first part of the dissertation concerns the Ising problem proposed to Ernst Ising by his supervisor Wilhelm Lenz in the early 20s. The Ising model, or perhaps more correctly the Lenz-Ising model, tries to capture the behaviour of phase transitions, i.e. how local rules of engagement can produce large scale behaviour. Two decades later Lars Onsager solved the Ising problem for the quadratic lattice without an outer field. Using his ideas solutions for other lattices in two dimensions have been constructed. We describe a method for calculating the Ising partition function for immense square grids, up to linear order 320 (i.e. 102400 vertices). In three dimensions however only a few results are known. One of the most important unanswered questions is at which temperature the Ising model has its phase transition. In this dissertation it is shown that an upper bound for the critical coupling Kc, the inverse absolute temperature, is 0.29 for the tree dimensional cubic lattice. To be able to get more information one has to use different statistical methods. We describe one sampling method that can use simple state generation like the Metropolis algorithm for large lattices. We also discuss how to reconstruct the entropy from the model, in order to obtain parameters as the free energy. The Ising model gives a partition function associated with all finite graphs. In this dissertation we show that a number of interesting graph invariants can be calculated from the coefficients of the Ising partition function. We also give some interesting observations about the partition function in general and show that there are, for any N, N non-isomorphic graphs with the same Ising partition function. The second part of the dissertation is about matrix operations. We consider the problem of multiplying them when the entries are elements in a finite semiring or in an additively finitely generated semiring. We describe a method that uses O(n3 / log n) arithmetic operations. We also consider the problem of reducing n x n matrices over a finite field of size q using O(n2 / logq n) row operations in the worst case.
|
|
| 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, s. R4-
-
Tidskriftsartikel (refereegranskat)
|
|
| 3. |
- 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.
|
|
| 4. |
- 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.
|
|
| 5. |
- Eriksson, Henrik, et al.
(författare)
-
Level Sizes of the Bulgarian Solitaire Game Tree
- 2017
-
Ingår i: The Fibonacci quarterly. - : The Fibonacci Association. - 0015-0517. ; 55:3, s. 243-251
-
Tidskriftsartikel (refereegranskat)abstract
- Bulgarian solitaire is a dynamical system on integer partitions of n which converges to a unique fixed point if n=1+2+...+k is a triangular number. There are few results about the structure of the game tree, but when k tends to infinity the game tree itself converges to astructure that we are able to analyze. Its level sizes turns out to be a bisection of the Fibonacci numbers. The leaves in this tree structure are enumerated using Fibonacci numbers as well.We also demonstrate to which extent these results apply to the case when k is finite.
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
