bluuebunny/crossref_metadata_2025 huggingface dataset:
A topological interpretation of the cyclotomic polynomial
Authors: Musiker Gregg , Reiner Victor
Published: August 2021

We interpret the coefficients of the cyclotomic polynomial in terms of simplicial homology.

Nous donnons une interprétation des coefficients du polynôme cyclotomique en utilisant l'homologie simpliciale.
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.
Performance analysis of demodulation with diversity - A combinatorial approach I : Symmetric function theoretical methods
Authors: Dornstetter Jean Louis , Krob Daniel , Thibon Jean-Yves , Vassilieva Ekaterina
Published: August 2021

We present symmetric function theoretical methods for solving a performance analysis problem related with modulation protocols with diversity.
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.
Noncommutative Symmetric Hall-Littlewood Polynomials
Authors: Tevlin Lenny
Published: August 2021

Noncommutative symmetric functions have many properties analogous to those of classical (commutative) symmetric functions. For instance, ribbon Schur functions (analogs of the classical Schur basis) expand positively in noncommutative monomial basis. More of the classical properties extend to noncommutative setting as I will demonstrate introducing a new family of noncommutative symmetric functions, depending on one parameter. It seems to be an appropriate noncommutative analog of the Hall-Littlewood polynomials.

Les fonctions symétriques non commutatives ont de nombreuses propriétés analogues à celles des fonctions symétriques classiques (commutatives). Par exemple, les fonctions de Schur en rubans (analogues de la base de Schur classique) admettent des développements à coefficients positifs dans la base des monômes non commutatifs. La plupart des propriétés classiques s'étendent au cas non commutatif, comme je le montrerai en introduisant une nouvelle famille de fonctions symétriques non commutatives, dépendant d'un paramètre. Cette famille semble être un analogue non commutatif approprié de la famille des polynômes de Hall-Littlewood.
On the monotone hook hafnian conjecture
Authors: Visontai Mirkó
Published: August 2021

We investigate a conjecture of Haglund that asserts that certain graph polynomials have only real roots. We prove a multivariate generalization of this conjecture for the special case of threshold graphs.

Nous étudions une conjecture de Haglund qui affirme que certaines polynômes des graphes ont uniquement des racines réelles. Nous prouvons une généralisation multivariée de cette conjecture pour le cas particulier des graphes à seuil.
The structure of communication problems in cellular automata
Authors: Briceño Raimundo , Meunier Pierre-Etienne
Published: August 2021

Studying cellular automata with methods from communication complexity appears to be a promising approach. In the past, interesting connections between communication complexity and intrinsic universality in cellular automata were shown. One of the last extensions of this theory was its generalization to various "communication problems'', or "questions'' one might ask about the dynamics of cellular automata. In this article, we aim at structuring these problems, and find what makes them interesting for the study of intrinsic universality and quasi-orders induced by simulation relations.
On death processes and urn models
Authors: Kuba Markus , Panholzer Alois
Published: August 2021

We use death processes and embeddings into continuous time in order to analyze several urn models with a diminishing content. In particular we discuss generalizations of the pill's problem, originally introduced by Knuth and McCarthy, and generalizations of the well known sampling without replacement urn models, and OK Corral urn models.
Asymptotics of Divide-And-Conquer Recurrences Via Iterated Function Systems
Authors: Kieffer John
Published: August 2021

Let $k≥2$ be a fixed integer. Given a bounded sequence of real numbers $(a_n:n≥k)$, then for any sequence $(f_n:n≥1)$ of real numbers satisfying the divide-and-conquer recurrence $f_n = (k-mod(n,k))f_⌊n/k⌋+mod(n,k)f_⌈n/k⌉ + a_n, n ≥k$, there is a unique continuous periodic function $f^*:\mathbb{R}→\mathbb{R}$ with period 1 such that $f_n = nf^*(\log _kn)+o(n)$. If $(a_n)$ is periodic with period $k, a_k=0$, and the initial conditions $(f_i:1 ≤i ≤k-1)$ are all zero, we obtain a specific iterated function system $S$, consisting of $k$ continuous functions from $[0,1]×\mathbb{R}$ into itself, such that the attractor of $S$ is $\{(x,f^*(x)): 0 ≤x ≤1\}$. Using the system $S$, an accurate plot of $f^*$ can be rapidly obtained.
Additive tree functionals with small toll functions and subtrees of random trees
Authors: Wagner Stephan
Published: August 2021

Many parameters of trees are additive in the sense that they can be computed recursively from the sum of the branches plus a certain toll function. For instance, such parameters occur very frequently in the analysis of divide-and-conquer algorithms. Here we are interested in the situation that the toll function is small (the average over all trees of a given size $n$ decreases exponentially with $n$). We prove a general central limit theorem for random labelled trees and apply it to a number of examples. The main motivation is the study of the number of subtrees in a random labelled tree, but it also applies to classical instances such as the number of leaves.
Domination analysis for scheduling on non preemptive uniformly related machines
Authors: Eisner Idan , Vainshtein Alek
Published: August 2021

no abstract
On total variation approximations for random assemblies
Authors: Manstavičius Eugenijus
Published: August 2021

We prove a total variation approximation for the distribution of component vector of a weakly logarithmic random assembly. The proof demonstrates an analytic approach based on a comparative analysis of the coefficients of two power series.
Upper bounds on the non-3-colourability threshold of random graphs
Authors: Fountoulakis Nikolaos , McDiarmid Colin
Published: August 2021

We present a full analysis of the expected number of 'rigid' 3-colourings of a sparse random graph. This shows that, if the average degree is at least 4.99, then as n → ∞ the expected number of such colourings tends to 0 and so the probability that the graph is 3-colourable tends to 0. (This result is tight, in that with average degree 4.989 the expected number tends to ∞.) This bound appears independently in Kaporis \textitet al. [Kap]. We then give a minor improvement, showing that the probability that the graph is 3-colourable tends to 0 if the average degree is at least 4.989.
Generic properties of random subgroups of a free group for general distributions
Authors: Bassino Frédérique , Nicaud Cyril , Weil Pascal
Published: August 2021

We consider a generalization of the uniform word-based distribution for finitely generated subgroups of a free group. In our setting, the number of generators is not fixed, the length of each generator is determined by a random variable with some simple constraints and the distribution of words of a fixed length is specified by a Markov process. We show by probabilistic arguments that under rather relaxed assumptions, the good properties of the uniform word-based distribution are preserved: generically (but maybe not exponentially generically), the tuple we pick is a basis of the subgroup it generates, this subgroup is malnormal and the group presentation defined by this tuple satisfies a small cancellation condition.
Matching solid shapes in arbitrary dimension via random sampling
Authors: Schymura Daria
Published: August 2021

We give simple probabilistic algorithms that approximately maximize the volume of overlap of two solid, i.e. full-dimensional, shapes under translations and rigid motions. The shapes are subsets of $ℝ^d$ where $d≥ 2$. The algorithms approximate with respect to an pre-specified additive error and succeed with high probability. Apart from measurability assumptions, we only require that points from the shapes can be generated uniformly at random. An important example are shapes given as finite unions of simplices that have pairwise disjoint interiors.
Support and density of the limit $m$-ary search trees distribution
Authors: Chauvin Brigitte , Liu Quansheng , Pouyanne Nicolas
Published: August 2021

The space requirements of an $m$-ary search tree satisfies a well-known phase transition: when $m\leq 26$, the second order asymptotics is Gaussian. When $m\geq 27$, it is not Gaussian any longer and a limit $W$ of a complex-valued martingale arises. We show that the distribution of $W$ has a square integrable density on the complex plane, that its support is the whole complex plane, and that it has finite exponential moments. The proofs are based on the study of the distributional equation $ W \overset{\mathcal{L}}{=} \sum_{k=1}^mV_k^{\lambda}W_k$, where $V_1, ..., V_m$ are the spacings of $(m-1)$ independent random variables uniformly distributed on $[0,1]$, $W_1, ..., W_m$ are independent copies of W which are also independent of $(V_1, ..., V_m)$ and $\lambda$ is a complex number.
A phase transition in the distribution of the length of integer partitions
Authors: Ralaivaosaona Dimbinaina
Published: August 2021

We assign a uniform probability to the set consisting of partitions of a positive integer $n$ such that the multiplicity of each summand is less than a given number $d$ and we study the limiting distribution of the number of summands in a random partition. It is known from a result by Erdős and Lehner published in 1941 that the distributions of the length in random restricted $(d=2)$ and random unrestricted $(d \geq n+1)$ partitions behave very differently. In this paper we show that as the bound $d$ increases we observe a phase transition in which the distribution goes from the Gaussian distribution of the restricted case to the Gumbel distribution of the unrestricted case.
On Greedy Trie Execution
Authors: Gołębiewski Zbigniew , Zagórski Filip
Published: August 2021

In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping fair coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen. We give an answer to the question stated in the Prodinger's paper – what happens if not a 0-party is recursively looking for a leader but always a party with a smaller cardinality. We show the lower bound on the number of rounds of the greedy algorithm (for fair coin).
Analysis of Digital Expansions of Minimal Weight
Authors: Heigl Florian , Heuberger Clemens
Published: August 2021

Extending an idea of Suppakitpaisarn, Edahiro and Imai, a dynamic programming approach for computing digital expansions of minimal weight is transformed into an asymptotic analysis of minimal weight expansions. The minimal weight of an optimal expansion of a random input of length $\ell$ is shown to be asymptotically normally distributed under suitable conditions. After discussing the general framework, we focus on expansions to the base of $\tau$, where $\tau$ is a root of the polynomial $X^2- \mu X + 2$ for $\mu \in \{ \pm 1\}$. As the Frobenius endomorphism on a binary Koblitz curve fulfils the same equation, digit expansions to the base of this $\tau$ can be used for scalar multiplication and linear combination in elliptic curve cryptosystems over these curves.
Toward the asymptotic count of bi-modular hidden patterns under probabilistic dynamical sources: a case study
Authors: Lhote Loïck , Lladser Manuel E.
Published: August 2021

Consider a countable alphabet $\mathcal{A}$. A multi-modular hidden pattern is an $r$-tuple $(w_1,\ldots , w_r)$, where each $w_i$ is a word over $\mathcal{A}$ called a module. The hidden pattern is said to occur in a text $t$ when the later admits the decomposition $t = v_0 w_1v_1 \cdots v_{r−1}w_r v_r$, for arbitrary words $v_i$ over $\mathcal{A}$. Flajolet, Szpankowski and Vallée (2006) proved via the method of moments that the number of matches (or occurrences) with a multi-modular hidden pattern in a random text $X_1\cdots X_n$ is asymptotically Normal, when $(X_n)_{n\geq1}$ are independent and identically distributed $\mathcal{A}$-valued random variables. Bourdon and Vallée (2002) had conjectured however that asymptotic Normality holds more generally when $(X_n)_{n\geq1}$ is produced by an expansive dynamical source. Whereas memoryless and Markovian sequences are instances of dynamical sources with finite memory length, general dynamical sources may be non-Markovian i.e. convey an infinite memory length. The technical difficulty to count hidden patterns under sources with memory is the context-free nature of these patterns as well as the lack of logarithm-and exponential-type transformations to rewrite the product of non-commuting transfer operators. In this paper, we address a case study in which we have successfully overpassed the aforementioned difficulties and which may illuminate how to address more general cases via auto-correlation operators. Our main result shows that the number of matches with a bi-modular pattern $(w_1, w_2)$ normalized by the number of matches with the pattern $w_1$, where $w_1$ and $w_2$ are different alphabet characters, is indeed asymptotically Normal when $(X_n)_{n\geq1}$ is produced by a holomorphic probabilistic dynamical source.
Crystal energy via charge
Authors: Lenart Cristian , Schilling Anne
Published: August 2021

The Ram–Yip formula for Macdonald polynomials (at t=0) provides a statistic which we call charge. In types ${A}$ and ${C}$ it can be defined on tensor products of Kashiwara–Nakashima single column crystals. In this paper we show that the charge is equal to the (negative of the) energy function on affine crystals. The algorithm for computing charge is much simpler than the recursive definition of energy in terms of the combinatorial ${R}$-matrix.

La formule de Ram et Yip pour les polynômes de Macdonald (à t = 0) fournit une statistique que nous appelons la charge. Dans les types ${A}$ et ${C}$, elle peut être définie sur les produits tensoriels des cristaux pour les colonnes de Kashiwara–Nakashima. Dans ce papier, nous montrons que la charge est égale à (l'opposé de) la fonction d'énergie sur cristaux affines. L'algorithme pour calculer la charge est bien plus simple que la définition récursive de l'énergie en fonction de la ${R}$-matrice combinatoire.
The Möbius function of generalized subword order
Authors: McNamara Peter R. W. , Sagan Bruce E.
Published: August 2021

Let $P$ be a poset and let $P^*$ be the set of all finite length words over $P$. Generalized subword order is the partial order on $P^*$ obtained by letting $u≤ w$ if and only if there is a subword $u'$ of $w$ having the same length as $u$ such that each element of $u$ is less than or equal to the corresponding element of $u'$ in the partial order on $P$. Classical subword order arises when $P$ is an antichain, while letting $P$ be a chain gives an order on compositions. For any finite poset $P$, we give a simple formula for the Möbius function of $P^*$ in terms of the Möbius function of $P$. This permits us to rederive in an easy and uniform manner previous results of Björner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in $P^*$ for any finite $P$ of rank at most 1.

Soit $P$ un ensemble partiellement ordonné et soit $P^*$ l'ensemble des mots de longueur finie sur $P$. On définit l'ordre des sous-mots généralisé comme l'ordre partiel sur $P^*$ obtenu en posant $u≤ w$ s'il existe un sous-mot $u'$ de $w$ ayant la même longueur que $u$, tel que chaque élément de $u$ soit plus petit ou égal à l'élément correspondant de $u'$ dans l'ordre partiel sur $P$. L'ordre des sous-mots classique correspond au cas où $P$ est une antichaîne ; tandis que si P est une chaîne, on obtient un ordre sur les compositions. Pour tout ensemble partiellement ordonné fini $P$, nous donnons une formule simple pour la fonction de Möbius de $P^*$ en fonction de celle de $P$. Cela nous permet de retrouver de manière simple et uniforme des résultats de Björner, Sagan et Vatter, et de Tomie. Nous sommes aussi en mesure de déterminer le type d'homotopie de tous les intervalles de $P^*$ pour n'importe quel $P$ fini de rang au plus 1.
Modified Growth Diagrams, Permutation Pivots, and the BWX Map $\phi^*$
Authors: Bloom Jonathan , Saracino Dan
Published: August 2021

In their paper on Wilf-equivalence for singleton classes, Backelin, West, and Xin introduced a transformation $\phi^*$, defined by an iterative process and operating on (all) full rook placements on Ferrers boards. Bousquet-Mélou and Steingrimsson proved the analogue of the main result of Backelin, West, and Xin in the context of involutions, and in so doing they needed to prove that $\phi^*$ commutes with the operation of taking inverses. The proof of this commutation result was long and difficult, and Bousquet-Mélou and Steingrimsson asked if $\phi^*$ might be reformulated in such a way as to make this result obvious. In the present paper we provide such a reformulation of $\phi^*$, by modifying the growth diagram algorithm of Fomin. This also answers a question of Krattenthaler, who noted that a bijection defined by the unmodified Fomin algorithm obviously commutes with inverses, and asked what the connection is between this bijection and $\phi^*$.

Dans leur article sur l'équivalence de Wilf pour les classes de singletons, Backelin, West et Xin ont introduit une transformation $\phi^*$, définie par un processus itératif et opérant sur (tous) les placements complets de tours sur un plateau de Ferrers. Bousquet-Melou et Steingrimsson ont démontré l'analogue du résultat principal de Backelin, West et Xin dans le contexte d'involutions, et pour ce faire ont eu besoin de démontrer que $\phi^*$ commute avec l'opération inverse. La preuve de cette commutativité est longue et difficile, et Bousquet-Melou et Steingrômsson se demandèrent s'il n'était pas possible de reformuler $\phi^*$ de sorte que le resultat devienne évident. Dans le présent article, nous proposons une telle reformulation de $\phi^*$ en modifiant l'algorithme de croissance de diagramme de Fomin. Cette reformulation répond également à une question de Krattenthaler, qui, remarquant qu'une bijection définie par l'algorithme de Fomin non modifié commute évidemment avec l'opération inverse, se demanda quel était le rapport entre cette bijection et $\phi^*$.
Probabilistic Analysis of Carlitz Compositions
Authors: Louchard Guy , Prodinger Helmut
Published: August 2021

Using generating functions and limit theorems, we obtain a stochastic description of Carlitz compositions of large integer n (i.e. compositions two successive parts of which are different). We analyze: the number M of parts, the number of compositions T(m,n) with m parts, the distribution of the last part size, the correlation between two successive parts, leading to a Markov chain. We describe also the associated processes and the limiting trajectories, the width and thickness of a composition. We finally present a typical simulation. The limiting processes are characterized by Brownian Motion and some discrete distributions.
On the degree-chromatic polynomial of a tree
Authors: Cifuentes Diego
Published: August 2021

The degree chromatic polynomial $P_m(G,k)$ of a graph $G$ counts the number of $k$ -colorings in which no vertex has m adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.

Le polynôme degré chromatique $P_m(G,k)$ d'un graphe $G$ compte le nombre de $k$-colorations dans lesquelles aucun sommet n'a m sommets adjacents de sa même couleur. On démontre la conjecture de Humpert et Martin sur les coefficients principaux du polynôme degré chromatique d'un arbre.
Symmetries of the k-bounded partition lattice
Authors: Berg Chris , Zabrocki Mike
Published: August 2021

We generalize the symmetry on Young's lattice, found by Suter, to a symmetry on the $k$-bounded partition lattice of Lapointe, Lascoux and Morse.

Nous généralisons la symétrie sur le treillis de Young, découvert par Suter, à une symétrie sur le treillis des partages bornés par $k$ et étudié par Lapointe, Lascoux and Morse.
Polynomials and Parking Functions
Authors: Hicks Angela
Published: August 2021

In a 2010 paper Haglund, Morse, and Zabrocki studied the family of polynomials $\nabla C_{p1}\dots C_{pk}1$ , where $p=(p_1,\ldots,p_k)$ is a composition, $\nabla$ is the Bergeron-Garsia Macdonald operator and the $C_\alpha$ are certain slightly modified Hall-Littlewood vertex operators. They conjecture that these polynomials enumerate a composition indexed family of parking functions by area, dinv and an appropriate quasi-symmetric function. This refinement of the nearly decade old ``Shuffle Conjecture,'' when combined with properties of the Hall-Littlewood operators can be shown to imply the existence of certain bijections between these families of parking functions. In previous work to appear in her PhD thesis, the author has shown that the existence of these bijections follows from some relatively simple properties of a certain family of polynomials in one variable x with coefficients in $\mathbb{N}[q]$. In this paper we introduce those polynomials, explain their connection to the conjecture of Haglund, Morse, and Zabrocki, and explore some of their surprising properties, both proven and conjectured.

Dans un article de 2010, Haglund, Morse et Zabrocki étudient la famille de polynômes $\nabla C_{p1}\dots C_{pk}1$ où $p=(p_1,\ldots,p_k)$ est une composition, $\nabla$ est l’opérateur de Bergeron-Garsia et les $C_\alpha$ sont des opérateurs ``vertex'' de Hall-Littlewood légèrement altérés. Il posent la conjecture que ces polynômes donnent l’énumération d'une famille de fonctions ``parking'', indexées par des compositions, par aire, le ``dinv'' et une fonction quasi-symétrique associée. Cette conjecture raffine la conjecture ``Shuffle'', qui est âgée de presque dix ans. On peut montrer, a partir de cette conjecture, que les propriétés des opérateurs de Hall-Littlewood, impliquent l'existence de certaines bijections entre ces familles de fonctions ``parking''. Dans un précédent travail , qui fait partie de sa thèse de doctorat, l'auteur montre que l’existence de ces bijections découle de certaines propriétés relativement simples d'une famille de polynômes à une variable x, avec coefficients dans $\mathbb{N}[q]$. Dans cet article, on introduit ces polynômes, on explique leur connexion avec la conjecture de Haglund, Morse et Zabrocki, et on explore certaines de leurs propriétés surprenantes, qu'elles soient prouvées ou seulement conjecturées.
An explicit formula for ndinv, a new statistic for two-shuffle parking functions
Authors: Hicks Angela , Kim Yeonkyung
Published: August 2021

In a recent paper, Duane, Garsia, and Zabrocki introduced a new statistic, "ndinv'', on a family of parking functions. The definition was guided by a recursion satisfied by the polynomial $\langle\Delta_{h_m}C_p1C_p2...C_{pk}1,e_n\rangle$, for $\Delta_{h_m}$ a Macdonald eigenoperator, $C_{p_i}$ a modified Hall-Littlewood operator and $(p_1,p_2,\dots ,p_k)$ a composition of n. Using their new statistics, they are able to give a new interpretation for the polynomial $\langle\nabla e_n, h_j h_n-j\rangle$ as a q,t numerator of parking functions by area and ndinv. We recall that in the shuffle conjecture, parking functions are q,t enumerated by area and diagonal inversion number (dinv). Since their definition is recursive, they pose the problem of obtaining a non recursive definition. We solved this problem by giving an explicit formula for ndinv similar to the classical definition of dinv. In this paper, we describe the work we did to construct this formula and to prove that the resulting ndinv is the same as the one recursively defined by Duane, Garsia, and Zabrocki.

Dans un travail récent Duane, Garsia et Zabrocki ont introduit une nouvelle statistique, "ndinv'' pour une famille de Fonctions Parking. Ce "ndinv" découle d'une récurrence satisfaite par le polynôme $\langle\Delta_{h_m}C_p1C_p2...C_{pk}1,e_n\rangle$, oú $\Delta_{h_m}$ est un opérateur linéaire avec fonctions propres les polynômes de Macdonald, les $C_{p_i}$ sont des opérateurs de Hall-Littlewood modifiés et $(p_1,p_2,\dots ,p_n)$ est un vecteur à composantes entières positives. Par moyen de cette statistique, ils ont réussi à donner une nouvelle interprétation combinatoire au polynôme $\langle\nabla e_n, h_j h_n-j\rangle$ on remplaçant "dinv'" par "ndinv". Rappelons nous que la conjecture "Shuffle"' exprime ce même polynôme comme somme pondérée de Fonctions Parking avec poids t à la "aire'" est q au "dinv". Puisque il donnent une définition récursive du "ndinv" il posent le problème de l'obtenir d'une façon directe. On rèsout se problème en donnant une formule explicite qui permet de calculer directement le "ndinv" à la manière de la formule classique du "dinv". Dans cet article on décrit le travail qu'on a fait pour construire cette formule et on démontre que nôtre formule donne le même "ndinv" récursivement construit par Duane, Garsia et Zabrocki.
Partially complemented representations of digraphs
Authors: Dahlhaus Elias , Gustedt Jens , Mcconnell Ross M.
Published: August 2021

Special issue: Graph Decompositions

A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent if one can be obtained from the other by a sequence of such operations. We show that given an adjacency-list representation of a digraph G, many fundamental graph algorithms can be carried out on any member G' of G's equivalence class in O(n+m) time, where m is the number of arcs in G, not the number of arcs in G' . This may have advantages when G' is much larger than G. We use this to generalize to digraphs a simple O(n + m log n) algorithm of McConnell and Spinrad for finding the modular decomposition of undirected graphs. A key step is finding the strongly-connected components of a digraph F in G's equivalence class, where F may have ~(m log n) arcs.
New light on Bergman complexes by decomposing matroid types
Authors: Dlugosch Martin
Published: August 2021

Bergman complexes are polyhedral complexes associated to matroids. Faces of these complexes are certain matroids, called matroid types, too. In order to understand the structure of these faces we decompose matroid types into direct summands. Ardila/Klivans proved that the Bergman Complex of a matroid can be subdivided into the order complex of the proper part of its lattice of flats. Beyond that Feichtner/Sturmfels showed that the Bergman complex can even be subdivided to the even coarser nested set complex. We will give a much shorter and more general proof of this fact. Generalizing formulas proposed by Ardila/Klivans and Feichtner/Sturmfels for special cases, we present a decomposition into direct sums working for faces of any of these complexes. Additionally we show that it is the finest possible decomposition for faces of the Bergman complex.

Les complexes de Bergmann sont des complexes polyhedrales affectès à des matroides. Les faces de ces complexes sont des matroides pour leur part, on les appelle types de matroides. Pour pouvoir comprendre ces types de matroides nous les divisons en sommes directes. Ardila et Klivans ont prouvè que le complexe de Bergman dun matroide peut être subdivisè en le complexe dordre du propre treillis des flats. Au surplus, Feichtner/Sturmfels ont pu montrer que le complexe de Bergmann peut même être subdivisè en le nested set complexe qui est encore plus grossier. Nous y prèsenterons une preuve plus courte et plus gènèrale. Nous gènèraliserons des formules qui ont dèjà ètè rèdigèes pour des cas spèciaux par Ardila/Klivans. Ainsi, nous rèvèlerons une division des types de matroides en sommes directes qui est valable tous les complexes èvoquès. De plus, nous montrerons que cette division est la division la plus fine pour les faces du complexe de Bergmann.
Constructing combinatorial operads from monoids
Authors: Giraudo Samuele
Published: August 2021

We introduce a functorial construction which, from a monoid, produces a set-operad. We obtain new (symmetric or not) operads as suboperads or quotients of the operad obtained from the additive monoid. These involve various familiar combinatorial objects: parking functions, packed words, planar rooted trees, generalized Dyck paths, Schröder trees, Motzkin paths, integer compositions, directed animals, etc. We also retrieve some known operads: the magmatic operad, the commutative associative operad, and the diassociative operad.
Consecutive patterns in permutations: clusters and generating functions
Authors: Elizalde Sergi , Noy Marc
Published: August 2021

We use the cluster method in order to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new ones, including some patterns of length 4 and 5, as well as some infinite families of patterns of a given shape. Our main tool is the cluster method of Goulden and Jackson. We also prove some that, for a large class of patterns, the inverse of the exponential generating function counting occurrences is an entire function, but we conjecture that it is not D-finite in general.

On utilise la mèthode des clusters pour ènumèrer permutations qui èvitent motifs consècutifs. On redèmontre et on gènèralise d'une manière unifièe plusieurs rèsultats et on obtient de nouveaux rèsultats pour certains motifs de longueur 4 et 5, ainsi que pour certaines familles infinies de motifs. L'outil principal c'est la mèthode des clusters de Goulden et Jackson. On dèmontre aussi que, pour une grande classe de motifs, l'inverse de la sèrie gènèratrice exponentielle qui compte occurrences est une fonction entière, mais on conjecture qu'elle n'est pas D-finie en gènèral.
Arc Permutations (extended abstract)
Authors: Elizalde Sergi , Roichman Yuval
Published: August 2021

Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. In this paper we describe combinatorial properties of these permutations, including characterizations in terms of pattern avoidance, connections to Young tableaux, and an affine Weyl group action on them.

Les permutations arc et les permutations unimodales ont ètè introduites dans l'étude des triangulations et des caractères. Dans cet article, on dècrit les propriètès combinatoires de ces permutations, y compris des caractèrisations en termes de motifs interdits, des connexions avec des tableaux de Young, et une action du groupe de Weyl affine.
Arithmetic matroids and Tutte polynomials
Authors: D'Adderio Michele , Moci Luca
Published: August 2021

We introduce the notion of arithmetic matroid, whose main example is provided by a list of elements in a finitely generated abelian group. We study the representability of its dual, and, guided by the geometry of toric arrangements, we give a combinatorial interpretation of the associated arithmetic Tutte polynomial, which can be seen as a generalization of Crapo's formula.

Nous introduisons la notion de matroï de arithmètique, dont le principal exemple est donnè par une liste d'élèments dans un groupe abèlien fini. Nous ètudions la reprèsentabilitè de son dual, et, guidè par la gèomètrie des arrangements toriques, nous donnons une interprètation combinatoire du polynôme de Tutte arithmètique associèe, ce qui peut être vu comme une gènèralisation de la formule de Crapo.