bluuebunny/crossref_metadata_2025_split huggingface dataset:
A reciprocity approach to computing generating functions for permutations with no pattern matches
Authors: Jones Miles Eli , Remmel Jeffrey 
Published: August 2021

In this paper, we develop a new method to compute generating functions of the form $NM_τ (t,x,y) = \sum\limits_{n ≥0} {\frac{t^n} {n!}}∑_{σ ∈\mathcal{lNM_{n}(τ )}} x^{LRMin(σ)} y^{1+des(σ )}$ where $τ$ is a permutation that starts with $1, \mathcal{NM_n}(τ )$ is the set of permutations in the symmetric group $S_n$ with no $τ$ -matches, and for any permutation $σ ∈S_n$, $LRMin(σ )$ is the number of left-to-right minima of $σ$ and $des(σ )$ is the number of descents of $σ$ . Our method does not compute $NM_τ (t,x,y)$ directly, but assumes that $NM_τ (t,x,y) = \frac{1}{/ (U_τ (t,y))^x}$ where $U_τ (t,y) = \sum_{n ≥0} U_τ ,n(y) \frac{t^n}{ n!}$ so that $U_τ (t,y) = \frac{1}{ NM_τ (t,1,y)}$. We then use the so-called homomorphism method and the combinatorial interpretation of $NM_τ (t,1,y)$ to develop recursions for the coefficient of $U_τ (t,y)$.
Dans cet article, nous développons une nouvelle méthode pour calculer les fonctions génératrices de la forme $NM_τ (t,x,y) = \sum\limits_{n ≥0} {\frac{t^n} {n!}}∑_{σ ∈\mathcal{lNM_{n}(τ )}} x^{LRMin(σ)} y^{1+des(σ )}$ où τ est une permutation, $\mathcal{NM_n}(τ )$ est l'ensemble des permutations dans le groupe symétrique $S_n$ sans $τ$-matches, et pour toute permutation $σ ∈S_n$, $LRMin(σ )$ est le nombre de minima de gauche à droite de $σ$ et $des(σ )$ est le nombre de descentes de $σ$ . Notre méthode ne calcule pas $NM_τ (t,x,y)$ directement, mais suppose que $NM_τ (t,x,y) = \frac{1}{/ (U_τ (t,y))^x}$ où $U_τ (t,y) = \sum_{n ≥0} U_τ ,n(y) \frac{t^n}{ n!}$ de sorte que $U_τ (t,y) = \frac{1}{ NM_τ (t,1,y)}$. Nous utilisons ensuite la méthode dite "de l'homomorphisme'' et l'interprétation combinatoire de $NM_τ (t,1,y)$ pour développer des récursions sur le coefficient de $U_τ (t,y)$.
Touchard-Riordan formulas, T-fractions, and Jacobi's triple product identity
Authors: Josuat-Vergès Matthieu , Kim Jang-Soo 
Published: August 2021

We give a combinatorial proof of a Touchard-Riordan-like formula discovered by the first author. As a consequence we find a connection between his formula and Jacobi's triple product identity. We then give a combinatorial analog of Jacobi's triple product identity by showing that a finite sum can be interpreted as a generating function of weighted Schröder paths, so that the triple product identity is recovered by taking the limit. This can be stated in terms of some continued fractions called T-fractions, whose important property is the fact that they satisfy some functional equation. We show that this result permits to explain and generalize some Touchard-Riordan-like formulas appearing in enumerative problems.
Nous donnons une preuve combinatoire d'une formule à la Touchard-Riordan due au premier auteur. En conséquence, nous faisons appara\^ıtre un lien entre cette formule et l'identité du produit triple de Jacobi. Nous donnons un analogue combinatoire à l'identité du produit triple en montrant qu'une somme finie peut être interprétée comme fonction génératrice de chemins de Schröder pondérés, de sorte que l'identité du produit triple s'obtient en passant à la limite. Ceci peut être énoncé en termes de fractions continues appelées T-fractions, dont la propriété importante est le fait qu'elle satisfont certaines équations fonctionnelles. Nous montrons que ce résultat permet d'expliquer et généraliser certaines formules à la Touchard-Riordan apparaissant dans des problèmes d'énumération.
Double homotopy Cohen-Macaulayness for the poset of injective words and the classical NC-partition lattice
Authors: Kallipoliti Myrto , Kubitzke Martina 
Published: August 2021

In this paper we study topological properties of the poset of injective words and the lattice of classical non-crossing partitions. Specifically, it is shown that after the removal of the bottom and top elements (if existent) these posets are doubly Cohen-Macaulay. This extends the well-known result that those posets are shellable. Both results rely on a new poset fiber theorem, for doubly homotopy Cohen-Macaulay posets, which can be considered as an extension of the classical poset fiber theorem for homotopy Cohen-Macaulay posets.
Dans cet article, nous étudions certaines propriétés topologiques du poset des mots injectifs et du treillis des partitions non-croisées classiques. Plus précisément, nous montrons qu'après suppression des plus petit et plus grand élément (s'ils existent), ces posets sont doublement Cohen-Macaulay. C'est une extension du fait bien connu que ces deux posets sont épluchables ("shellable''). Ces deux résultats reposent sur un nouveau théorème poset-fibre pour les posets doublement homotopiquement Cohen-Macaulay, que l'on peut voir comme extension du théorème poset-fibre classique pour les posets homotopiquement Cohen-Macaulay.
Minkowski decompositions of associahedra
Authors: Lange Carsten 
Published: August 2021

Realisations of associahedra can be obtained from the classical permutahedron by removing some of its facets and the set of facets is determined by the diagonals of certain labeled convex planar $n$-gons as shown by Hohlweg and Lange (2007). Ardila, Benedetti, and Doker (2010) expressed polytopes of this type as Minkowski sums and differences of scaled faces of a standard simplex and computed the corresponding coefficients $y_I$ by Möbius inversion from the $z_I$ if tight right-hand sides $z_I$ for all inequalities of the permutahedron are assumed. Given an associahedron of Hohlweg and Lange, we first characterise all tight values $z_I$ in terms of non-crossing diagonals of the associated labeled $n$-gon, simplify the formula of Ardila et al., and characterise the remaining terms combinatorially.
Dans un article paru en 2007, Hohlweg et Lange décrivent des associaèdres réalisés à partir du permutoèdre en enlevant certaines de ses facettes. Ces facettes sont déterminées par les diagonales d'une famille de $n$-gones étiquetés. En 2010, Ardila, Benedetti et Doker ont montré que ces polytopes s'expriment par des sommes et différences de Minkowski de faces pondérées d'un simplexe. De plus, si les coefficients $z_I$ des inégalités décrivant l'associaèdre à partir du permutoèdre sont optimaux, alors les coefficients $y_I$ correspondants sont calculés par une inversion de Möbius. Étant donné un tel associaèdre, nous décrivons d'abord les valeurs optimales $z_I$ en termes de diagonales non croisées d'un certain $n$-gone étiqueté, ensuite nous simplifions la formule de Ardila et al. pour finalement décrire combinatoirement les termes restants.
Row-strict quasisymmetric Schur functions
Authors: Mason Sarah K , Remmel Jeffrey 
Published: August 2021

Haglund, Luoto, Mason, and van Willigenburg introduced a basis for quasisymmetric functions called the $\textit{quasisymmetric Schur function basis}$ which are generated combinatorially through fillings of composition diagrams in much the same way as Schur functions are generated through reverse column-strict tableaux. We introduce a new basis for quasisymmetric functions called the $\textit{row-strict quasisymmetric Schur function basis}$ which are generated combinatorially through fillings of composition diagrams in much the same way as Schur functions are generated through row-strict tableaux. We describe the relationship between this new basis and other known bases for quasisymmetric functions, as well as its relationship to Schur polynomials. We obtain a refinement of the omega transform operator as a result of these relationships.
Haglund, Luoto, Mason, et van Willigenburg ont introduit une base pour les fonctions quasi-symétriques appelée $\textit{base des fonctions de Schur quasi-symétriques}$, qui sont construites en remplissant des diagrammes de compositions, d'une manière très semblable à la construction des fonctions de Schur à partir des tableaux "column-strict'' (ordre strict sur les colonnes). Nous introduisons une nouvelle base pour les fonctions quasi-symétriques appelée $\textit{base des fonctions de Schur quasi-symétriques "row-strict''}$, qui sont construites en remplissant des diagrammes de compositions, d'une manière très semblable à la construction des fonctions de Schur à partir des tableaux "row-strict'' (ordre strict sur les lignes). Nous décrivons la relation entre cette nouvelle base et d'autres bases connues pour les fonctions quasi-symétriques, ainsi que ses relations avec les polynômes de Schur. Nous obtenons un raffinement de l'opérateur oméga comme conséquence de ces relations.
Generalized permutohedra, h-vectors of cotransversal matroids and pure O-sequences (extended abstract)
Authors: Oh Suho 
Published: August 2021

Stanley has conjectured that the h-vector of a matroid complex is a pure O-sequence. We will prove this for cotransversal matroids by using generalized permutohedra. We construct a bijection between lattice points inside a $r$-dimensional convex polytope and bases of a rank $r$ transversal matroid.
Stanley a conjecturé que le h-vecteur d'un complexe matroïde est une pure O-séquence. Nous allons le prouver pour les matroïdes cotransversaux en utilisant generalized permutohedra. Nous construisons une bijection entre les points du réseau intérieur d'un polytope convexe $r$-dimensions et les bases d'un matroïde transversal $r$-rang.
Stable rigged configurations and Littlewood―Richardson tableaux
Authors: Okado Masato , Sakamoto Reiho 
Published: August 2021

For an affine algebra of nonexceptional type in the large rank we show the fermionic formula depends only on the attachment of the node 0 of the Dynkin diagram to the rest, and the fermionic formula of not type $A$ can be expressed as a sum of that of type $A$ with Littlewood–Richardson coefficients. Combining this result with theorems of Kirillov–Schilling–Shimozono and Lecouvey–Okado–Shimozono, we settle the $X=M$ conjecture under the large rank hypothesis.
Pour une algèbre affine de type non-exceptionnel de grand rang nous prouvons que la formule fermionique dépend seulement du voisinage du nœud 0 dans le diagramme de Dynkin, et également que la formule fermionique en type autre que $A$ peut être exprimée comme combinaison de celles de type $A$ avec des coefficients de Littlewood–Richardson. Combinant ce résultat avec des théorèmes de Kirillov–Schilling–Shimozono et de Lecouvey–Okado–Shimozono, nous résolvons la conjecture $X=M$ lorsque le rang est grand.
How often do we reject a superior value? (Extended abstract)
Authors: Oliver Kamilla , Prodinger Helmut 
Published: August 2021

Words $a_1 a_2 \ldots a_n$ with independent letters $a_k$ taken from the set of natural numbers, and a weight (probability) attached via the geometric distribution $pq^{i-1}(p+q=1)$ are considered. A consecutive record (motivated by the analysis of a skip list structure) can only advance from $k$ to $k+1$, thus ignoring perhaps some larger (=superior) values. We investigate the number of these rejected superior values. Further, we study the probability that there is a single consecutive maximum and show that (apart from fluctuations) it tends to a constant.
On considère des mots $a_1a_2 \ldots a_n$ formés de lettres à valeurs entières, tirées de façon indépendante avec une distribution géométrique $pq^{i-1}(p+q=1)$. Un record $k+1$ est dit consécutif si la lettre précédente est $k$. La notion est motivée par des considérations algorithmiques. Les autres records sont rejetés. Nous étudions le nombre de records rejetés. Nous étudions aussi la probabilité qu'il y ait un seul maximum consécutif, et montrons qu'elle converge vers une constante, à certaines fluctuations près.
Tableaux and plane partitions of truncated shapes (extended abstract)
Authors: Panova Greta 
Published: August 2021

We consider a new kind of straight and shifted plane partitions/Young tableaux — ones whose diagrams are no longer of partition shape, but rather Young diagrams with boxes erased from their upper right ends. We find formulas for the number of standard tableaux in certain cases, namely a shifted staircase without the box in its upper right corner, i.e. truncated by a box, a rectangle truncated by a staircase and a rectangle truncated by a square minus a box. The proofs involve finding the generating function of the corresponding plane partitions using interpretations and formulas for sums of restricted Schur functions and their specializations. The number of standard tableaux is then found as a certain limit of this function.
Nous considérons un nouveau type de partitions planes, ou de tableaux de Young, droits ou décalés, obtenus en privant leurs diagrammes de certaines cellules en haut à droite, et dans certains cas nous trouvons des formules d'énumération pour les tableaux standard. Les preuves impliquent le calcul de la fonction génératrice pour les partitions planes correspondantes, en utilisant des interprétations et des formules pour les sommes de fonctions de Schur restreintes et leurs spécialisations. Le nombre de tableaux standard est alors obtenu comme une certaine limite de cette fonction.
Isotropical Linear Spaces and Valuated Delta-Matroids
Authors: Rincón Felipe 
Published: August 2021

The spinor variety is cut out by the quadratic Wick relations among the principal Pfaffians of an $n \times n$ skew-symmetric matrix. Its points correspond to $n$-dimensional isotropic subspaces of a $2n$-dimensional vector space. In this paper we tropicalize this picture, and we develop a combinatorial theory of tropical Wick vectors and tropical linear spaces that are tropically isotropic. We characterize tropical Wick vectors in terms of subdivisions of Delta-matroid polytopes, and we examine to what extent the Wick relations form a tropical basis. Our theory generalizes several results for tropical linear spaces and valuated matroids to the class of Coxeter matroids of type $D$.
La variété spinorielle est decoupée par les relations quadratiques de Wick parmi les Pfaffiens principaux d'une matrice antisymétrique $n \times n$. Ses points correspondent aux sous-espaces isotropes à $n$ dimensions d'un espace vectoriel de dimension $2n$. Dans cet article nous tropicalisons cette description, et nous développons une théorie combinatoire de vecteurs tropicaux de Wick et d'espaces linéaires tropicaux qui sont tropicalement isotropes. Nous caractérisons des vecteurs tropicaux de Wick en termes de subdivisions des polytopes Delta-matroïde, et nous étudions dans quelle mesure les relations de Wick forment une base tropicale. Notre théorie généralise plusieurs résultats pour les espaces linéaires tropicaux et évaluait des matroïdes à la classe des matroïdes de Coxeter du type $D$.
Local extrema in random permutations and the structure of longest alternating subsequences
Authors: Romik Dan 
Published: August 2021

Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. From Stanley's result it can be shown that after rescaling, $\textbf{as}_n$ converges in the limit to the Gaussian distribution. In this extended abstract we present a new approach to the study of $\textbf{as}_n$ by relating it to the sequence of local extrema of a random permutation, which is shown to form a "canonical'' longest alternating subsequence. Using this connection we reprove the abovementioned results in a more probabilistic and transparent way. We also study the distribution of the values of the local minima and maxima, and prove that in the limit the joint distribution of successive minimum-maximum pairs converges to the two-dimensional distribution whose density function is given by $f(s,t) = 3(1-s)t e^{t-s}$.
Pour une permutation aléatoire d'ordre $n$, on désigne par $\textbf{as}_n$ la longueur maximale d'une de ses sous-suites alternantes. Stanley a étudié la distribution de $\textbf{as}_n$ en utilisant des méthodes algébriques, et il a démontré en particulier que $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ et $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. A partir du résultat de Stanley on peut montrer qu'après changement d'échelle, $\textbf{as}_n$ converge vers la distribution normale. Nous présentons ici une approche nouvelle pour l'étude de $\textbf{as}_n$, en la reliant à la suite des extrema locaux d'une permutation aléatoire, dont nous montrons qu'elle constitue une sous-suite alternante maximale "canonique''. En utilisant cette relation, nous prouvons à nouveau les résultats mentionnés ci-dessus d'une façon plus probabiliste et transparente. En plus, nous prouvons un résultat asymptotique sur la distribution limite des paires formées d'un minimum et d'un maximum locaux consécutifs.
Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs
Authors: Rubey Martin 
Published: August 2021

We show that maximal 0-1-fillings of moon polynomials, with restricted chain lengths, can be identified with certain rc-graphs, also known as pipe dreams. In particular, this exhibits a connection between maximal 0-1-fillings of Ferrers shapes and Schubert polynomials. Moreover, it entails a bijective proof showing that the number of maximal fillings of a stack polyomino $S$ with no north-east chains longer than $k$ depends only on $k$ and the multiset of column heights of $S$. Our main contribution is a slightly stronger theorem, which in turn leads us to conjecture that the poset of rc-graphs with covering relation given by generalised chute moves is in fact a lattice.
Nous démontrons que les remplissages maximaux avec 0 et 1 des polyominos $L$-convexes, avec longueurs de chaînes restreintes, peuvent être identifiés avec certains $\textit{rc-graphes}$, également connus sous le nom de $\textit{pipe dreams}$. En particulier, ceci montre un lien entre ces remplissages d'un diagramme de Ferrers et les polynômes de Schubert. On en déduit en outre une preuve bijective du fait que le nombre de remplissages maximaux d'un $\textit{stack polyomino}$ $S$, avec longueurs de chaînes bornées par un entier $k$, dépend seulement de $k$ et du multi-ensemble des tailles des colonnes de $S$. Notre contribution principale est un énoncé un peu plus fort, qui nous mène à conjecturer que l'ensemble ordonné (poset) des $\textit{rc-graphes}$ est en fait un treillis.
The equivariant topology of stable Kneser graphs
Authors: Schultz Carsten 
Published: August 2021

Schrijver introduced the stable Kneser graph $SG_{n,k}, n \geq 1, k \geq 0$. This graph is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$. Björner and de Longueville have shown that its box complex is homotopy equivalent to a sphere, $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. The dihedral group $D_{2m}$ acts canonically on $SG_{n,k}$. We study the $D_{2m}$ action on $\mathrm{Hom}(K_2,SG_{n,k})$ and define a corresponding orthogonal action on $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. We establish a close equivariant relationship between the graphs $SG_{n,k}$ and Borsuk graphs of the $k$-sphere and use this together with calculations in the $\mathbb{Z}_2$-cohomology ring of $D_{2m}$ to tell which stable Kneser graphs are test graphs in the sense of Babson and Kozlov. The graphs $SG_{2s,4}$ are test graphs, i.e. for every graph $H$ and $r \geq 0$ such that $\mathrm{Hom}(SG_{2s,4},H)$ is $(r-1)$-connected, the chromatic number $\chi (H)$ is at least $r+6$. On the other hand, if $k \notin \{0,1,2,4,8\}$ and $n \geq N(k)$ then $SG_{n,k}$ is not a homotopy test graph, i.e. there are a graph $G$ and an $r \geq 1$ such that $\mathrm{Hom}(SG_{n,k}, G)$ is $(r-1)$-connected and $\chi (G) < r+k+2$. The latter result also depends on a new necessary criterion for being a test graph, which involves the automorphism group of the graph.
Schrijver a défini le graphe de Kneser stable $SG_{n,k}$, avec $n \geq 1$ et $k \geq 0$. Le graphe $SG_{n,k}$ est un graphe critique (par rapport aux sommets) de nombre chromatique $k+2$, dont les sommets correspondent à certains sous-ensembles d'un ensemble de cardinalité $m=2n+k$. Björner et de Longueville ont démontré que son complexe de boîtes et la sphère sont homotopiquement équivalents, c'est-à-dire $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. Le groupe diédral $D_{2m}$ agit sur $SG_{n,k}$ canoniquement. Nous étudions l'action de $D_{2m}$ sur $\mathrm{Hom}(K_2,SG_{n,k})$ et nous définissons une action orthogonale correspondante sur $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. Par ailleurs, nous fournissons une relation équivariante étroite entre les graphes $SG_{n,k}$ et les graphes de Borsuk de la sphère de dimension $k$. Utilisant cette relation et certains calculs dans l'anneau de cohomologie de $D_{2m}$ sur $\mathbb{Z}_2$, nous décrivons quels graphes de Kneser stables sont des graphes de tests selon la notion de Babson et Kozlov. Les graphes $SG_{2s,4}$ sont des graphes de tests, c'est-à-dire que pour tout $H$ et $r \geq 0$ tels que $\mathrm{Hom}(SG_{2s,4},H)$ est $(r-1)$-connexe, le nombre chromatique $\chi (H)$ est au moins $r+6$. D'autre part, si $k \notin \{0,1,2,4,8\}$ et $n \geq N(k)$, alors $SG_{n,k}$ n'est pas un graphe de tests d'homologie: il existe un graphe $G$ et un entier $r \geq 1$ tels que $\mathrm{Hom}(SG_{n,k}, G)$ est $(r-1)$-connexe et $\chi (G) < r+k+2$. Ce dernier résultat dépend d'un nouveau critère nécessaire pour être un graphe de tests, qui implique le groupe d'automorphismes du graphe.
Generalized triangulations, pipe dreams, and simplicial spheres
Authors: Serrano Luis , Stump Christian 
Published: August 2021

We exhibit a canonical connection between maximal $(0,1)$-fillings of a moon polyomino avoiding north-east chains of a given length and reduced pipe dreams of a certain permutation. Following this approach we show that the simplicial complex of such maximal fillings is a vertex-decomposable and thus a shellable sphere. In particular, this implies a positivity result for Schubert polynomials. For Ferrers shapes, we moreover construct a bijection to maximal fillings avoiding south-east chains of the same length which specializes to a bijection between $k$-triangulations of the $n$-gon and $k$-fans of Dyck paths. Using this, we translate a conjectured cyclic sieving phenomenon for $k$-triangulations with rotation to $k$-flagged tableaux with promotion.
Nous décrivons un lien canonique entre les $(0,1)$-remplissages maximaux d'un polyomino-lune évitant les chaînes Nord-Est d'une longueur donnée, et les "pipe dreams'' réduits d'une certaine permutation. En suivant cette approche nous montrons que le complexe simplicial de tels remplissages maximaux est une sphère "vertex-decomposable'' et donc "shellable''. En particulier, cela entraîne un résultat de positivité sur les polynômes de Schubert. De plus, nous construisons, dans le cas des diagrammes de Ferrers, une bijection vers les remplissages maximaux évitant les chaînes Sud-Est de même longueur, qui se spécialise en une bijection entre les $k$-triangulations d'un $n$-gone et les $k$-faisceaux de chemins de Dyck. A l'aide de celle-ci, nous traduisons une instance conjecturale du phénomène de tamis cyclique pour les $k$-triangulations avec rotation dans le cadre des tableaux $k$-marqués avec promotion.
A $q$-analog of Ljunggren's binomial congruence
Authors: Straub Armin 
Published: August 2021

We prove a $q$-analog of a classical binomial congruence due to Ljunggren which states that $\binom{ap}{bp} \equiv \binom{a}{b}$ modulo $p^3$ for primes $p \geq 5$. This congruence subsumes and builds on earlier congruences by Babbage, Wolstenholme and Glaisher for which we recall existing $q$-analogs. Our congruence generalizes an earlier result of Clark.
Nous démontrons un $q$-analogue d'une congruence binomiale classique de Ljunggren qui stipule: $\binom{ap}{bp} \equiv \binom{a}{b}$ modulo $p^3$ pour $p$ premier tel que $p \geq 5$. Cette congruence s'inspire d'une précédente congruence prouvée par Babbage, Wolstenholme et Glaisher pour laquelle nous présentons les $q$-analogues existantes. Notre congruence généralise un précédent résultat de Clark.