mdh.sePublications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Processes on Integer Partitions and Their Limit Shapes
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (MAM)ORCID iD: 0000-0003-1242-3599
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

This thesis deals with processes on integer partitions and their limit shapes, with focus on deterministic and stochastic variants on one such process called Bulgarian solitaire. The main scientific contributions are the following.

Paper I: 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 a structure 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.

Paper II: 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. In a recent generalization, σ-Bulgarian solitaire, the number of cards you pick from a pile is some function σ of the pile size, such that you pick σ(h) < h cards from a pile of size h. Here we consider a special class of such functions. Let us call σ well-behaved if σ(1) = 1 and if both σ(h) and h − σ(h) are non-decreasing functions of h. Well-behaved σ-Bulgarian solitaire has a geometric interpretation in terms of layers at certain levels being picked in each move. It also satisfies that if a stable configuration of n cards exists it is unique. Moreover, if piles are sorted in order of decreasing size then a configuration is convex if and only if it is a stable configuration of some well-behaved σ-Bulgarian solitaire. If sorted configurations are represented by Young diagrams and scaled down to have unit height and unit area, the stable configurations corresponding to an infinite sequence of well-behaved functions (σ1, σ2, ...) may tend to a limit shape Φ. We show that every convex Φ with certain properties can arise as the limit shape of some sequence of well-behaved σn. For the special case when σn(h) = ceil(qnh) for 0 < qn ≤ 1 (where ceil is the ceiling function rounding upward to the nearest integer), these limit shapes are triangular (in case qn2n → 0), or exponential (in case qn2n → ∞), or interpolating between these shapes (in case qn2n → C > 0).

Paper III: We introduce pn-random qn-proportion Bulgarian solitaire (0 < pn,qn ≤ 1), played on n cards distributed in piles. In each pile, a number of cards equal to the proportion qn of the pile size rounded upward to the nearest integer are candidates to be picked. Each candidate card is picked with probability pn, independently of other candidate cards. This generalizes Popov's random Bulgarian solitaire, in which there is a single candidate card in each pile. Popov showed that a triangular limit shape is obtained for a fixed p as n tends to infinity. Here we let both pn and qn vary with n. We show that under the conditions qn2pnn/log n → ∞ and pnqn → 0 as n → ∞, the pn-random qn-proportion Bulgarian solitaire has an exponential limit shape.

Paper IV: We consider two types of discrete-time Markov chains where the state space is a graded poset and the transitions are taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts between the up-directed transition probabilities (an up rule) and the down-directed (a down rule), and we relate these to compatibility between up-and-down chains. This framework is used to prove a conjecture about a limit shape for a process on Young's lattice. Finally, we settle the questions whether the reverse of an up chain is a down chain for some down rule and whether there exists an up or down chain at all if the rank function is not bounded.

##### Place, publisher, year, edition, pages
Västerås: Mälardalen University , 2017.
##### Series
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 223
Mathematics
##### Research subject
Mathematics/Applied Mathematics
##### Identifiers
ISBN: 978-91-7485-316-2 (print)OAI: oai:DiVA.org:mdh-35023DiVA, id: diva2:1082060
##### Public defence
2017-05-05, Delta, Mälardalens högskola, Västerås, 13:15 (English)
##### Supervisors
Available from: 2017-03-15 Created: 2017-03-15 Last updated: 2017-09-28Bibliographically approved
##### List of papers
1. Level Sizes of the Bulgarian Solitaire Game Tree
Open this publication in new window or tab >>Level Sizes of the Bulgarian Solitaire Game Tree
2017 (English)In: The Fibonacci quarterly, ISSN 0015-0517, ISSN 0015-0517, Vol. 55, no 3, p. 243-251Article in journal (Refereed) Published
##### Abstract [en]

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.

##### Place, publisher, year, edition, pages
The Fibonacci Association, 2017
##### Keywords
Bulgarian solitaire
##### National Category
Discrete Mathematics
##### Research subject
Mathematics/Applied Mathematics
##### Identifiers
urn:nbn:se:mdh:diva-35012 (URN)000412356200006 ()2-s2.0-85030458141 (Scopus ID)
##### Funder
Swedish Research Council, 2010-5565 Available from: 2017-03-13 Created: 2017-03-13 Last updated: 2018-02-03Bibliographically approved
2. Limit shapes of stable configurations of a generalized Bulgarian solitaire
Open this publication in new window or tab >>Limit shapes of stable configurations of a generalized Bulgarian solitaire
(English)In: Order, ISSN 0167-8094, E-ISSN 1572-9273, ISSN 0167-8094Article in journal (Other academic) Submitted
##### Abstract [en]

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. In a recent generalization, $\sigma$-Bulgarian solitaire,  the number of cards you pick from a pile is some function $\sigma$ of the pile size, such that you pick $\sigma(h) \le h$ cards from a pile of size h. Here we consider a special class of such functions. Let us call $\sigma$ well-behaved if $\sigma(1)=1$ and if both $\sigma(h)$ and $h-\sigma(h)$ are non-decreasing functions of h. Well-behaved $\sigma$-Bulgarian solitaire has a geometric interpretation in terms of layers at certain levels being picked in each move. It also satisfies that if a stable configuration of n cards exists it is unique. Moreover, if piles are sorted in order of decreasing size ($\lambda_1 \ge \lambda_2\ge \dots$) then a configuration is convex if and only if it is a stable configuration of some well-behaved  $\sigma$-Bulgarian solitaire. If sorted configurations are represented by Young diagrams and scaled down to have unit height and unit area, the stable configurations corresponding to an infinite sequence of well-behaved functions ($\sigma_1, \sigma_2, \dots$) may tend to a limit shape $\phi$. We show that every convex $\phi$ with certain properties can arise as the limit shape of some sequence of well-behaved $\sigma_n$. For the special case when $\sigma_n(h)=\lceil q_n h \rceil$ for $0 < q_n \le 1$, these limit shapes are triangular (in case $q_n^2 n\rightarrow 0$), or exponential (in case $q_n^2 n\rightarrow \infty$), or interpolating between these shapes (in case $q_n^2 n\rightarrow C>0$).

##### Place, publisher, year, edition, pages
Springer Netherlands
##### Keywords
Bulgarian solitaire, Limit shape
##### National Category
Discrete Mathematics
##### Research subject
Mathematics/Applied Mathematics
##### Identifiers
urn:nbn:se:mdh:diva-35013 (URN)
##### Funder
Swedish Research Council, 2010-5565, 621-2009-6090 Available from: 2017-03-13 Created: 2017-03-13 Last updated: 2017-09-28Bibliographically approved
3. An exponential limit shape of random q-proportion Bulgarian solitaire
Open this publication in new window or tab >>An exponential limit shape of random q-proportion Bulgarian solitaire
##### Abstract [en]

We introduce $p_n$-random $q_n$-proportion Bulgarian solitaire ($0), played on n cards distributed in piles. In each pile, a number of cards equal to the proportion $q_n$ of the pile size rounded upward to the closest integer are candidates to be picked. Each candidate card is picked with probability $p_n$, independently of other candidate cards. This generalizes Popov's random Bulgarian solitaire, in which there is a single candidate card in each pile. Popov showed that a triangular limit shape is obtained for a fixed p as n tends to infinity. Here we let both $p_n$ and $q_n$ vary with n. We show that under the conditions $q_n^2 p_n n/{\log n}\rightarrow \infty$ and $p_n q_n \rightarrow 0$ as $n\to\infty$, the $p_n$-random $q_n$-proportion Bulgarian solitaire has an exponential limit shape.

##### Keywords
Random Bulgarian solitaire, Limit shape
##### National Category
Probability Theory and Statistics
##### Research subject
Mathematics/Applied Mathematics
##### Identifiers
urn:nbn:se:mdh:diva-35014 (URN)
##### Funder
Swedish Research Council, 2010-5565, 621-2009-6090 Available from: 2017-03-13 Created: 2017-03-13 Last updated: 2017-03-16Bibliographically approved
4. Markov chains on graded posets: Compatibility of up-directed and down-directed transition probabilities
Open this publication in new window or tab >>Markov chains on graded posets: Compatibility of up-directed and down-directed transition probabilities
2018 (English)In: Order, ISSN 0167-8094, E-ISSN 1572-9273, ISSN 0167-8094, no 1, p. 93-109Article in journal (Refereed) Published
##### Abstract [en]

We consider two types of discrete-time Markov chains where thestate space is a graded poset and the transitionsare taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts between the up-directed transition probabilities (an up rule) and the down-directed(a down rule), and we relate these to compatibility betweenup-and-down chains. This framework is used to prove a conjecture about a limit shape for a process on Young's lattice. Finally, we settle the questions whether the reverse of an up chain is a down chain for some down rule and whether there exists an up or down chain at all if the rank function is not bounded.

##### Place, publisher, year, edition, pages
Springer Netherlands, 2018
##### Keywords
Graded poset, Markov chain, Young diagram, Young's lattice, Limit shape
##### National Category
Discrete Mathematics
##### Research subject
Mathematics/Applied Mathematics
##### Identifiers
urn:nbn:se:mdh:diva-35015 (URN)10.1007/s11083-016-9420-1 (DOI)000427496600006 ()2-s2.0-85017160313 (Scopus ID)
##### Funder
Swedish Research Council, 2010-5565, 621-2009-6090 Available from: 2017-03-13 Created: 2017-03-13 Last updated: 2018-04-05Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT02.pdfFile size 1909 kBChecksum SHA-512
189e1a0a595ea7b82f9f78959af271d5c08cd793f1957aeb83682171337a0f0a7fc710a97ea183f883ca8f784359dd7f6882c351cc878603de636a638c916ecf
Type fulltextMimetype application/pdf

Jonsson, Markus

#### Search in DiVA

Jonsson, Markus
##### By organisation
Educational Sciences and Mathematics
Mathematics

#### Search outside of DiVA

The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available
isbn
urn-nbn

#### Altmetric score

isbn
urn-nbn
Total: 310 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
v. 2.35.9
| |