| 1. |
- Aas, Erik, et al.
(författare)
-
A product formula for the TASEP on a ring
- 2016
-
Ingår i: Random structures & algorithms (Print). - : Wiley-Blackwell. - 1042-9832 .- 1098-2418. ; 48:2, s. 247-259
-
Tidskriftsartikel (refereegranskat)abstract
- For a random permutation sampled from the stationary distributionof the TASEP on a ring, we show that, conditioned on the event that the rstentries are strictly larger than the last entries, the order of the rst entries isindependent of the order of the last entries. The proof uses multi-line queues asdened by Ferrari and Martin, and the theorem has an enumerative combinatorialinterpretation in that setting.As an application we prove a conjecture of Lam and Williams concerningSchubert factors of the stationary probability of certain states.Finally, we present a conjecture for the case where the small and large entriesare not separated.
|
|
| 2. |
- Aas, Erik, et al.
(författare)
-
A product formula for the TASEP on a ring - Extended Abstract
- 2014
-
Ingår i: Discrete Mathematics and Theoretical Computer Science. - : Discrete Mathematics and Theoretical Computer Science. ; , s. 633-641
-
Konferensbidrag (refereegranskat)abstract
- For a random permutation sampled from the stationary distribution of the TASEP on a ring, we show that, conditioned on the event that the first entries are strictly larger than the last entries, the order of the first entries is independent of the order of the last entries. The proof uses multi-line queues as defined by Ferrari and Martin, and the theorem has an enumerative combinatorial interpretation in that setting. Finally, we present a conjecture for the case where the small and large entries are not separated.
|
|
| 3. |
- Björner, Anders., et al.
(författare)
-
Bier spheres and posets
- 2005
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 34:1, s. 71-86
-
Tidskriftsartikel (refereegranskat)abstract
- In 1992 Thomas Bier presented a strikingly simple method to produce a huge number of simplicial (n -2)-spheres on 2n vertices, as deleted joins of a simplicial complex on n vertices with its combinatorial Alexander dual. Here we interpret his construction as giving the poset of all the intervals in a boolean algebra that cut across an ideal. Thus we arrive at a substantial generalization of Bier's construction: the Bier posets Bier(P, I) of an arbitrary bounded poset P of finite length. In the case of face posets of PL spheres this yields cellular generalized Bier spheres. In the case of Eulerian or Cohen-Macaulay posets P we show that the Bier posets Bier(P, I) inherit these properties. In the boolean case originally considered by Bier, we show that all the spheres produced by his construction are shellable, which yields many shellable spheres, most of which lack convex realization. Finally, we present simple explicit formulas for the g-vectors of these simplicial spheres and verify that they satisfy a strong form of the g-conjecture for spheres.
|
|
| 4. |
- Bång, Magnus, et al.
(författare)
-
Automatisk trafikövervakning genom AI i svenska farvatten : Slutrapport AutoMon Del I
- 2023
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Denna slutrapport redogör för resultatet av projektet: AutoMon Del I—Automatisk trafikövervakning genom AI i svenska farvatten (TRV2019/95873). Projektägare är Linköpings universitet och genomförts tillsammans med Sjöfartsverket, SAAB, VTI, och Luftfartsverket. Vi kommer i denna rapport redogöra för resultaten samt diskutera framtida utmaningar med konceptet AutoMon. Syftet med AutoMon är att undersöka och belysa problemområdet automatiserad trafikövervakning genom att implementera en AI-demonstrator för svenska farvatten, initialt med fokus på att detektera anomalier i trafiken, och där hanteringen (dvs. granskning och lösning) av problemsituationer lämnas över till en mänsklig operatör. Förekomsten av fartygsolyckor och -incidenter, med potentiellt stora konsekvenser för individ och miljö - utanför etablerade VTS-områden - visar på behovet av utökad övervakning av sjötrafiken i svenska farvatten för att möjliggöra proaktiva åtgärder för att minimera olycksrisker till sjöss. Forskningsprojektet undersöker hur en hög nivå av automation kan användas för att upptäcka och hantera trafikavvikelser på svenskt vatten samt ge möjlighet till s.k. situational awareness (lägesbild) över hela dess yta, samtidigt som stöd för centralt eller distribuerat beslutsfattande ges. Runt om i världen förekommer även manipulation av AIS-systemet och dess positionsangivelser; ett problem som sannolikt kommer att öka även i Sverige. Båda problemställningarna är globala, vilket ger hög relevans. Lösningar har högt värde där digitalisering och artificiell intelligens kan användas som medel för ökad sjösäkerhet (safety och cyber security).
|
|
| 5. |
- 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.
|
|
| 6. |
- Eriksen, Niklas, 1974-, et al.
(författare)
-
Equidistributed Statistics on Matchings and Permutations
- 2014
-
Ingår i: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 21:4
-
Tidskriftsartikel (refereegranskat)abstract
- We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization. As a special case we obtain proofs of two conjectures of Claesson and Linusson. Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
| 10. |
- 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.
|
|
| 11. |
- 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.
|
|
| 12. |
- 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.
|
|
| 13. |
- 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).
|
|
| 14. |
- 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.
|
|
| 15. |
- 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.
|
|
| 16. |
|
|
| 17. |
- Eriksson, Kimmo, et al.
(författare)
-
Optimal Expected Rank in a Two-Sided Secretary Problem
- 2007
-
Ingår i: Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0030-364X .- 1526-5463. ; 55:5, s. 921-931
-
Tidskriftsartikel (refereegranskat)abstract
- In a two-sided version of the famous secretary problem, employers search for a secretary at the same time as secretaries search for an employer. Nobody accepts being put on hold, and nobody is willing to take part in more than N interviews. Preferences are independent, and agents seek to optimize the expected rank of the partner they obtain among the N potential partners. We find that in any subgame perfect equilibrium, the expected rank grows as the square root of N (whereas it tends to a constant in the original secretary problem). We also compute how much agents can gain by cooperation.
|
|
| 18. |
|
|
| 19. |
- Eriksson, Kimmo, et al.
(författare)
-
Three-dimensional stable matching with cyclic preferences
- 2006
-
Ingår i: Mathematical Social Sciences. - : Elsevier BV. - 0165-4896 .- 1879-3118. ; 52:1, s. 77-87
-
Tidskriftsartikel (refereegranskat)abstract
- We consider stable three-dimensional matchings of three genders (3GSM). Alkan [Alkan, A., 1988. Nonexistence of stable threesome matchings. Mathematical Social Sciences 16, 207-209] showed that not all instances of 3GSM allow stable matchings. Boros et al. [Boros, E., Gurvich, V, Jaslar, S., Krasner, D., 2004. Stable matchings in three-sided systems with cyclic preferences. Discrete Mathematics 286, 1-10] showed that if preferences are cyclic, and the number of agents is limited to three of each gender, then a stable matching always exists. Here we extend this result to four agents of each gender. We also show that a number of well-known sufficient conditions for stability do not apply to cyclic 3GSM. Based on computer search, we formulate a conjecture on stability of "strongest link" 3GSM, which would imply stability of cyclic 3GSM.
|
|
| 20. |
- Flötteröd, Gunnar, 1976-, et al.
(författare)
-
Intensity and severity of ship conflicts : an AIS based approach
- 2023
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- There is a lack of standardized methods for socio-economic evaluations within the maritime transport sector. This paper presents a model for analysing and quantifying the intensity and severity of ship conflicts using AIS (Automatic Identification System) data and expert assessments. Also, a case study applying the proposed method to the Southern Gothenburg Archipelago is carried out. The goal is to contribute to cost-benefit analyses within the maritime transport sector by a better understanding of how different actions, such as the widening of fairways or new regulation, impact maritime safety. The importance of validating the model by comparing its results with independent sources of reported maritime accidents is emphasized, and the challenges of using existing accident statistics for this purpose is discussed. The basic model described in the paper can be built upon by differentiating parameters by region and vessel type, account for seasonality etc. Furthermore, a downstream consequence analysis model is needed to enable a monetary valuation of (the consequences of) identified conflicts. Finally, the same principles as laid out here for conflict analysis can also be adopted to the identification of groundings.
|
|
| 21. |
|
|
| 22. |
- Hansson, Mikael, 1986-
(författare)
-
Generalised Ramsey numbers and Bruhat order on involutions
- 2015
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis consists of two papers within two different areas of combinatorics.Ramsey theory is a classic topic in graph theory, and Paper A deals with two of its most fundamental problems: to compute Ramsey numbers and to characterise critical graphs. More precisely, we study generalised Ramsey numbers for two sets Γ1 and Γ2 of cycles. We determine, in particular, all generalised Ramsey numbers R(Γ1, Γ2) such that Γ1 or Γ2 contains a cycle of length at most 6, or the shortest cycle in each set is even. This generalises previous results of Erdös, Faudree, Rosta, Rousseau, and Schelp. Furthermore, we give a conjecture for the general case. We also characterise many (Γ1, Γ2)-critical graphs. As special cases, we obtain complete characterisations of all (Cn,C3)-critical graphs for n ≥ 5, and all (Cn,C5)-critical graphs for n ≥ 6.In Paper B, we study the combinatorics of certain partially ordered sets. These posets are unions of conjugacy classes of involutions in the symmetric group Sn, with the order induced by the Bruhat order on Sn. We obtain a complete characterisation of the posets that are graded. In particular, we prove that the set of involutions with exactly one fixed point is graded, which settles a conjecture of Hultman in the affirmative. When the posets are graded, we give their rank functions. We also give a short, new proof of the EL-shellability of the set of fixed-point-free involutions, recently proved by Can, Cherniavsky, and Twelbeck.
|
|
| 23. |
- Hultman, Axel, et al.
(författare)
-
From Bruhat intervals to intersection lattices and a conjecture of Postnikov
- 2009
-
Ingår i: Journal of combinatorial theory. Series A (Print). - : Elsevier BV. - 0097-3165 .- 1096-0899. ; 116:3, s. 564-580
-
Tidskriftsartikel (refereegranskat)abstract
- We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w is an element of (sic)(n). is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups. A byproduct of this result and its proof is a set of inequalities relating Betti numbers of complexified inversion arrangements to Betti numbers of closed Schubert cells. Another consequence is a simple combinatorial interpretation of the chromatic polynomial of the inversion graph of a permutation which avoids the above patterns.
|
|
| 24. |
- Jonsson, Markus, et al.
(författare)
-
Limit shapes of stable configurations of a generalized Bulgarian solitaire
- 2024
-
Ingår i: Order. - : Springer Netherlands. - 0167-8094 .- 1572-9273.
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)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. 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 cards from a pile of size h. Here we consider a special class of such functions. Let us call well-behaved if and if both and 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 () 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 . For the special case when for , these limit shapes are triangular (in case ), or exponential (in case ), or interpolating between these shapes (in case ).
|
|
| 25. |
- Jonsson, Markus, et al.
(författare)
-
Markov chains on graded posets : Compatibility of up-directed and down-directed transition probabilities
- 2018
-
Ingår i: Order. - : Springer Netherlands. - 0167-8094 .- 1572-9273. ; :1, s. 93-109
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
