| 1. |
- Fill, James Allen, et al.
(författare)
-
Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
- 2009
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 12:4, s. 403-416
-
Tidskriftsartikel (refereegranskat)abstract
- For certain random variables that arise as limits of functionals of random finite trees, we obtain precise asymptotics for the logarithm of the right-hand tail. Our results are based on the facts (i) that the random variables we study can be represented as functionals of a Brownian excursion and (ii) that a large deviation principle with good rate function is known explicitly for Brownian excursion. Examples include limit distributions of the total path length and of the Wiener index in conditioned Galton-Watson trees (also known as simply generated trees). In the case of Wiener index (where we recover results proved by Svante Janson and Philippe Chassaing by a different method) and for some other examples, a key constant is expressed as the solution to a certain optimization problem, but the constant's precise value remains unknown.
|
|
| 2. |
- Backelin, Jörgen, et al.
(författare)
-
Parity splits by triple point distances in X-trees
- 2006
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 10:1, s. 1-18
-
Tidskriftsartikel (refereegranskat)abstract
- At the conference Dress defined parity split maps by triple point distance and asked for a characterisation of such maps coming from binary phylogenetic X-trees. This article gives an answer to that question. The characterisation for X-trees can be easily described as follows: If all restrictions of a split map to sets of five or fewer elements is a parity split map for an X-tree, then so is the entire map. To ensure that the parity split map comes from an X-tree which is binary and phylogenetic, we add two more technical conditions also based on studying at most five points at a time.
|
|
| 3. |
- Dress, Andreas, et al.
(författare)
-
Hereditarily Optimal Realizations of Consistent Metrics.
- 2006
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 10:1, s. 63-76
-
Tidskriftsartikel (refereegranskat)abstract
- One of the main problems in phylogenetics is to find good approximations of metrics by weighted trees. As an aid to solving this problem, it could be tempting to consider optimal realizations of metrics—the guiding principle being that, the (necessarily unique) optimal realization of a tree metric is the weighted tree that realizes this metric. And, although optimal realizations of arbitrary metrics are, in general, not trees, but rather weighted networks, one could still hope to obtain a phylogenetically informative representation of a given metric, maybe even more informative than the best approximating tree. However, optimal realizations are not only difficult to compute, they may also be non-unique. Here we focus on one possible way out of this dilemma: hereditarily optimal realizations. These are essentially unique, and can be described in a rather explicit way. In this paper, we recall what a hereditarily optimal realization of a metric is and how it is related to the 1-skeleton of the tight span of that metric, and we investigate under what conditions it coincides with this 1-skeleton. As a consequence, we will show that hereditarily optimal realizations for consistent metrics, a large class of phylogentically relevant metrics, can be computed in a straight-forward fashion.
|
|
| 4. |
- Eriksen, Niklas, 1974-, et al.
(författare)
-
Expected reflection distance in G(r, 1, n) after a fixed number of reflections
- 2005
-
Ingår i: Annals of Combinatorics. - Basel, Switzerland : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 9:1, s. 21-33
-
Tidskriftsartikel (refereegranskat)abstract
- Extending to r > 1 a formula of the authors, we compute the expected reflection distance of a product of t random reflections in the complex reflection group G (r, 1, n). The result relies on an explicit decomposition of the reflection distance function into irreducible G (r, 1, n) characters and on the eigenvalues of certain adjacency matrices.
|
|
| 5. |
- Eriksson, Henrik, et al.
(författare)
-
Dense packing of patterns in a permutation
- 2007
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 11:3-4, s. 459-470
-
Tidskriftsartikel (refereegranskat)abstract
- We study the length L-k of the shortest permutation containing all patterns of length k. We establish the bounds e(-2)k(2) < L-k <= (2/3 + o(1))k(2). We also prove that as k there are permutations of length (1/4+o(1))k(2) containing almost all patterns of length k.
|
|
| 6. |
- Incitti, Federico
(författare)
-
Permutation diagrams, fixed points and Kazhdan-Lusztig R-polynomials
- 2006
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 10:3, s. 369-387
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we give an algorithm for computing the Kazhdan-Lusztig R-polynomials in the symmetric group. The algorithm is described in terms of permutation diagrams. In particular we focus on how the computation of the polynomial is affected by certain fixed points. As a consequence of our methods, we obtain explicit formulas for the R-polynomials associated with some general classes of intervals, generalizing results of Brenti and Pagliacci.
|
|
| 7. |
- Janson, Svante, 1955-
(författare)
-
Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence
- 2009
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 12:4, s. 417-447
-
Tidskriftsartikel (refereegranskat)abstract
- We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0's, and then evolves by changing each 0 to 1, with the n changes done in random order. What is the maximal number of runs of 1's? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order n (1/2), and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1; there is also a second order term of order n (1/3). We also treat some variations, including priority queues and sock-sorting. The proofs use methods originally developed for random graphs.
|
|
| 8. |
- Johansson, Robert, et al.
(författare)
-
Pattern avoidance in alternating sign matrices
- 2007
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 11:04-mar, s. 471-480
-
Tidskriftsartikel (refereegranskat)abstract
- We generalize the definition of a pattern from permutations to alternating sign matrices. The number of alternating sign matrices avoiding 132 is proved to be counted by the large Schroder numbers, 1, 2, 6, 22, 90, 394,.... We give a bijection between 132-avoiding alternating sign matrices and Schroder paths, which gives a refined enumeration. We also show that the 132-, 123-avoiding alternating sign matrices are counted by every second Fibonacci number.
|
|
| 9. |
- Sivertsson, Olof, et al.
(författare)
-
A bound on the overlap of same-sized subsets
- 2008
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 12:3, s. 347-352
-
Tidskriftsartikel (refereegranskat)
|
|
| 10. |
|
|
