| 11. |
- 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.
|
|
| 12. |
- Ferroni, Luis, et al.
(författare)
-
The Merino–Welsh Conjecture for Split Matroids
- 2023
-
Ingår i: Annals of Combinatorics. - : Springer Nature. - 0218-0006 .- 0219-3094. ; 27:3, s. 737-748
-
Tidskriftsartikel (refereegranskat)abstract
- In 1999, Merino and Welsh conjectured that evaluations of the Tutte polynomial of a graph satisfy an inequality. In this short article, we show that the conjecture generalized to matroids holds for the large class of all split matroids by exploiting the structure of their lattice of cyclic flats. This class of matroids strictly contains all paving and copaving matroids.
|
|
| 13. |
- Hultman, Axel, 1975-, et al.
(författare)
-
Boolean Complexes of Involutions
- 2023
-
Ingår i: Annals of Combinatorics. - : SPRINGER BASEL AG. - 0218-0006 .- 0219-3094. ; 27, s. 129-147
-
Tidskriftsartikel (refereegranskat)abstract
- Let (W,S) be a Coxeter system. We introduce the boolean com-plex of involutions ofWwhich is an analogue of the boolean complex ofWstudied by Ragnarsson and Tenner. By applying discrete Morse theory,we determine the homotopy type of the boolean complex of involutionsfor a large class of (W,S), including all finite Coxeter groups, finding thatthe homotopy type is that of a wedge of spheres of dimension |S|-1. In addition, we find simple recurrence formulas for the number of spheres inthe wedge
|
|
| 14. |
- 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.
|
|
| 15. |
- 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.
|
|
| 16. |
- 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.
|
|
| 17. |
- Jonsson, Jakob
(författare)
-
On the 3-Torsion Part of the Homology of the Chessboard Complex
- 2010
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 14:4, s. 487-505
-
Tidskriftsartikel (refereegranskat)abstract
- Let 1 (d) (M-m,M-n; Z) not equal 0. Second, for each k >= 0, we show that there is a polynomial f(k)(a, b) of degree 3k such that the dimension of (H) over tilde (k+a+2b-2) (M-k+a+3b-1,M- k+2a+3b-1; Z(3)), viewed as a vector space over Z(3), is at most f(k)(a, b) for all a >= 0 and b >= k+ 2. Third, we give a computer- free proof that (H) over tilde (2) (M-5,M-5; Z) congruent to Z(3). Several proofs are based on a new long exact sequence relating the homology of a certain subcomplex of M-m,M-n to the homology of M-m-2,M-n-1 and M-m-2,M-n-3.
|
|
| 18. |
- Liu, Fu, et al.
(författare)
-
On the Relationship Between Ehrhart Unimodality and Ehrhart Positivity
- 2019
-
Ingår i: Annals of Combinatorics. - : Springer Berlin/Heidelberg. - 0218-0006 .- 0219-3094. ; 23:2, s. 347-365
-
Tidskriftsartikel (refereegranskat)abstract
- For a given lattice polytope, two fundamental problems within the field of Ehrhart theory are (1) to determine if its (Ehrhart) h-polynomial is unimodal and (2) to determine if its Ehrhart polynomial has only positive coefficients. The former property of a lattice polytope is known as Ehrhart unimodality and the latter property is known as Ehrhart positivity. These two properties are often simultaneously conjectured to hold for interesting families of lattice polytopes, yet they are typically studied in parallel. As to answer a question posed at the 2017 Introductory Workshop to the MSRI Semester on Geometric and Topological Combinatorics, the purpose of this note is to show that there is no general implication between these two properties in any dimension greater than two. To do so, we investigate these two properties for families of well-studied lattice polytopes, assessing one property where previously only the other had been considered. Consequently, new examples of each phenomena are developed, some of which provide an answer to an open problem in the literature. The well-studied families of lattice polytopes considered include zonotopes, matroid polytopes, simplices of weighted projective spaces, empty lattice simplices, smooth polytopes, and s-lecture hall simplices.
|
|
| 19. |
- Norén, Patrik, et al.
(författare)
-
Ideals of graph homomorphisms
- 2011
-
Ingår i: Annals of Combinatorics. - 0218-0006 .- 0219-3094.
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)
|
|
| 20. |
- 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)
|
|
