bluuebunny/crossref_metadata_2025_split huggingface dataset:
Ehrhart Positivity for Generalized Permutohedra
Authors: Castillo Federico , Liu Fu 
Published: August 2021

There are few general results about the coefficients of Ehrhart polynomials. We present a conjecture about their positivity for a certain family of polytopes known as generalized permutohedra. We have verified the conjecture for small dimensions combining perturbation methods with a new valuation on the algebra of rational pointed polyhedral cones constructed by Berline and Vergne.
Il existe peu de résultats sur les coefficients des polynômes d’Ehrhart. On présente une conjecture concernant leur positivité pour une certaine famille de polytopes connus sous le nom de permutoèdre généralisé. On a vérifié la conjecture pour les petites dimensions en combinant des méthodes de perturbation avec une nouvelle valuation sur l’algèbre des cônes polyédraux rationnels pointés, construite par Berline et Vergne.
The Real-rootedness of Eulerian Polynomials via the Hermite–Biehler Theorem
Authors: Yang Arthur L.B. , Zhang Philip B. 
Published: August 2021

Based on the Hermite–Biehler theorem, we simultaneously prove the real-rootedness of Eulerian polynomials of type $D$ and the real-rootedness of affine Eulerian polynomials of type $B$, which were first obtained by Savage and Visontai by using the theory of $s$-Eulerian polynomials. We also confirm Hyatt’s conjectures on the inter-lacing property of half Eulerian polynomials. Borcea and Brändén’s work on the characterization of linear operators preserving Hurwitz stability is critical to this approach.
Basé sur le théorème de Hermite–Biehler, nous prouvons simultanément les polynômes eulériens de type $D$ et les polynômes eulériens affine de type $B$ ont seulement racines réelle, qui sont d’abord obtenue par Savage et Visontai en utilisant le théorie des polynômes $s$-eulériens. Nous confirmons aussi les conjectures de Hyatt sur la propriété entrelacement de polynômes mi-eulériens. Le travail de Borcea et Brändén sur la caractérisation des opérateurs linéaires préservant la stabilité Hurwitz est essentielle à cette approche.
Spanning forests, electrical networks, and a determinant identity
Authors: Teufl Elmar , Wagner Stephan 
Published: August 2021

We aim to generalize a theorem on the number of rooted spanning forests of a highly symmetric graph to the case of asymmetric graphs. We show that this can be achieved by means of an identity between the minor determinants of a Laplace matrix, for which we provide two different (combinatorial as well as algebraic) proofs in the simplest case. Furthermore, we discuss the connections to electrical networks and the enumeration of spanning trees in sequences of self-similar graphs.
Nous visons à généraliser un théorème sur le nombre de forêts couvrantes d'un graphe fortement symétrique au cas des graphes asymétriques. Nous montrons que cela peut être obtenu au moyen d'une identité sur les déterminants mineurs d'une matrice Laplacienne, pour laquelle nous donnons deux preuves différentes (combinatoire ou bien algébrique) dans le cas le plus simple. De plus, nous discutons les relations avec des réseaux électriques et l'énumération d'arbres couvrants dans de suites de graphes autosimilaires.
The Discrete Fundamental Group of the Associahedron
Authors: Severs Christopher , White Jacob 
Published: August 2021

The associahedron is an object that has been well studied and has numerous applications, particularly in the theory of operads, the study of non-crossing partitions, lattice theory and more recently in the study of cluster algebras. We approach the associahedron from the point of view of discrete homotopy theory, that is we consider 5-cycles in the 1-skeleton of the associahedron to be combinatorial holes, but 4-cycles to be contractible. We give a simple description of the equivalence classes of 5-cycles in the 1-skeleton and then identify a set of 5-cycles from which we may produce all other cycles. This set of 5-cycle equivalence classes turns out to be the generating set for the abelianization of the discrete fundamental group of the associahedron. In this paper we provide presentations for the discrete fundamental group and the abelianization of the discrete fundamental group. We also discuss applications to cluster algebras as well as generalizations to type B and D associahedra. \par
L'associahèdre est un objet bien etudié que l'on retrouve dans plusieurs contextes. Par exemple, il est associé à la théorie des opérades, à l'étude des partitions non-croisées, à la théorie des treillis et plus récemment aux algèbres dámas. Nous étudions cet objet par le biais de la théorie des homotopies discretes. En bref cette théorie signifie qu'un cycle de longueur 5 (sur le squelette de l'associahèdre) est considéré comme étant le bord d'un trou combinatoire, alors qu'un cycle de longueur 4 peut être contracté sans problème. Les classes d'homotopies discrètes sont donc des classes d'équivalence de cycles de longueurs 5. Nous donnons une description simple de ces classes d'équivalence et identifions un ensemble de générateurs du groupe correspondant (abélien) d'homotopies discrètes. Nous d'ecrivons également les liens entre notre construction et les algèbres d'amas.
$m$-noncrossing partitions and $m$-clusters
Authors: Bakke Buan Aslak , Reiten Idun , Thomas Hugh 
Published: August 2021

Let $W$ be a finite crystallographic reflection group, with root system $\Phi$. Associated to $W$ there is a positive integer, the generalized Catalan number, which counts the clusters in the associated cluster algebra, the noncrossing partitions for $W$, and several other interesting sets. Bijections have been found between the clusters and the noncrossing partitions by Reading and Athanasiadis et al. There is a further generalization of the generalized Catalan number, sometimes called the Fuss-Catalan number for $W$, which we will denote $C_m(W)$. Here $m$ is a positive integer, and $C_1(W)$ is the usual generalized Catalan number. $C_m(W)$ counts the $m$-noncrossing partitions for $W$ and the $m$-clusters for $\Phi$. In this abstract, we will give an explicit description of a bijection between these two sets. The proof depends on a representation-theoretic reinterpretation of the problem, in terms of exceptional sequences of representations of quivers.
Soit $W$ un groupe de réflexions fini et cristallographique, avec système de racines $\Phi$. Associé à $W$, il y a un entier positif, le nombre de Catalan généralisé, qui compte les amas dans l'algèbre amassée associée, les partitions non-croisées de $W$, et plusieurs autres ensembles intéressantes. Des bijections entre les amas et les partitions non-croisées ont été données par Reading et Athanasiadis et al. On peut encore généraliser le nombre de Catalan généralisé, obtenant le nombre Fuss-Catalan de $W$, que nous noterons $C_m(W)$. Ici $m$ est un entier positif, et $C_1(W)$ est le nombre Catalan généralisé standard. $C_m(W)$ compte les partitions $m$-non-croisées de $W$ et les $m$-amas de $\Phi$. Dans ce résumé, nous donnerons une bijection explicite entre ces deux ensembles. La démonstration dépend d'une réinterprétation des objets du point de vue des suites exceptionnelles de représentations de carquois.
Unlabeled $(2+2)$-free posets, ascent sequences and pattern avoiding permutations
Authors: Bousquet-Mélou Mireille , Claesson Anders , Dukes Mark , Kitaev Sergey 
Published: August 2021

We present statistic-preserving bijections between four classes of combinatorial objects. Two of them, the class of unlabeled $(\textrm{2+2})$-free posets and a certain class of chord diagrams (or involutions), already appeared in the literature, but were apparently not known to be equinumerous. The third one is a new class of pattern avoiding permutations, and the fourth one consists of certain integer sequences called $\textit{ascent sequences}$. We also determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $3\bar{1}52\bar{4}$, and enumerate those permutations, thus settling a conjecture of Pudwell.
Nous présentons des bijections, transportant de nombreuses statistiques, entre quatre classes d'objets. Deux d'entre elles, la classe des EPO (ensembles partiellement ordonnés) sans motif $(\textrm{2+2})$ et une certaine classe d'involutions, sont déjà apparues dans la littérature. La troisième est une classe de permutations à motifs exclus, et la quatrième une classe de suites que nous appelons $\textit{suites à montées}$. Nous déterminons ensuite la série génératrice de ces classes, retrouvant ainsi un résultat prouvé par Zagier pour les involutions sus-mentionnées. La série obtenue n'est pas D-finie. Apparemment, le fait qu'elle compte aussi les EPO sans motif $(\textrm{2+2})$ est nouveau. Finalement, nous caractérisons les suites à montées qui correspondent aux permutations évitant le motif barré $3\bar{1}52\bar{4}$ et énumérons ces permutations, ce qui démontre une conjecture de Pudwell.
Universal cycles for permutation classes
Authors: Albert Michael , West Julian 
Published: August 2021

We define a universal cycle for a class of $n$-permutations as a cyclic word in which each element of the class occurs exactly once as an $n$-factor. We give a general result for cyclically closed classes, and then survey the situation when the class is defined as the avoidance class of a set of permutations of length $3$, or of a set of permutations of mixed lengths $3$ and $4$.
Nous définissons un cycle universel pour une classe de $n$-permutations comme un mot cyclique dans lequel chaque élément de la classe apparaît une unique fois comme $n$-facteur. Nous donnons un résultat général pour les classes cycliquement closes, et détaillons la situation où la classe de permutations est définie par motifs exclus, avec des motifs de taille $3$, ou bien à la fois des motifs de taille $3$ et de taille $4$.
Median clouds and a fast transposition median solver
Authors: Eriksen Niklas 
Published: August 2021

The median problem seeks a permutation whose total distance to a given set of permutations (the base set) is minimal. This is an important problem in comparative genomics and has been studied for several distance measures such as reversals. The transposition distance is less relevant biologically, but it has been shown that it behaves similarly to the most important biological distances, and can thus give important information on their properties. We have derived an algorithm which solves the transposition median problem, giving all transposition medians (the median cloud). We show that our algorithm can be modified to accept median clouds as elements in the base set and briefly discuss the new concept of median iterates (medians of medians) and limit medians, that is the limit of this iterate.
Le problème de la médiane est de trouver une permutation dont la distance totale à un ensemble donné de permutations (l´ensemble de base) est minimale. C'est un problème important en génomique comparative et il a été étudié pour certaines mesures de distance. La distance de transposition n'est pas directement liée à la biologie, mais il a été démontré que son comportement est similaire à celui des distances biologiques essentielles, et elle peut donc donner des indications sur leurs propriétés. Nous construisons un algorithme qui résout le problème de la médiane pour la transposition, et donne toutes les transpositions médianes (le nuage des médianes). Nous démontrons que notre algorithme peut être modifié pour admettre des nuages de médianes comme éléments de l´ensemble de base et introduisons le concept de médianes itérées (médianes de médianes) et de médianes limites, c-à-d de limites de ces itérations.
Counting Quiver Representations over Finite Fields Via Graph Enumeration
Authors: Helleloid Geir , Rodriguez-Villegas Fernando 
Published: August 2021

Let $\Gamma$ be a quiver on $n$ vertices $v_1, v_2, \ldots , v_n$ with $g_{ij}$ edges between $v_i$ and $v_j$, and let $\boldsymbol{\alpha} \in \mathbb{N}^n$. Hua gave a formula for $A_{\Gamma}(\boldsymbol{\alpha}, q)$, the number of isomorphism classes of absolutely indecomposable representations of $\Gamma$ over the finite field $\mathbb{F}_q$ with dimension vector $\boldsymbol{\alpha}$. We use Hua's formula to show that the derivatives of $A_{\Gamma}(\boldsymbol{\alpha}, q)$ with respect to $q$, when evaluated at $q = 1$, are polynomials in the variables $g_{ij}$, and we can compute the highest degree terms in these polynomials. The formulas for these coefficients depend on the enumeration of certain families of connected graphs. This note simply gives an overview of these results; a complete account of this research is available on the arXiv and has been submitted for publication.
Soit $\Gamma$ un carquois sur $n$ sommets $ v_1, v_2, \ldots , v_n$ avec $g_{ij}$ arêtes entre $v_i$ et $v_j$, et soit $\boldsymbol{\alpha} \in \mathbb{N}^n$. Hua a donné une formule pour $A_{\Gamma}(\boldsymbol{\alpha}, q)$, le nombre de classes d'isomorphisme absolument indécomposables de représentations de $\Gamma$ sur le corps fini $\mathbb{F}_q$ avec vecteur de dimension $\boldsymbol{\alpha}$. Nous utilisons la formule de Hua pour montrer que les dérivées de $A_{\Gamma}(\boldsymbol{\alpha}, q)$ par rapport à $q$, alors évaluée à $q=1$, sont des polynômes dans les variables $g_{ij}$, et on peut calculer les termes de plus haut degré de ces polynômes. Les formules pour ces coefficients dépendent de l'énumération de certaines familles de graphes connectés. Cette note donne simplement un aperçu de ces résultats, un compte rendu complet de cette recherche est disponible sur arXiv et a été soumis pour publication.
Permutations realized by shifts
Authors: Elizalde Sergi 
Published: August 2021

A permutation $\pi$ is realized by the shift on $N$ symbols if there is an infinite word on an $N$-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as $\pi$. The set of realized permutations is closed under consecutive pattern containment. Permutations that cannot be realized are called forbidden patterns. It was shown in [J.M. Amigó, S. Elizalde and M. Kennel, $\textit{J. Combin. Theory Ser. A}$ 115 (2008), 485―504] that the shortest forbidden patterns of the shift on $N$ symbols have length $N+2$. In this paper we give a characterization of the set of permutations that are realized by the shift on $N$ symbols, and we enumerate them with respect to their length.
Une permutation $\pi$ est réalisée par le $\textit{shift}$ avec $N$ symboles s'il y a un mot infini sur un alphabet de $N$ lettres dont les déplacements successifs d'une position à gauche sont lexicographiquement dans le même ordre relatif que $\pi$. Les permutations qui ne sont pas réalisées s'appellent des motifs interdits. On sait [J.M. Amigó, S. Elizalde and M. Kennel, $\textit{J. Combin. Theory Ser. A}$ 115 (2008), 485―504] que les motifs interdits les plus courts du $\textit{shift}$ avec $N$ symboles ont longueur $N+2$. Dans cet article on donne une caractérisation des permutations réalisées par le $\textit{shift}$ avec $N$ symboles, et on les dénombre selon leur longueur.
Indecomposable permutations with a given number of cycles
Authors: Cori Robert , Mathieu Claire 
Published: August 2021

A permutation $a_1a_2 \ldots a_n$ is $\textit{indecomposable}$ if there does not exist $p \lt n$ such that $a_1a_2 \ldots a_p$ is a permutation of $\{ 1,2, \ldots ,p\}$. We compute the asymptotic probability that a permutation of $\mathbb{S}_n$ with $m$ cycles is indecomposable as $n$ goes to infinity with $m/n$ fixed. The error term is $O(\frac{\log(n-m)}{ n-m})$. The asymptotic probability is monotone in $m/n$, and there is no threshold phenomenon: it degrades gracefully from $1$ to $0$. When $n=2m$, a slight majority ($51.1 \ldots$ percent) of the permutations are indecomposable. We also consider indecomposable fixed point free involutions which are in bijection with maps of arbitrary genus on orientable surfaces, for these involutions with $m$ left-to-right maxima we obtain a lower bound for the probability of being indecomposable.
Une permutation $a_1a_2 \ldots a_n$ est $\textit{indécomposable}$, s’il n’existe pas de $p \lt n$ tel que $a_1a_2 \ldots a_p$ est une permutation de $\{ 1,2, \ldots ,p\}$. Nous calculons la probabilité pour qu’une permutation de $\mathbb{S}_n$ ayant $m$ cycles soit indécomposable et plus particulièrement son comportement asymptotique lorsque $n$ tend vers l’infini et que $m=n$ est fixé. Cette valeur décroît régulièrement de $1$ à $0$ lorsque $m=n$ croît, et il n’y a pas de phénomène de seuil. Lorsque $n=2m$, une faible majorité ($51.1 \ldots$ pour cent) des permutations sont indécomposables. Nous considérons aussi les involutions sans point fixe indécomposables qui sont en bijection avec les cartes de genre quelconque plongées dans une surface orientable, pour ces involutions ayant $m$ maxima partiels (ou records) nous obtenons une borne inférieure pour leur probabilité d’êtres indécomposables.
Enumerating (2+2)-free posets by the number of minimal elements and other statistics
Authors: Kitaev Sergey , Remmel Jeffrey 
Published: August 2021

A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: $P(t)=∑_n≥ 0 ∏_i=1^n ( 1-(1-t)^i)$. We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form $P(t,z)=∑_n,k ≥0 p_n,k t^n z^k = 1+ ∑_n ≥0\frac{zt}{(1-zt)^n+1}∏_i=1^n (1-(1-t)^i)$ where $p_n,k$ equals the number of (2+2)-free posets of size $n$ with $k$ minimal elements.
Un poset sera dit (2+2)-libre s'il ne contient aucun sous-poset isomorphe à 2+2, l'union disjointe de deux chaînes à deux éléments. Dans un article récent, Bousquet-Mélou et al. ont trouvé, à l'aide de "suites de montées'', la fonction génératrice des nombres de posets (2+2)-libres: c'est $P(t)=∑_n≥ 0 ∏_i=1^n ( 1-(1-t)^i)$. Nous étendons ce résultat en trouvant la fonction génératrice des posets (\textrm2+2)-libres rendant compte de quatre statistiques, dont le nombre d'éléments minimaux du poset. Nous montrons aussi que lorsqu'on ne s'intéresse qu'au nombre d'éléments minimaux, notre fonction génératrice assez compliquée peut être simplifiée en$P(t,z)=∑_n,k ≥0 p_n,k t^n z^k = 1+ ∑_n ≥0\frac{zt}{(1-zt)^n+1}∏_i=1^n (1-(1-t)^i)$, où $p_n,k$ est le nombre de posets (2+2)-libres de taille $n$ avec $k$ éléments minimaux.
Linear coefficients of Kerov's polynomials: bijective proof and refinement of Zagier's result
Authors: Féray Valentin , Vassilieva Ekaterina A. 
Published: August 2021

We look at the number of permutations $\beta$ of $[N]$ with $m$ cycles such that $(1 2 \ldots N) \beta^{-1}$ is a long cycle. These numbers appear as coefficients of linear monomials in Kerov's and Stanley's character polynomials. D. Zagier, using algebraic methods, found an unexpected connection with Stirling numbers of size $N+1$. We present the first combinatorial proof of his result, introducing a new bijection between partitioned maps and thorn trees. Moreover, we obtain a finer result, which takes the type of the permutations into account.
Nous étudions le nombre de permutations $\beta$ de $[N]$ avec $m$ cycles telles que $(1 2 \ldots N) \beta^{-1}$ a un seul cycle. Ces nombres apparaissent en tant que coefficients des monômes linéaires des polynômes de Kerov et de Stanley. À l'aide de méthodes algébriques, D. Zagier a trouvé une connexion inattendue avec les nombres de Stirling de taille $N+1$. Nous présentons ici la première preuve combinatoire de son résultat, en introduisant une nouvelle bijection entre des cartes partitionnées et des arbres épineux. De plus, nous obtenons un résultat plus fin, prenant en compte le type des permutations.
Extended Abstract for Enumerating Pattern Avoidance for Affine Permutations
Authors: Crites Andrew 
Published: August 2021

In this paper we study pattern avoidance for affine permutations. In particular, we show that for a given pattern $p$, there are only finitely many affine permutations in $\widetilde{S}_n$ that avoid $p$ if and only if $p$ avoids the pattern $321$. We then count the number of affine permutations that avoid a given pattern $p$ for each $p$ in $S_3$, as well as give some conjectures for the patterns in $S_4$. This paper is just an outline; the full version will appear elsewhere.
Dans cet œuvre, on étudie comment les permutations affines évitent les motifs. Spécifiquement, on peut dire que pour le motif $p$, il existe un nombre limité de permutations affines dans $\widetilde{S}_n$ qui évite $p$ si et seulement si $p$ évite le motif $321$. Après, on compte le nombre de permutations affines qui évitent le motif $p$ pour chaque $p$ de $S_3$. Puis, on donne des conjectures pour les motifs de $S_4$. Ceci n'est qu'un aperçu; la version complète apparaîtra ailleurs.
The Hodge Structure of the Coloring Complex of a Hypergraph (Extended Abstract)
Authors: Rundell Sarah C , Long Jane H 
Published: August 2021

Let $G$ be a simple graph with $n$ vertices. The coloring complex$ Δ (G)$ was defined by Steingrímsson, and the homology of $Δ (G)$ was shown to be nonzero only in dimension $n-3$ by Jonsson. Hanlon recently showed that the Eulerian idempotents provide a decomposition of the homology group $H_{n-3}(Δ (G))$ where the dimension of the $j^th$ component in the decomposition, $H_{n-3}^{(j)}(Δ (G))$, equals the absolute value of the coefficient of $λ ^j$ in the chromatic polynomial of $G, _{\mathcal{χg}}(λ )$. Let $H$ be a hypergraph with $n$ vertices. In this paper, we define the coloring complex of a hypergraph, $Δ (H)$, and show that the coefficient of $λ ^j$ in $χ _H(λ )$ gives the Euler Characteristic of the $j^{th}$ Hodge subcomplex of the Hodge decomposition of $Δ (H)$. We also examine conditions on a hypergraph, $H$, for which its Hodge subcomplexes are Cohen-Macaulay, and thus where the absolute value of the coefficient of $λ ^j$ in $χ _H(λ )$ equals the dimension of the $j^{th}$ Hodge piece of the Hodge decomposition of $Δ (H)$.
Soit $G$ un graphe simple à n sommets. Le complexe de coloriage $Δ (G)$ a été défini par Steingrímsson et Jonsson a prouvé que l'homologie de $Δ (G)$ est non nulle seulement en dimension $n-3$. Hanlon a récemment prouvé que les idempotents eulériens fournissent une décomposition du groupe d'homologie $H_{n-3}(Δ (G))$ où la dimension de la $j^e$ composante dans la décomposition de $H_{n-3}^{(j)}(Δ (G))$ est égale à la valeur absolue du coefficient de $λ ^j$ dans le polynôme chromatique de $G, _{\mathcal{χg}}(λ )$ . Soit H un hypergraphe à $n$ sommets. Dans ce texte, nous définissons le complexe de coloration d'un hypergraphe $Δ (H)$ et nous prouvons que le coefficient de $λ ^j$ dans $χ _H(λ )$ donne la caractéristique d'Euler du $j^e$ sous-complexe de Hodge dans la décomposition de Hodge de Δ (H). Nous examinons également des conditions sur un hypergraphe H pour lesquelles les sous-complexes de Hodge sont Cohen-Macaulay. Ainsi la valeur absolue du coefficient de $λ ^j$ in $χ _H(λ )$ est égale à la dimension du $j^e$sous-complexe de Hodge dans la décomposition de Hodge de $Δ (H)$.