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.
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 certainpatterns 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 cross-ings of matchings too.
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.
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 is
E-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.
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.
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.
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).
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.
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. Non-existence 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.
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 ).
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.
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. (C) 2007 Elsevier Inc. All rights reserved.
A locally uniform random permutation is generated by sampling n points independently from some absolutely continuous distribution ρ on the plane and interpreting them as a permutation by the rule that i maps to j if the ith point from the left is the jth point from below. As n tends to infinity, decreasing subsequences in the permutation will appear as curves in the plane, and by interpreting these as level curves, a union of decreasing subsequences gives rise to a surface. In a recent paper by the author it was shown that, for any r≥0, under the correct scaling as n tends to infinity, the surface of the largest union of ⌊rn⌋ decreasing subsequences approaches a limit in the sense that it will come close to a maximizer of a specific variational integral (and, under reasonable assumptions, that the maximizer is essentially unique). In the present paper we show that there exists a continuous maximizer, provided that ρ has bounded density and support. The key ingredient in the proof is a new theorem about real functions of two variables that are increasing in both variables: We show that, for any constant C, any such function can be made continuous without increasing the diameter of its image or decreasing anywhere the product of its partial derivatives clipped by C, that is the minimum of the product and C.
The following special case of a conjecture by Loehr and Warrington was proved recently by Ekhad, Vatter. and Zeilberger:
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. (c) 2005 Elsevier Ltd. All rights reserved.
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.
We show that any loopy multigraph with a graphical degree sequence can be transformed into a simple graph by a finite sequence of double edge swaps with each swap involving at least one loop or multiple edge. Our result answers a question of Janson motivated by random graph theory, and it adds to the rich literature on reachability of double edge swaps with applications in Markov chain Monte Carlo sampling from the uniform distribution of graphs with prescribed degrees.
A locally uniform random permutation is generated by sampling n points independently from some absolutely continuous distribution ρ on the plane and interpreting them as a permutation by the rule that i maps to j if the ith point from the left is the j th point from below. As n tends to infinity, decreasing subsequences in the permutation will appear as curves in the plane, and by interpreting these as level curves, a union of decreasing subsequences give rise to a surface. We show that, under the correct scaling, for any r ≥ 0, the largest union of (Formula Presenmted)decreasing subsequences approaches a limit surface as n tends to infinity, and the limit surface is a solution to a specific variational problem. As a corollary, we prove the existence of a limit shape for the Young diagram associated to the random permutation under the Robinson– Schensted correspondence. In the special case where ρ is the uniform distribution on the diamond |x| + |y| < 1, we conjecture that the limit shape is triangular, and assuming the conjecture is true, we find an explicit formula for the limit surfaces of a uniformly random permutation and recover the famous limit shape of Vershik, Kerov and Logan, Shepp.
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.