| 1. |
- Alexandersson, Per, et al.
(författare)
-
A Major-Index Preserving Map on Fillings
- 2017
-
Ingår i: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 24:4
-
Tidskriftsartikel (refereegranskat)abstract
- We generalize a map by S. Mason regarding two combinatorial models for key polynomials, in a way that accounts for the major index. Furthermore we define a similar variant of this map, that regards alternative models for the modified Macdonald polynomials at t = 0, and thus partially answers a question by J. Haglund. These maps together imply a certain uniqueness property regarding inversion- and coinversion-free fillings. These uniqueness properties allow us to generalize the notion of charge to a non-symmetric setting, thus answering a question by A. Lascoux and the analogous question in the symmetric setting proves a conjecture by K. Nelson.
|
|
| 2. |
- Alexandersson, Per
(författare)
-
Schur polynomials, banded Toeplitz matrices and Widom's formula
- 2012
-
Ingår i: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 19:4, s. P22-
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that for arbitrary partitions lambda subset of kappa, and integers 0 <= c < r <= n, the sequence of Schur polynomials S(kappa+k.1c)/(lambda+k.1r)(x(1), ... , x(n)) for k sufficiently large, satisfy a linear recurrence. The roots of the characteristic equation are given explicitly. These recurrences are also valid for certain sequences of minors of banded Toeplitz matrices. In addition, we show that Widom's determinant formula from 1958 is a special case of a well-known identity for Schur polynomials.
|
|
| 3. |
- Alexandersson, Per, et al.
(författare)
-
Symmetric polynomials in the symplectic alphabet and the change of variables z(j) = x(j) + x(j)(-1)
- 2021
-
Ingår i: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 28:1
-
Tidskriftsartikel (refereegranskat)abstract
- Given a symmetric polynomial P in 2n variables, there exists a unique symmetric polynomial Q in n variables such that P(x(1), ..., x(n), x(1)(-1), ..., x(n)(-1)) = Q(x(1) + x(1)(-1), ..., x(n) + x(n)(-1)). We denote this polynomial Q by Phi(n)(P) and show that Phi(n) is an epimorphism of algebras. We compute Phi(n)(P) for several families of symmetric polynomials P: symplectic and orthogonal Schur polynomials, elementary symmetric polynomials, complete homogeneous polynomials, and power sums. Some of these formulas were already found by Elouafi (2014) and Lachaud (2016). The polynomials of the form Phi(n)(s(lambda/mu)((2n))), where s(lambda/mu)((2n)) is a skew Schur polynomial in 2n variables, arise naturally in the study of the minors of symmetric banded Toeplitz matrices, when the generating symbol is a palindromic Laurent polynomial, and its roots can be written as x(1), ..., x(n), x(1)(-1), ..., x(n)(-1). Trench (1987) and Elouafi (2014) found efficient formulas for the determinants of symmetric banded Toeplitz matrices. We show that these formulas are equivalent to the result of Ciucu and Krattenthaler (2009) about the factorization of the characters of classical groups.
|
|
| 4. |
- Alexandersson, Per, et al.
(författare)
-
The cyclic sieving phenomenon on circular Dyck paths
- 2019
-
Ingår i: The Electronic Journal of Combinatorics. - : ELECTRONIC JOURNAL OF COMBINATORICS. - 1097-1440 .- 1077-8926. ; 26:4
-
Tidskriftsartikel (refereegranskat)abstract
- We give a q-enumeration of circular Dyck paths, which is a superset of the classical Dyck paths enumerated by the Catalan numbers. These objects have recently been studied by Alexandersson and Panova. Furthermore, we show that this q-analogue exhibits the cyclic sieving phenomenon under a natural action of the cyclic group. The enumeration and cyclic sieving is generalized to Mobius paths. We also discuss properties of a generalization of cyclic sieving, which we call subset cyclic sieving, and introduce the notion of Lyndon-like cyclic sieving that concerns special recursive properties of combinatorial objects exhibiting the cyclic sieving phenomenon.
|
|
| 5. |
- Amini, Nima
(författare)
-
Equidistributions of mahonian statistics over pattern avoiding permutations
- 2018
-
Ingår i: The Electronic Journal of Combinatorics. - : Australian National University Press. - 1097-1440 .- 1077-8926. ; 25:1
-
Tidskriftsartikel (refereegranskat)abstract
- A Mahonian d-function is a Mahonian statistic that can be expressed as a linear combination of vincular pattern functions of length at most d. Babson and Ste- ingrímsson classified all Mahonian 3-functions up to trivial bijections and identified many of them with well-known Mahonian statistics in the literature. We prove a host of Mahonian 3-function equidistributions over permutations in Sn avoiding a single classical pattern in S3. Tools used include block decomposition, Dyck paths and generating functions.
|
|
| 6. |
- Andrén, Lina J
(författare)
-
Avoiding (m, m, m)-arrays of order n=2(k)
- 2012
-
Ingår i: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 19:1, s. P63-
-
Tidskriftsartikel (refereegranskat)abstract
- An (m, m, m)-array of order n is an n x n array such that each cell is assigned a set of at most m symbols from f 1,...,n g such that no symbol occurs more than m times in any row or column. An (m, m, m)-array is called avoidable if there exists a Latin square such that no cell in the Latin square contains a symbol that also belongs to the set assigned to the corresponding cell in the array. We show that there is a constant gamma such that if m <= gamma 2(k) and k >= 14, then any (m, m, m)-array of order n = 2(k) is avoidable. Such a constant gamma has been conjectured to exist for all n by Haggkvist.
|
|
| 7. |
- Andriantiana, Eric O. D., et al.
(författare)
-
Extremal trees with fixed degree sequence
- 2021
-
Ingår i: The Electronic Journal of Combinatorics. - : ELECTRONIC JOURNAL OF COMBINATORICS. - 1097-1440 .- 1077-8926. ; 28:1
-
Tidskriftsartikel (refereegranskat)abstract
- The greedy tree G(D) and the M-tree M(D) are known to be extremal among trees with degree sequence D with respect to various graph invariants. This paper provides a general theorem that covers a large family of invariants for which G(D) or M(D) is extremal. Many known results, for example on the Wiener index, the number of subtrees, the number of independent subsets and the number of matchings follow as corollaries, as do some new results on invariants such as the number of rooted spanning forests, the incidence energy and the solvability. We also extend our results on trees with fixed degree sequence D to the set of trees whose degree sequence is majorised by a given sequence D, which also has a number of applications.
|
|
| 8. |
- Atkins, Ross, et al.
(författare)
-
Guessing Numbers of Odd Cycles
- 2017
-
Ingår i: The Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 24:1
-
Tidskriftsartikel (refereegranskat)abstract
- For a given number of colours, s, the guessing number of a graph is the base s logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the n-vertex cycle graph Cn is n/2. It is known that the guessing number equals n/2 whenever n is even or s is a perfect square. We show that, for any given integer s≥2, if a is the largest factor of s less than or equal to √s, for sufficiently large odd n, the guessing number of Cn with s colours is (n−1)/2+logs(a). This answers a question posed by Christofides and Markström in 2011.We also present an explicit protocol which achieves this bound for every n. Linking this to index coding with side information, we deduce that the information defect of Cn with s colours is (n+1)/2−logs(a) for sufficiently large odd n.
|
|
| 9. |
- Beer, Elizabeth, et al.
(författare)
-
On Vertex, Edge, and Vertex-Edge Random Graphs
- 2011
-
Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 18:1, s. P110-
-
Tidskriftsartikel (refereegranskat)abstract
- We consider three classes of random graphs: edge random graphs, vertex random graphs, and vertex-edge random graphs. Edge random graphs are Erdos-Renyi random graphs, vertex random graphs are generalizations of geometric random graphs, and vertex-edge random graphs generalize both. The names of these three types of random graphs describe where the randomness in the models lies: in the edges, in the vertices, or in both. We show that vertex-edge random graphs, ostensibly the most general of the three models, can be approximated arbitrarily closely by vertex random graphs, but that the two categories are distinct.
|
|
| 10. |
- Berglund, Alexander
(författare)
-
Shellability and the strong gcd-condition
- 2009
-
Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 16:2
-
Tidskriftsartikel (refereegranskat)abstract
- Shellability is a well-known combinatorial criterion on a simplicial complex for verifying that the associated Stanley-Reisner ring k[] is Cohen-Macaulay. Anotion familiar to commutative algebraists, but which has not received as muchattention from combinatorialists as the Cohen-Macaulay property, is the notion ofa Golod ring. Recently, J¨ollenbeck introduced a criterion on simplicial complexesreminiscent of shellability, called the strong gcd-condition, and he together with theauthor proved that it implies Golodness of the associated Stanley-Reisner ring. Thetwo algebraic notions were earlier tied together by Herzog, Reiner and Welker, whoshowed that if k[∨] is sequentially Cohen-Macaulay, where ∨ is the Alexanderdual of , then k[] is Golod. In this paper, we present a combinatorial companionof this result, namely that if ∨ is (non-pure) shellable then satisfies the stronggcd-condition. Moreover, we show that all implications just mentioned are strict ingeneral but that they are equivalences if is a flag complex.
|
|
