| 1. |
- 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.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- Enquist, Magnus, et al.
(författare)
-
One cultural parent makes no culture
- 2010
-
Ingår i: Animal Behaviour. - : Elsevier BV. - 0003-3472 .- 1095-8282. ; 79:6, s. 1353-1362
-
Tidskriftsartikel (refereegranskat)abstract
- The ability to acquire knowledge and skills from others is widespread in animals and is commonly thought to be responsible for the behavioural traditions observed in many species. However, in spite of the extensive literature on theoretical analyses and empirical studies of social learning, little attention has been given to whether individuals acquire knowledge from a single individual or multiple models. Researchers commonly refer to instances of sons learning from fathers, or daughters from mothers, while theoreticians have constructed models of uniparental transmission, with little consideration of whether such restricted modes of transmission are actually feasible. We used mathematical models to demonstrate that the conditions under which learning from a single cultural parent can lead to stable culture are surprisingly restricted ( the same reasoning applies to a single social-learning event). Conversely, we demonstrate how learning from more than one cultural parent can establish culture, and find that cultural traits will reach a nonzero equilibrium in the population provided the product of the fidelity of social learning and the number of cultural parents exceeds 1. We discuss the implications of the analysis for interpreting various findings in the animal social-learning literature, as well as the unique features of human culture.
|
|
| 5. |
- Eriksson, Kimmo, 1967-, et al.
(författare)
-
An Exponential Limit Shape of Random q-proportion Bulgarian Solitaire
- 2018
-
Ingår i: Integers. - 1553-1732. ; 18
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce pn-random qn-proportion Bulgarian solitaire (0 < pn, qn ≤ 1), playedon n cards distributed in piles. In each pile, a number of cards equal to the propor-tion qn of the pile size rounded upward to the nearest integer are candidates to bepicked. Each candidate card is picked with probability pn, independently of othercandidate cards. This generalizes Popov’s random Bulgarian solitaire, in whichthere is a single candidate card in each pile. Popov showed that a triangular limitshape is obtained for a fixed p as n tends to infinity. Here we let both pn and qnvary with n. We show that under the conditions q2npnn/log n → ∞ and pnqn → 0 asn → ∞, the pn-random qn-proportion Bulgarian solitaire has an exponential limitshape.
|
|
| 6. |
- Eriksson, Kimmo, et al.
(författare)
-
Asymmetric equilibria in dynamic two-sided matching markets with independent preferences
- 2008
-
Ingår i: International Journal of Game Theory. - : Springer Science and Business Media LLC. - 0020-7276 .- 1432-1270. ; 36, s. 421-440
-
Tidskriftsartikel (refereegranskat)abstract
- A fundamental fact in two-sided matching is that if amarket allows several stable outcomes, then one is optimal for all men in the sense that no man would prefer another stable outcome.We study a related phenomenon of asymmetric equilibria in a dynamic market where agents enter and search for a mate for at most n rounds before exiting again. Assuming independent preferences, we find that this game has multiple equilibria, some of which are highly asymmetric between sexes. We also investigate how the set of equilibria depends on a sex difference in the outside option of not being mated at all.
|
|
| 7. |
- Eriksson, Kimmo, et al.
(författare)
-
Bentley’s conjecture on popularity toplist turnover under random copying
- 2010
-
Ingår i: The Ramanujan journal. - : Springer Science and Business Media LLC. - 1382-4090 .- 1572-9303. ; 23, s. 371-396
-
Tidskriftsartikel (refereegranskat)abstract
- Bentley et al studied the turnover rate in popularity toplists in a ’random copying’ model of cultural evolution. Based on simulations of a model with population size N, list length ℓ and invention rate μ, they conjectured a remarkably simple formula for the turnover rate: ℓ√μ. Here we study an overlapping generations version of the random copying model, which can be interpreted as a random walk on the integer partitions of the population size. In this model we show that the conjectured formula, after a slight correction, holds asymptotically.
|
|
| 8. |
- Eriksson, Kimmo, 1967-, et al.
(författare)
-
Limit shapes of stable and recurrent configurations of a generalized bulgarian solitaire
- 2020
-
Ingår i: Online Journal of Analytic Combinatorics. - : Department of Computer Science. - 1931-3365. ; :15
-
Tidskriftsartikel (refereegranskat)abstract
- Bulgarian solitaire is played on n cards divided into several piles; a move consists of picking one card from each pile to form a new pile. This can be seen as a process on the set of integer partitions of n: If sorted configurations are represented by Young diagrams, a move in the solitaire consists of picking all cards in the bottom layer of the diagram and inserting the picked cards as a new column. Here we consider a generalization, L-solitaire, wherein a fixed set of layers L (that includes the bottom layer) are picked to form a new column. L-solitaire has the property that if a stable configuration of n cards exists it is unique. Moreover, the Young diagram of a configuration is convex if and only if it is a stable (fixpoint) configuration of some L-solitaire. If the Young diagrams representing card configurations are scaled down to have unit area, the stable configurations corresponding to an infinite sequence of pick-layer sets (L1, L2, . . .) may tend to a limit shape φ. We show that every convex φ with certain properties can arise as the limit shape of some sequence of Ln. We conjecture that recurrent configurations have the same limit shapes as stable configurations. For the special case Ln = {1, 1 + ⌊1/qn⌋, 1 + ⌊2/qn⌋, . . . }, where the pick layers are approximately equidistant with average distance 1/qn for some qn ∈ (0, 1], these limit shapes are linear (in case nq2n → 0), exponential (in case nq2n → ∞), or interpolating between these shapes (in case nq2n → C > 0).
|
|
| 9. |
- Eriksson, Kimmo, et al.
(författare)
-
Limiting shapes of birth-and-death processes on Young diagrams
- 2012
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 48:4, s. 575-602
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a family of birth processes and birth-and-death processes on Young diagrams of integer partitions of n. This family incorporates three famous models from very different fields: Rost's totally asymmetric particle model (in discrete time), Simon's urban growth model, and Moran's infinite alleles model. We study stationary distributions and limit shapes as n tends to infinity, and present a number of results and conjectures.
|
|
| 10. |
- Eriksson, Kimmo, et al.
(författare)
-
On two theorems of Quinzii and rent controlled housing allocation in Sweden
- 2007
-
Ingår i: International Game Theory Review. - 0219-1989. ; 3:9, s. 515-526
-
Tidskriftsartikel (refereegranskat)abstract
- The Swedish rent control system creates a white market for swapping rental contracts and a black market for selling rental contracts. Empirical data suggests that in this black-and-white market some people act according to utility functions that are both discontinuous and locally decreasing in money. We discuss Quinzii's theorem for the nonemptiness of the core of generalized house-swapping games, and show how it can be extended to cover the Swedish game. In a second part, we show how this theorem of Quinzii and her second theorem on nonemptiness of the core in two-sided models are both special cases of a more general theorem.
|
|
