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.

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.

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.

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.

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.

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.

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.

A fundamental fact in two-sided matching is that if a market 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.

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.

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.

We characterise the permutations pi such that the elements in the closed lower Bruhat interval [id, pi] of the symmetric group correspond to non-taking rook configurations on a skew Ferrers board. It turns out that these are exactly the permutations pi such that [id, pi] corresponds to a flag manifold defined by inclusions, studied by Gasharov and Reiner.Our characterisation connect, the Poincare polynomials (rank-generating function) of Bruhat intervals with q-rook polynomials, and we are able to compute the Poincare polynomial of some particularly interesting intervals in the finite Weyl groups An and B, The expressions involve q-Stirling numbers of the second kind, and for the group A, putting q = 1 yields the poly-Bernoulli numbers defined by Kaneko.

There are 10(n) zero-sum words of length 5n in the alphabet {+3, -2} such that no zero-sum consecutive subword that starts with +3 may be followed immediately by -2.

We give a simple bijective proof of the conjecture in its original and more general setting. To do this we reformulate the problem in terms of cylindrical lattice walks.

Ämnet för denna avhandling är enumerativ kombinatorik tillämpad på tre olika objekt med anknytning till partitionsformer, nämligen tablåer, begränsade ord och bruhatintervall. Dom viktigaste vetenskapliga bidragen är följande.

Artikel I: Låt tecknet av en standardtablå vara tecknet hos permutationen man får om man läser tablån rad för rad från vänster till höger, som en bok. En förmodan av Richard Stanley säjer att teckensumman av alla standardtablåer med n rutor är 2^[n/2]. Vi visar en generalisering av denna förmodan med hjälp av Robinson-Schensted-korrespondensen och ett nytt begrepp som vi kallar schacktablåer. Beviset bygger på ett anmärkningsvärt enkelt samband mellan tecknet hos en permutation pi och tecknen hos dess RS-motsvarande tablåer P och Q, nämligen sgn(pi)=(-1)^v sgn(P)sgn(Q), där v är antalet disjunkta vertikala dominobrickor som får plats i partitionsformen hos P och Q. Teckenobalansen hos en partitionsform definieras som teckensumman av alla standardtablåer av den formen. Som en ytterligare tillämpning av formeln för teckenöverföring ovan bevisar vi också en starkare variant av en annan förmodan av Stanley som handlar om viktade summor av kvadrerade teckenobalanser.

Artikel II: Vi generaliserar några av resultaten i artikel I till skeva tablåer. Närmare bestämt undersöker vi hur teckenegenskapen överförs av Sagan och Stanleys skeva Robinson-Schensted-korrespondens. Resultatet är en förvånansvärt enkel generalisering av den vanliga ickeskeva formeln ovan. Som en tillämpning visar vi att vissa viktade summor av kvadrerade teckenobalanser blir noll, vilket leder till en generalisering av en variant av Stanleys andra förmodan.

Artikel III: Följande specialfall av en förmodan av Loehr och Warrington bevisades av Ekhad, Vatter och Zeilberger: Det finns 10^n ord med summan noll av längd 5n i alfabetet {+3,-2} sådana att inget sammanhängande delord börjar med +3, slutar med -2 och har summan -2. Vi ger ett enkelt bevis för denna förmodan i dess ursprungliga allmännare utförande där 3 och 2 byts ut mot vilka som helst relativt prima positiva heltal a och b, 10^n byts ut mot ((a+b) över a)^n och 5n mot (a+b)n. För att göra detta formulerar vi problemet i termer av cylindriska latticestigar som kan tolkas som den sydöstra gränslinjen för vissa partitionsformer.

Artikel IV: Vi karakteriserar dom permutationer pi sådana att elementen i det slutna bruhatintervallet [id,pi] i symmetriska gruppen motsvarar ickeslående tornplaceringar på ett skevt ferrersbräde. Dessa intervall visar sej vara precis dom vars flaggmångfalder är definierade av inklusioner, ett begrepp introducerat av Gasharov och Reiner. Karakteriseringen skapar en länk mellan poincarépolynom (ranggenererande funktioner) för bruhatintervall och q-tornpolynom, och vi kan beräkna poincarépolynomet för några särskilt intressanta intervall i dom ändliga weylgrupperna A_n och B_n. Uttrycken innehåller q-stirlingtal av andra sorten, och sätter man q=1 för grupp A_n så får man Kanekos poly-bernoullital.

We present a simple formula for the expected number of inversions in a permutation of size n obtained by applying t random (not necessarily adjacent) transpositions to the identity permutation. More generally, for any finite irreducible Coxeter group belonging to one of the infinite families (type A, B, D, and I), an exact expression is obtained for the expected length of a product of t random reflections.

Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2([n/2]). We present a stronger theorem with a purely combinatorial proof using the Robinson-Schensted correspondence and a new concept called chess tableaux. We also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. The proof is built on a remarkably simple relation between the sign of a permutation and the signs of its RS-corresponding tableaux.

Let the sign of a skew standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. We examine how the sign property is transferred by the skew Robinson-Schensted correspondence invented by Sagan and Stanley. The result is a remarkably simple generalization of the ordinary non-skew formula.The sum of the signs of all standard tableaux on a given skew shape is the sign-imbalance of that shape. We generalize previous results on the sign-imbalance of ordinary partition shapes to skew ones.

For any configuration of pebbles on the nodes of a graph, a pebbling move replaces two pebbles on one node by one pebble on an adjacent node. A cover pebbling is a move sequence ending with no empty nodes. The number of pebbles needed for a cover pebbling starting with all pebbles on one node is trivial to compute and it was conjectured that the maximum of these simple cover pebbling numbers is indeed the general cover pebbling number of the graph. That is, for any configuration of this size, there exists a cover pebbling. In this note, we prove a generalization of the conjecture. All previously published results about cover pebbling numbers for special graphs (trees, hypercubes et cetera) are direct consequences of this theorem. We also prove that the cover pebbling number of a product of two graphs equals the product of the cover pebbling numbers of the graphs.

In a species capable of (imperfect) social learning, how much culture can a population of a given size carry? And what is the relationship between the individual and the population? In the first study of these novel questions, here we develop a mathematical model of the accumulation of independent cultural traits in a finite population with overlapping generations.