| 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. |
- Ahmed, Chwas, et al.
(författare)
-
On the number of principal ideals in d-tonal partition monoids
- 2021
-
Ingår i: Annals of Combinatorics. - : Springer. - 0218-0006 .- 0219-3094. ; 25:1, s. 79-113
-
Tidskriftsartikel (refereegranskat)abstract
- For a positive integer d, a non-negative integer n and a non-negative integer h <= n, we study the number C-n((d)) of principal ideals; and the number C-n,h((d)) of principal ideals generated by an element of rank h, in the d-tonal partition monoid on n elements. We compute closed forms for the first family, as partial cumulative sums of known sequences. The second gives an infinite family of new integral sequences. We discuss their connections to certain integral lattices as well as to combinatorics of partitions.
|
|
| 3. |
- Alexandersson, Per, et al.
(författare)
-
Properties of Non-symmetric Macdonald Polynomials at q=1 and q=0
- 2019
-
Ingår i: Annals of Combinatorics. - : Springer Publishing Company. - 0218-0006 .- 0219-3094. ; 23:2, s. 219-239
-
Tidskriftsartikel (refereegranskat)abstract
- We examine the non-symmetric Macdonald polynomials E at q=1, as well as the more general permuted-basement Macdonald polynomials. When q=1, we show that E(x;1,t) is symmetric and independent of t whenever is a partition. Furthermore, we show that, in general , this expression factors into a symmetric and a non-symmetric part, where the symmetric part is independent of t, and the non-symmetric part only depends on x, t, and the relative order of the entries in . We also examine the case q=0, which gives rise to the so-called permuted-basement t-atoms. We prove expansion properties of these t-atoms, and, as a corollary, prove that Demazure characters (key polynomials) expand positively into permuted-basement atoms. This complements the result that permuted-basement atoms are atom-positive. Finally, we show that the product of a permuted-basement atom and a Schur polynomial is again positive in the same permuted-basement atom basis. Haglund, Luoto, Mason, and van Willigenburg previously proved this property for the identity basement and the reverse identity basement, so our result can be seen as an interpolation (in the Bruhat order) between these two results. The common theme in this project is the application of basement-permuting operators as well as combinatorics on fillings, by applying results in a previous article by Per Alexandersson.
|
|
| 4. |
- 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.
|
|
| 5. |
- Beck, Matthias, et al.
(författare)
-
Smooth Centrally Symmetric Polytopes in Dimension 3 are IDP
- 2019
-
Ingår i: Annals of Combinatorics. - : Springer Publishing Company. - 0218-0006 .- 0219-3094. ; 23:2, s. 255-262
-
Tidskriftsartikel (refereegranskat)abstract
- In 1997 Oda conjectured that every smooth lattice polytope has the integer decomposition property. We prove Oda's conjecture for centrally symmetric 3-dimensional polytopes, by showing they are covered by lattice parallelepipeds and unimodular simplices.
|
|
| 6. |
- Björner, Anders, et al.
(författare)
-
A note on blockers in posets
- 2004
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 8:2, s. 123-131
-
Tidskriftsartikel (refereegranskat)abstract
- The blocker A* of an antichain A in a finite poset P is the set of elements minimal with the property of having with each member of A a common predecessor. The following is done: (1) The posets P for which A** = A for all antichains are characterized.(2) The blocker A* of a symmetric antichain in the partition lattice is characterized.(3) Connections with the question of finding minimal size blocking sets for certain set families are discussed.
|
|
| 7. |
- Diaconis, Persi, et al.
(författare)
-
Interval Graph Limits
- 2013
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 17:1, s. 27-52
-
Tidskriftsartikel (refereegranskat)abstract
- We work out a graph limit theory for dense interval graphs. The theory developed departs from the usual description of a graph limit as a symmetric function W(x, y) on the unit square, with x and y uniform on the interval (0, 1). Instead, we fix a W and change the underlying distribution of the coordinates x and y. We find choices such that our limits are continuous. Connections to random interval graphs are given, including some examples. We also show a continuity result for the chromatic number and clique number of interval graphs. Some results on uniqueness of the limit description are given for general graph limits.
|
|
| 8. |
- Dress, A., et al.
(författare)
-
A 'Non-Additive' Characterization of p-Adic Norms
- 2011
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 15:1, s. 37-50
-
Tidskriftsartikel (refereegranskat)abstract
- For F a p-adic field together with a p-adic valuation, we present a new characterization for a map p: F-n -> R boolean OR {-infinity} to be a delta-adic norm on the vector space F-n. This characterization was motivated by the concept of tight maps-maps that naturally arise within the theory of valuated matroids and tight spans. As an immediate consequence, we show that the two descriptions of the affine building of SLn(F) in terms of (i) p-adic norms given by Bruhat and Tits and (ii) tight maps given by Terhalle essentially coincide. The result suggests that similar characterizations of affine buildings of other classical groups should exist, and that the theory of affine buildings may turn out as a particular case of a yet to be developed geometric theory of valuated (and delta-valuated) matroids and their tight spans providing simply-connected G-spaces for large classes of appropriately specified groups G that could serve as a basis for an affine variant of Gromov's theory.
|
|
| 9. |
- 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.
|
|
| 10. |
- 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.
|
|
