bluuebunny/crossref_metadata_2025 huggingface dataset:
polymake and Lattice Polytopes
Authors: Joswig Michael , Müller Benjamin , Paffenholz Andreas
Published: August 2021

The $\mathtt{polymake}$ software system deals with convex polytopes and related objects from geometric combinatorics. This note reports on a new implementation of a subclass for lattice polytopes. The features displayed are enabled by recent changes to the $\mathtt{polymake}$ core, which will be discussed briefly.
Combinatorics of Positroids
Authors: Oh Suho
Published: August 2021

Recently Postnikov gave a combinatorial description of the cells in a totally-nonnegative Grassmannian. These cells correspond to a special class of matroids called positroids. There are many interesting combinatorial objects associated to a positroid. We introduce some recent results, including the generalization and proof of the purity conjecture by Leclerc and Zelevinsky on weakly separated sets.
Combinatorial formulas for ⅃-coordinates in a totally nonnegative Grassmannian, extended abstract, extended abstract
Authors: Talaska Kelli
Published: August 2021

Postnikov constructed a decomposition of a totally nonnegative Grassmannian $(Gr _{kn})_≥0$ into positroid cells. We provide combinatorial formulas that allow one to decide which cell a given point in $(Gr _{kn})_≥0$ belongs to and to determine affine coordinates of the point within this cell. This simplifies Postnikov's description of the inverse boundary measurement map and generalizes formulas for the top cell given by Speyer and Williams. In addition, we identify a particular subset of Plücker coordinates as a totally positive base for the set of non-vanishing Plücker coordinates for a given positroid cell.
Blocks in Constrained Random Graphs with Fixed Average Degree
Authors: Panagiotou Konstantinos
Published: August 2021

This work is devoted to the study of typical properties of random graphs from classes with structural constraints, like for example planar graphs, with the additional restriction that the average degree is fixed. More precisely, within a general analytic framework, we provide sharp concentration results for the number of blocks (maximal biconnected subgraphs) in a random graph from the class in question. Among other results, we discover that essentially such a random graph belongs with high probability to only one of two possible types: it either has blocks of at most logarithmic size, or there is a \emphgiant block that contains linearly many vertices, and all other blocks are significantly smaller. This extends and generalizes the results in the previous work [K. Panagiotou and A. Steger. Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 432-440, 2009], where similar statements were shown without the restriction on the average degree.
Application of graph combinatorics to rational identities of type $A^\ast$
Authors: Boussicault Adrien , Féray Valentin
Published: August 2021

To a word $w$, we associate the rational function $\Psi_w = \prod (x_{w_i} - x_{w_{i+1}})^{-1}$. The main object, introduced by C. Greene to generalize identities linked to Murnaghan-Nakayama rule, is a sum of its images by certain permutations of the variables. The sets of permutations that we consider are the linear extensions of oriented graphs. We explain how to compute this rational function, using the combinatorics of the graph $G$. We also establish a link between an algebraic property of the rational function (the factorization of the numerator) and a combinatorial property of the graph (the existence of a disconnecting chain).

À un mot $w$, nous associons la fonction rationnelle $\Psi_w = \prod (x_{w_i} - x_{w_{i+1}})^{-1}$. L'objet principal, introduit par C. Greene pour généraliser des identités rationnelles liées à la règle de Murnaghan-Nakayama, est une somme de ses images par certaines permutations des variables. Les ensembles de permutations considérés sont les extensions linéaires des graphes orientés. Nous expliquons comment calculer cette fonction rationnelle à partir de la combinatoire du graphe $G$. Nous établissons ensuite un lien entre une propriété algébrique de la fonction rationnelle (la factorisation du numérateur) et une propriété combinatoire du graphe (l'existence d'une chaîne le déconnectant).
Automatic Classification of Restricted Lattice Walks
Authors: Bostan Alin , Kauers Manuel
Published: August 2021

We propose an $\textit{experimental mathematics approach}$ leading to the computer-driven $\textit{discovery}$ of various conjectures about structural properties of generating functions coming from enumeration of restricted lattice walks in 2D and in 3D.
Brauer-Schur functions
Authors: Aokage Kazuya
Published: August 2021

A new class of functions is studied. We define the Brauer-Schur functions $B^{(p)}_{\lambda}$ for a prime number $p$, and investigate their properties. We construct a basis for the space of symmetric functions, which consists of products of $p$-Brauer-Schur functions and Schur functions. We will see that the transition matrix from the natural Schur function basis has some interesting numerical properties.
Bijections between noncrossing and nonnesting partitions for classical reflection groups
Authors: Fink Alex , Giraldo Benjamin Iriarte
Published: August 2021

We present $\textit{type preserving}$ bijections between noncrossing and nonnesting partitions for all classical reflection groups, answering a question of Athanasiadis and Reiner. The bijections for the abstract Coxeter types $B$, $C$ and $D$ are new in the literature. To find them we define, for every type, sets of statistics that are in bijection with noncrossing and nonnesting partitions, and this correspondence is established by means of elementary methods in all cases. The statistics can be then seen to be counted by the generalized Catalan numbers Cat$(W)$ when $W$ is a classical reflection group. In particular, the statistics of type $A$ appear as a new explicit example of objects that are counted by the classical Catalan numbers.
Enumeration of derangements with descents in prescribed positions
Authors: Eriksen Niklas , Freij Ragnar , Wästlund Johan
Published: August 2021

We enumerate derangements with descents in prescribed positions. A generating function was given by Guo-Niu Han and Guoce Xin in 2007. We give a combinatorial proof of this result, and derive several explicit formulas. To this end, we consider fixed point $\lambda$-coloured permutations, which are easily enumerated. Several formulae regarding these numbers are given, as well as a generalisation of Euler's difference tables. We also prove that except in a trivial special case, if a permutation $\pi$ is chosen uniformly among all permutations on $n$ elements, the events that $\pi$ has descents in a set $S$ of positions, and that $\pi$ is a derangement, are positively correlated.
$k$-distant crossings and nestings of matchings and partitions
Authors: Drake Dan , Kim Jang Soo
Published: August 2021

We define and consider $k$-distant crossings and nestings for matchings and set partitions, which are a variation of crossings and nestings in which the distance between vertices is important. By modifying an involution of Kasraoui and Zeng (Electronic J. Combinatorics 2006, research paper 33), we show that the joint distribution of $k$-distant crossings and nestings is symmetric. We also study the numbers of $k$-distant noncrossing matchings and partitions for small $k$, which are counted by well-known sequences, as well as the orthogonal polynomials related to $k$-distant noncrossing matchings and partitions. We extend Chen et al.'s $r$-crossings and enhanced $r$-crossings.

Nous définissons les notions de croisements et imbrications $k$-distants sur les appariements et les partitions d'ensemble, qui sont une variation sur les notions usuelles prenant en compte la distance entre les sommets. En modifiant une involution de Kasraoui et Zeng (Electronic J. Combinatorics 2006, research paper 33), nous montrons que la distribution jointe des croisements et imbrications $k$-distants est symétrique. Nous étudions le nombre d'involutions et de partitions sans croisement $k$-distant pour de petites valeurs de $k$, qui sont des suites d'entiers bien connues, ainsi que les polynômes orthogonaux qui leur sont reliés. Nous étendons les notions de $r$-croisements et $r$-croisements améliorés dues à Chen et al.
Combinatorial invariant theory of projective reflection groups
Authors: Caselli Fabrizio
Published: August 2021

We introduce the class of projective reflection groups which includes all complex reflection groups. We show that several aspects involving the combinatorics and the representation theory of complex reflection groups find a natural description in this wider setting.

On introduit la classe des groupes de réflexions projectifs, ce qui généralise la notion de groupe engendré par des réflexions. On montre que plusieurs aspects concernant la combinatoire et la théorie des représentations des groupes de réflexions complexes trouvent une description naturelle dans ce cadre plus général.
An Edge-Signed Generalization of Chordal Graphs, Free Multiplicities on Braid Arrangements, and Their Characterizations
Authors: Abe Takuro , Nuida Koji , Numata Yasuhide
Published: August 2021

In this article, we propose a generalization of the notion of chordal graphs to signed graphs, which is based on the existence of a perfect elimination ordering for a chordal graph. We give a special kind of filtrations of the generalized chordal graphs, and show a characterization of those graphs. Moreover, we also describe a relation between signed graphs and a certain class of multiarrangements of hyperplanes, and show a characterization of free multiarrangements in that class in terms of the generalized chordal graphs, which generalizes a well-known result by Stanley on free hyperplane arrangements. Finally, we give a remark on a relation of our results with a recent conjecture by Athanasiadis on freeness characterization for another class of hyperplane arrangements.

Dans cet article, nous proposons une généralisation de la notion des graphes triangulés à graphes signés, qui est basée sur l'existence d'un ordre d'élimination simplicial à un graphe triangulé. Nous donnons un genre spécial de filtrations des graphes triangulés généralisés, et montrons une caractérisation de ces graphes. De plus, nous décrivons aussi une relation entre graphes signés et une certaine classe de multicompositions d'hyperplans, et montrons une caractérisation de multicompositions libres dans cette classe en termes des graphes triangulés généralisés, qui généralise un résultat célèbre de Stanley sur compositions libres d'hyperplans. Finalement, nous donnons une remarque sur une relation de nos résultats avec une conjecture récente d'Athanasiadis sur une caractérisation du freeness d'une autre classe de compositions d'hyperplans.
Faster Methods for Identifying Nontrivial Energy Conservation Functions for Cellular Automata
Authors: Baird Leemon , Fagin Barry
Published: August 2021

The biggest obstacle to the efficient discovery of conserved energy functions for cellular auotmata is the elimination of the trivial functions from the solution space. Once this is accomplished, the identification of nontrivial conserved functions can be accomplished computationally through appropriate linear algebra. As a means to this end, we introduce a general theory of trivial conserved functions. We consider the existence of nontrivial additive conserved energy functions ("nontrivials") for cellular automata in any number of dimensions, with any size of neighborhood, and with any number of cell states. We give the first known basis set for all trivial conserved functions in the general case, and use this to derive a number of optimizations for reducing time and memory for the discovery of nontrivials. We report that the Game of Life has no nontrivials with energy windows of size 13 or smaller. Other $2D$ automata, however, do have nontrivials. We give the complete list of those functions for binary outer-totalistic automata with energy windows of size 9 or smaller, and discuss patterns we have observed.
Geometric Bucket Trees: Analysis of Linear Bucket Tree
Authors: Jacquet Philippe , Muhlethaler Paul
Published: August 2021

We analyse the average number of buckets in a Linear Bucket tree created by $n$ points uniformly dispatched on an interval of length $y$. A new bucket is created when a point does not fall in an existing bucket. The bucket is the interval of length 2 centered on the point. We illustrate this concept by an interesting tale of how the moon's surface took on its present form. Thanks to an explicit Laplace transform of the Poissonized sequence, and the use of dePoissonization tools, we obtain the explicit asymptotic expansions of the average number of buckets in most of the asymptotic regimes relative to $n$ and $y$.
The maximum of Brownian motion with parabolic drift (Extended abstract)
Authors: Janson Svante , Louchard Guy , Martin-Löf Anders
Published: August 2021

We study the maximum of a Brownian motion with a parabolic drift; this is a random variable that often occurs as a limit of the maximum of discrete processes whose expectations have a maximum at an interior point. This has some applications in algorithmic and data structures analysis. We give series expansions and integral formulas for the distribution and the first two moments, together with numerical values to high precision.
Counting Markov Types
Authors: Jacquet Philippe , Knessl Charles , Szpankowski Wojciech
Published: August 2021

The method of types is one of the most popular techniques in information theory and combinatorics. Two sequences of equal length have the same type if they have identical empirical distributions. In this paper, we focus on Markov types, that is, sequences generated by a Markov source (of order one). We note that sequences having the same Markov type share the same so called $\textit{balanced frequency matrix}$ that counts the number of distinct pairs of symbols. We enumerate the number of Markov types for sequences of length $n$ over an alphabet of size $m$. This turns out to coincide with the number of the balanced frequency matrices as well as with the number of special $\textit{linear diophantine equations}$, and also balanced directed multigraphs. For fixed $m$ we prove that the number of Markov types is asymptotically equal to $d(m) \frac{n^{m^{2-m}}}{(m^2-m)!}$, where $d(m)$ is a constant for which we give an integral representation. For $m \to \infty$ we conclude that asymptotically the number of types is equivalent to $\frac{\sqrt{2}m^{3m/2} e^{m^2}}{m^{2m^2} 2^m \pi^{m/2}} n^{m^2-m}$ provided that $m=o(n^{1/4})$ (however, our techniques work for $m=o(\sqrt{n})$). These findings are derived by analytical techniques ranging from multidimensional generating functions to the saddle point method.
Analysis of Transmissions Scheduling with Packet Fragmentation
Authors: Namman Nir , Rom Raphaël
Published: August 2021

We investigate a scheduling problem in which packets, or datagrams, may be fragmented. While there are a few applications to scheduling with datagram fragmentation, our model of the problem is derived from a scheduling problem present in data over CATV networks. In the scheduling problem datagrams of variable lengths must be assigned (packed) into fixed length time slots. One of the capabilities of the system is the ability to break a datagram into several fragments. When a datagram is fragmented, extra bits are added to the original datagram to enable the reassembly of all the fragments. We convert the scheduling problem into the problem of bin packing with item fragmentation, which we define in the following way: we are asked to pack a list of items into a minimum number of unit capacity bins. Each item may be fragmented in which case overhead units are added to the size of every fragment. The cost associated with fragmentation renders the problem NP-hard, therefore an approximation algorithm is needed. We define a version of the well-known Next-Fit algorithm, capable of fragmenting items, and investigate its performance. We present both worst case and average case results and compare them to the case where fragmentation is not allowed.
A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems
Authors: Loi Cedric , Cournède Paul-Henry , Françon Jean
Published: August 2021

The analysis of pattern occurrences has numerous applications, in particular in biology. In this article, a symbolic method is proposed to compute the distribution associated to the number of occurences of a specific pattern in a random text generated by a stochastic 0L-system. To that purpose, a semiring structure is set for combinatorial classes composed of weighted words. This algebraic structure relies on new union and concatenation operators which, under some assumptions, are admissible constructions. Decomposing the combinatorial classes of interest by using these binary operators enables the direct translation of specifications into a set of functional equations relating generating functions thanks to transformation rules. The article ends with two examples. The first one deals with unary patterns and the connection with multitype branching process is established. The second one is about a pattern composed of two letters and underlines the importance of writing a proper specification.
Minimum Eccentricity Multicast Trees
Authors: Krumme David , Fragopoulou Paraskevi
Published: August 2021

We consider the problem of constructing a multicast tree that connects a group of source nodes to a group of sink nodes (receivers) and minimizes the maximum end-to-end delay between any pair of source/sink nodes. This is known as the \emphminimum eccentricity multicast tree problem, and is directly related to the quality of service requirements of real multipoint applications. We deal directly with the problem in its general form, meaning that the sets of source and sink nodes need not be overlapping nor disjoint. The main contribution of this work is a polynomial algorithm for this problem on general networks which is inspired by an innovative method that uses geometric relationships on the xy-plane.
Partial Quicksort and Quickpartitionsort
Authors: Martínez Conrado , Rösler Uwe
Published: August 2021

Partial Quicksort sorts the $l$ smallest elements in a list of length $n$. We provide a complete running time analysis for this combination of Find and Quicksort. Further we give some optimal adapted versions, called Partition Quicksort, with an asymptotic running time $c_1l\ln l+c_2l+n+o(n)$. The constant $c_1$ can be as small as the information theoretic lower bound $\log_2 e$.
Occupancy distributions in Markov chains via Doeblin's ergodicity coefficient
Authors: Chestnut Stephen , Lladser Manuel E.
Published: August 2021

We state and prove new properties about Doeblin's ergodicity coefficient for finite Markov chains. We show that this coefficient satisfies a sub-multiplicative type inequality (analogous to the Markov-Dobrushin's ergodicity coefficient), and provide a novel but elementary proof of Doeblin's characterization of weak-ergodicity for non-homogeneous chains. Using Doeblin's coefficient, we illustrate how to approximate a homogeneous but possibly non-stationary Markov chain of duration $n$ by independent and short-lived realizations of an auxiliary chain of duration of order $\ln (n)$. This leads to approximations of occupancy distributions in homogeneous chains, which may be particularly useful when exact calculations via one-step methods or transfer matrices are impractical, and when asymptotic approximations may not be yet reliable. Our findings may find applications to pattern problems in Markovian and non-Markovian sequences that are treatable via embedding techniques.
Stochastic Analysis of the $k$-Server Problem on the Circle
Authors: Anagnostopoulos Aris , Dombry Clément , Guillotin-Plantard Nadine , Kontoyiannis Ioannis , Upfal Eli
Published: August 2021

We consider a stochastic version of the $k$-server problem in which $k$ servers move on a circle to satisfy stochastically generated requests. The requests are independent and identically distributed according to an arbitrary distribution on a circle, which is either discrete or continuous. The cost of serving a request is the distance that a server needs to move to reach the request. The goal is to minimize the steady-state expected cost induced by the requests. We study the performance of a greedy strategy, focusing, in particular, on its convergence properties and the interplay between the discrete and continuous versions of the process.
Asymptotics for Walks in a Weyl chamber of Type $B$ (extended abstract)
Authors: Feierl Thomas
Published: August 2021

We consider lattice walks in $\mathbb{R}^k$ confined to the region $0 < x_1 < x_2 \ldots < x_k$ with fixed (but arbitrary) starting and end points. The walks are required to be "reflectable", that is, we assume that the number of paths can be counted using the reflection principle. The main result is an asymptotic formula for the total number of walks of length $n$ with fixed but arbitrary starting and end point for a general class of walks as the number $n$ of steps tends to infinity. As applications, we find the asymptotics for the number of $k$-non-crossing tangled diagrams on the set $\{1,2, \ldots,n\}$ as $n$ tends to infinity, and asymptotics for the number of $k$-vicious walkers subject to a wall restriction in the random turns model as well as in the lock step model. Asymptotics for all of these objects were either known only for certain special cases, or have only been partially determined.
Stochastic Flips on Dimer Tilings
Authors: Fernique Thomas , Regnault Damien
Published: August 2021

This paper introduces a Markov process inspired by the problem of quasicrystal growth. It acts over dimer tilings of the triangular grid by randomly performing local transformations, called $\textit{flips}$, which do not increase the number of identical adjacent tiles (this number can be thought as the tiling energy). Fixed-points of such a process play the role of quasicrystals. We are here interested in the worst-case expected number of flips to converge towards a fixed-point. Numerical experiments suggest a $\Theta (n^2)$ bound, where $n$ is the number of tiles of the tiling. We prove a $O(n^{2.5})$ upper bound and discuss the gap between this bound and the previous one. We also briefly discuss the average-case.
The Möbius function of separable permutations (extended abstract)
Authors: Jelínek Vít , Jelínková Eva , Steingrímsson Einar
Published: August 2021

A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. Using the notion of separating tree, we give a computationally efficient formula for the Möbius function of an interval $(q,p)$ in the poset of separable permutations ordered by pattern containment. A consequence of the formula is that the Möbius function of such an interval $(q,p)$ is bounded by the number of occurrences of $q$ as a pattern in $p$. The formula also implies that for any separable permutation $p$ the Möbius function of $(1,p)$ is either 0, 1 or -1.

Une permutation est séparable si elle peut être générée á partir de la permutation 1 par des sommes directes et des sommes indirectes, ou de façon équivalente, si elle évite les motifs 2413 et 3142. En utilisant le concept de l'arbre séparant, nous donnons une formule pour le calcul efficace de la fonction de Möbius d'un intervalle de $(q, p)$ dans l'ensemble partiellement ordonné des permutations séparables. Une conséquence est que la fonction de Möbius de $(q,p)$ pour $q$ et $p$ séparables est bornée par le nombre d'occurrences de $q$ comme un motif en $p$. Nous montrons aussi que pour une permutation $p$ séparable, la fonction de Möbius de $(1,p)$ est soit 0, 1 ou -1.
Constant term evaluation for summation of C-finite sequences
Authors: Hou Qing-Hu , Xin Guoce
Published: August 2021

Based on constant term evaluation, we present a new method to compute a closed form of the summation $∑_k=0^n-1 ∏_j=1^r F_j(a_jn+b_jk+c_j)$, where ${F_j(k)} are $C$-finite sequences and $a_j$ and $a_j+b_j$ are nonnegative integers. Our algorithm is much faster than that of Greene and Wilf.

En s'appuyant sur l'évaluation de termes constants, nous présentons une nouvelle méthode pour calculer une forme close de la somme $∑_k=0^n-1 ∏_j=1^r F_j(a_jn+b_jk+c_j)$, où les ${F_j(k)}$ sont des suites C-finies, et où les $a_j$ et les $a_j+b_j$ sont des entiers positifs ou nuls. Notre algorithme est beaucoup plus rapide que celui de Greene et Wilf.
Affine structures and a tableau model for $E_6$ crystals
Authors: Jones Brant , Schilling Anne
Published: August 2021

We provide the unique affine crystal structure for type $E_6^{(1)}$ Kirillov―Reshetikhin crystals corresponding to the multiples of fundamental weights $s\Lambda _1, s\Lambda _2$, and $s\Lambda _6$ for all $s≥ 1$ (in Bourbaki's labeling of the Dynkin nodes, where 2 is the adjoint node). Our methods introduce a generalized tableaux model for classical highest weight crystals of type $E$ and use the order three automorphism of the affine $E_6^{(1)}$ Dynkin diagram. In addition, we provide a conjecture for the affine crystal structure of type $E_7^{(1)}$ Kirillov―Reshetikhin crystals corresponding to the adjoint node.

Nous donnons l'unique structure cristalline affine pour les cristaux de Kirillov―Reshetikhin de type $E_6^{(1)}$ correspondant aux multiples des poids fondamentaux $s\Lambda _1, s\Lambda _2$ et $s\Lambda _6 $pour tout $s≥ 1$ (dans l'étiquetage de Bourbaki des noeuds de Dynkin, où 2 est le noeud adjoint). Pour ceci, nous introduisons un modèle de tableaux généralisés pour les cristaux classiques du plus haut poids de type $E$ et nous employons l'automorphisme d'ordre trois du diagramme de Dynkin du type $E_6^{(1)}$. En outre, nous fournissons une conjecture pour la structure affine pour les cristaux de Kirillov―Reshetikhin de type $E_7^{(1)}$ correspondant au noeud adjoint.
Bruhat order, rationally smooth Schubert varieties, and hyperplane arrangements
Authors: Oh Suho , Yoo Hwanchul
Published: August 2021

We link Schubert varieties in the generalized flag manifolds with hyperplane arrangements. For an element of a Weyl group, we construct a certain graphical hyperplane arrangement. We show that the generating function for regions of this arrangement coincides with the Poincaré polynomial of the corresponding Schubert variety if and only if the Schubert variety is rationally smooth.

Nous relions des variétés de Schubert dans le variété flag généralisée avec des arrangements des hyperplans. Pour un élément dún groupe de Weyl, nous construisons un certain arrangement graphique des hyperplans. Nous montrons que la fonction génératrice pour les régions de cet arrangement coincide avec le polynome de Poincaré de la variété de Schubert correspondante si et seulement si la variété de Schubert est rationnellement lisse.
Toric Ideals of Flow Polytopes
Authors: Lenz Matthias
Published: August 2021

We show that toric ideals of flow polytopes are generated in degree $3$. This was conjectured by Diaconis and Eriksson for the special case of the Birkhoff polytope. Our proof uses a hyperplane subdivision method developed by Haase and Paffenholz. It is known that reduced revlex Gröbner bases of the toric ideal of the Birkhoff polytope $B_n$ have at most degree $n$. We show that this bound is sharp for some revlex term orders. For $(m \times n)$-transportation polytopes, a similar result holds: they have Gröbner bases of at most degree $\lfloor mn/2 \rfloor$. We construct a family of examples, where this bound is sharp.

Nous démontrons que les idéaux toriques des polytopes de flot sont engendrés par un ensemble de degré $3$. Cela a été conjecturé par Diaconis et Eriksson pour le cas particulier du polytope de Birkhoff. Notre preuve utilise une méthode de subdivision par hyperplans, développée par Haase et Paffenholz. Il est bien connu que les bases de Gröbner revlex réduite du polytope de Birkhoff $B_n$ sont au plus de degré $n$. Nous démontrons que cette borne est optimale pour quelques ordres revlex. Pour les polytopes de transportation de dimension $(m \times n)$, il existe un résultat similaire : leurs bases de Gröbner sont au plus de degré $\lfloor mn/2 \rfloor$. Nous construisons une famille d'exemples pour lesquels cette borne est atteinte.
On $\gamma$-vectors satisfying the Kruskal-Katona inequalities
Authors: Nevo E. , Petersen T. K.
Published: August 2021

We present examples of flag homology spheres whose $\gamma$-vectors satisfy the Kruskal-Katona inequalities. This includes several families of well-studied simplicial complexes, including Coxeter complexes and the simplicial complexes dual to the associahedron and to the cyclohedron. In these cases, we construct explicit flag simplicial complexes whose $f$-vectors are the $\gamma$-vectors in question, and so a result of Frohmader shows that the $\gamma$-vectors satisfy not only the Kruskal-Katona inequalities but also the stronger Frankl-Füredi-Kalai inequalities. In another direction, we show that if a flag $(d-1)$-sphere has at most $2d+3$ vertices its $\gamma$-vector satisfies the Frankl-Füredi-Kalai inequalities. We conjecture that if $\Delta$ is a flag homology sphere then $\gamma (\Delta)$ satisfies the Kruskal-Katona, and further, the Frankl-Füredi-Kalai inequalities. This conjecture is a significant refinement of Gal's conjecture, which asserts that such $\gamma$-vectors are nonnegative.

Nous présentons des exemples de sphères d'homologie flag dont $\gamma$-vecteurs satisfaire les inégalités de Kruskal-Katona. Cela comprend plusieurs familles de bien étudiés simplicial complexes, y compris les complexes de Coxeter et les complexes simpliciaux dual de l'associahedron et à la cyclohedron. Dans ces cas, nous construisons explicite flag simplicial complexes dont les $f$-vecteurs sont les $\gamma$-vecteurs en question, et ainsi de suite de Frohmader montre que le $\gamma$-vecteurs de satisfaire non seulement les inégalités de Kruskal-Katona mais aussi les plus fortes inégalités Frankl-Füredi-Kalai. Dans une autre direction, nous montrons que, si un flag $(d-1)$-sphère a au plus $2d+3$ sommets son $\gamma$-vecteur satisfait aux inégalités de Frankl-Füredi-Kalai. Nous conjecture que, si $\Delta$ est une sphère d'homologie flag alors $\gamma(\Delta)$ satisfait aux inégalités de Kruskal-Katona, en outre, celles de Frankl-Füredi-Kalai. Cette conjecture est un raffinement significatif de la conjecture de Gal, qui affirme que ces $\gamma$-vecteurs sont nonnégatifs.
An algorithm which generates linear extensions for a generalized Young diagram with uniform probability
Authors: Nakada Kento , Okamura Shuji
Published: August 2021

The purpose of this paper is to present an algorithm which generates linear extensions for a generalized Young diagram, in the sense of D. Peterson and R. A. Proctor, with uniform probability. This gives a proof of a D. Peterson's hook formula for the number of reduced decompositions of a given minuscule elements. \par

Le but de ce papier est présenter un algorithme qui produit des extensions linéaires pour un Young diagramme généralisé dans le sens de D. Peterson et R. A. Proctor, avec probabilité constante. Cela donne une preuve de la hook formule d'un D. Peterson pour le nombre de décompositions réduites d'un éléments minuscules donné.
Linear Systems on Tropical Curves
Authors: Haase Christian , Musiker Gregg , Yu Josephine
Published: August 2021

A tropical curve $\Gamma$ is a metric graph with possibly unbounded edges, and tropical rational functions are continuous piecewise linear functions with integer slopes. We define the complete linear system $|D|$ of a divisor $D$ on a tropical curve $\Gamma$ analogously to the classical counterpart. We investigate the structure of $|D|$ as a cell complex and show that linear systems are quotients of tropical modules, finitely generated by vertices of the cell complex. Using a finite set of generators, $|D|$ defines a map from $\Gamma$ to a tropical projective space, and the image can be modified to a tropical curve of degree equal to $\mathrm{deg}(D)$. The tropical convex hull of the image realizes the linear system $|D|$ as a polyhedral complex.

Une courbe tropicale $\Gamma$ est un graphe métrique pouvant contenir des arêtes infinies, et une fonction rationnelle tropicale est une fonction continue linéaire par morceaux à pentes entières. Le système linéaire complet $|D|$ d'un diviseur $D$ sur une courbe tropicale $\Gamma$ est défini de façon analogue au cas classique. Nous étudions la structure de $|D|$ en tant que complexe cellulaire et montrons que les systèmes linéaires sont des quotients de modules tropicaux engendrés par un nombre fini de sommets du complexe. Etant donné un ensemble fini de générateurs, $|D|$ définit une application de $\Gamma$ vers un espace projectif tropical, dont l'image peut être modifiée en une courbe tropicale de degré égal à $\mathrm{deg}(D)$. L'enveloppe convexe tropicale de l'image réalise le système linéaire $|D|$ en tant que complexe polyédral.
A bijection between (bounded) dominant Shi regions and core partitions
Authors: Fishel Susanna , Vazirani Monica
Published: August 2021

It is well-known that Catalan numbers $C_n = \frac{1}{ n+1} \binom{2n}{n}$ count the number of dominant regions in the Shi arrangement of type $A$, and that they also count partitions which are both n-cores as well as $(n+1)$-cores. These concepts have natural extensions, which we call here the $m$-Catalan numbers and $m$-Shi arrangement. In this paper, we construct a bijection between dominant regions of the $m$-Shi arrangement and partitions which are both $n$-cores as well as $(mn+1)$-cores. We also modify our construction to produce a bijection between bounded dominant regions of the $m$-Shi arrangement and partitions which are both $n$-cores as well as $(mn-1)$-cores. The bijections are natural in the sense that they commute with the action of the affine symmetric group.

Il est bien connu que les nombres de Catalan $C_n = \frac{1}{ n+1} \binom{2n}{n}$ comptent non seulement le nombre de régions dominantes dans le Shi arrangement de type $A$ mais aussi les partitions qui sont à la fois $n$-cœur et $(n+1)$-cœur. Ces concepts ont des extensions naturelles, que nous appelons ici les nombres $m$-Catalan et le $m$-Shi arrangement. Dans cet article, nous construisons une bijection entre régions dominantes du $m$-Shi arrangement et les partitions qui sont à la fois $n$-cœur et $(nm+1)$-coeur. Nous modifions également notre construction pour produire une bijection entre régions dominantes bornées du $m$-Shi arrangement et les partitions qui sont à la fois $n$-coeur et $(mn-1)$-cœur. Ces bijections sont naturelles dans le sens où elles commutent avec l'action du groupe affine symétrique.
Descent polynomials for permutations with bounded drop size
Authors: Chung Fan , Claesson Anders , Dukes Mark , Graham Ronald
Published: August 2021

Motivated by juggling sequences and bubble sort, we examine permutations on the set${1, 2, \ldots, n}$ with $d$ descents and maximum drop size $k$. We give explicit formulas for enumerating such permutations for given integers $k$ and $d$. We also derive the related generating functions and prove unimodality and symmetry of the coefficients.

Motivés par les "suites de jonglerie'' et le tri à bulles, nous étudions les permutations de l'ensemble ${1, 2, \ldots, n}$ ayant $d$ descentes et une taille de déficience maximale $k$. Nous donnons des formules explicites pour l'énumération de telles permutations pour des entiers k et d fixés, ainsi que les fonctions génératrices connexes. Nous montrons aussi que les coefficients possèdent des propriétés d'unimodalité et de symétrie.
Paths of specified length in random k-partite graphs
Authors: Subramanian C.R.
Published: August 2021

Fix positive integers k and l. Consider a random k-partite graph on n vertices obtained by partitioning the vertex set into V_i, (i=1, \ldots,k) each having size Ω (n) and choosing each possible edge with probability p. Consider any vertex x in any V_i and any vertex y. We show that the expected number of simple paths of even length l between x and y differ significantly depending on whether y belongs to the same V_i (as x does) or not. A similar phenomenon occurs when l is odd. This result holds even when k,l vary slowly with n. This fact has implications to coloring random graphs. The proof is based on establishing bijections between sets of paths.
Chamber Structure For Double Hurwitz Numbers
Authors: Cavalieri Renzo , JOHNSON Paul , Markwig Hannah
Published: August 2021

Double Hurwitz numbers count covers of the sphere by genus $g$ curves with assigned ramification profiles over $0$ and $\infty$, and simple ramification over a fixed branch divisor. Goulden, Jackson and Vakil (2005) have shown double Hurwitz numbers are piecewise polynomial in the orders of ramification, and Shadrin, Shapiro and Vainshtein (2008) have determined the chamber structure and wall crossing formulas for $g=0$. We provide new proofs of these results, and extend them in several directions. Most importantly we prove wall crossing formulas for all genera. The main tool is the authors' previous work expressing double Hurwitz number as a sum over labelled graphs. We identify the labels of the graphs with lattice points in the chambers of certain hyperplane arrangements, which give rise to piecewise polynomial functions. Our understanding of the wall crossing for these functions builds on the work of Varchenko (1987). This approach to wall crossing appears novel, and may be of broader interest. This extended abstract is based on a new preprint by the authors.

Les nombres de Hurwitz doubles dénombrent les revêtements de la sphère par une surface de genre $g$ avec ramifications prescrites en $0$ et $\infty$, et dont les autres valeurs critiques sont non dégénérées et fixées. Goulden, Jackson et Vakil (2005) ont prouvé que les nombres de Hurwitz doubles sont polynomiaux par morceaux en l'ordre des ramifications prescrites, et Shadrin, Shapiro et Vainshtein (2008) ont déterminé la structure des chambres et ont établis des formules pour traverser les murs en genre $0$. Nous proposons des nouvelles preuves de ces résultats, et les généralisons dans plusieurs directions. En particulier, nous prouvons des formules pour traverser les murs en tout genre. L'outil principal est le précédent travail des auteurs exprimant les nombres de Hurwitz doubles comme somme de graphes étiquetés. Nous identifions les étiquetages avec les points entiers à l'intérieur d'une chambre d'un arrangement d'hyperplans, qui sont connu pour donner une fonction polynomiale par morceaux. Notre étude des formules pour traverser les murs de ces fonctions se base sur un travail antérieur de Varchenko (1987). Cette approche paraît nouvelle, et peut être d'un large intérêt. Ce résumé élargi se base sur un papier nouveau des auteurs.
Three notions of tropical rank for symmetric matrices
Authors: Cartwright Dustin , Chan Melody
Published: August 2021

We introduce and study three different notions of tropical rank for symmetric matrices and dissimilarity matrices in terms of minimal decompositions into rank 1 symmetric matrices, star tree matrices, and tree matrices. Our results provide a close study of the tropical secant sets of certain nice tropical varieties, including the tropical Grassmannian. In particular, we determine the dimension of each secant set, the convex hull of the variety, and in most cases, the smallest secant set which is equal to the convex hull.

Nous introduisons et étudions trois notions différentes de rang tropical pour des matrices symétriques et des matrices de dissimilarité, en utilisant des décompositions minimales en matrices symétriques de rang 1, en matrices d'arbres étoiles, et en matrices d'arbres. Nos résultats donnent lieu à une étude détaillée des ensembles des sécantes tropicales de certaines jolies variétés tropicales, y compris la grassmannienne tropicale. En particulier, nous déterminons la dimension de chaque ensemble des sécantes, l'enveloppe convexe de la variété, ainsi que, dans la plupart des cas, le plus petit ensemble des sécantes qui est égal à l'enveloppe convexe.
Words and Noncommutative Invariants of the Hyperoctahedral Group
Authors: Bergeron-Brlek Anouk
Published: August 2021

Let $\mathcal{B}_n$ be the hyperoctahedral group acting on a complex vector space $\mathcal{V}$. We present a combinatorial method to decompose the tensor algebra $T(\mathcal{V})$ on $\mathcal{V}$ into simple modules via certain words in a particular Cayley graph of $\mathcal{B}_n$. We then give combinatorial interpretations for the graded dimension and the number of free generators of the subalgebra $T(\mathcal{V})^{\mathcal{B}_n}$ of invariants of $\mathcal{B}_n$, in terms of these words, and make explicit the case of the signed permutation module. To this end, we require a morphism from the Mantaci-Reutenauer algebra onto the algebra of characters due to Bonnafé and Hohlweg.

Soit $\mathcal{B}_n$ le groupe hyperoctaédral agissant sur un espace vectoriel complexe $\mathcal{V}$. Nous présentons une méthode combinatoire donnant la décomposition de l'algèbre $T(\mathcal{V})$ des tenseurs sur $\mathcal{V}$ en modules simples via certains mots dans un graphe de Cayley donné. Nous donnons ensuite des interprétations combinatoires pour la dimension graduée et le nombre de générateurs libres de la sous-algèbre $T(\mathcal{V})^{\mathcal{B}_n}$ des invariants de $\mathcal{B}_n$, en termes de ces mots, et explicitons le cas du module de permutation signé. À cette fin, nous utilisons un morphisme entre l'algèbre de Mantaci-Reutenauer et l'algèbre des caractères introduit par Bonnafé et Hohlweg.
Benders decomposition for local access network design with two technologies
Authors: Randazzo C. D. , Luna H. P. L. , Mahey P.
Published: August 2021

We have worked with the local access network design problem with two cable technologies. This is an optimization problem in graphs that consists of linking an origin node to a set of terminal nodes which have a flow demand. There are also a set of Steiner or transshipment nodes which do not have demand. Each arc of the graph has two associated costs: a variable cost depending on the flow through the arc and a fixed cost associated with the installation of the arc. Moreover, in each arc we can install one of two available technologies: optical fiber or copper (we can also use radio links with any other cable technology). Each one of these technologies has different variable and fixed costs. To be more precise, the fixed cost of the optical fiber is greater than that of the copper, but its variable cost is much smaller. The problem was modeled using a multicommodity flow formulation in which we added some structural constraints. This model was used to apply the Benders decomposition method. The structural constraints have the objective of trying to guarantee that the master problem of the Benders decomposition will yield a tree. The Benders subproblems are trivial network flow problems. The dual variables have commodity meaningfull values and are evaluated in a systematic form. The algorithm was implemented in C++ with CPLEX 3.0 callable library. We have tested the algorithm with some test instances obtained by a generator of problems that we developed.
Pattern avoidance in alternating permutations and tableaux (extended abstract)
Authors: Lewis Joel Brewster
Published: August 2021

We give bijective proofs of pattern-avoidance results for a class of permutations generalizing alternating permutations. The bijections employed include a modified form of the RSK insertion algorithm and recursive bijections based on generating trees. As special cases, we show that the sets $A_{2n}(1234)$ and $A_{2n}(2143)$ are in bijection with standard Young tableaux of shape $\langle 3^n \rangle$. Alternating permutations may be viewed as the reading words of standard Young tableaux of a certain skew shape. In the last section of the paper, we study pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape $\lambda / \mu$ whose reading words avoid $213$ is a natural $\mu$-analogue of the Catalan numbers. Similar results for the patterns $132$, $231$ and $312$.

Nous présentons des preuves bijectives de résultats pour une classe de permutations à motifs exclus qui généralisent les permutations alternantes. Les bijections utilisées reposent sur une modification de l'algorithme d'insertion "RSK" et des bijections récursives basées sur des arbres de génération. Comme cas particuliers, nous montrons que les ensembles $A_{2n}(1234)$ et $A_{2n}(2143)$ sont en bijection avec les tableaux standards de Young de la forme $\langle 3^n \rangle$. Une permutation alternante peut être considérée comme le mot de lecture de certain skew tableau. Dans la dernière section de l'article, nous étudions l'évitement des motifs dans les mots de lecture de skew tableaux généraux. Nous montrons bijectivement que le nombre de tableaux standards de forme $\lambda / \mu$ dont les mots de lecture évitent $213$ est un $\mu$-analogue naturel des nombres de Catalan. Des résultats analogues sont valables pour les motifs $132$, $231$ et $312$.
Fully Packed Loop configurations in a triangle and Littlewood Richardson coefficients
Authors: Nadeau Philippe
Published: August 2021

We are interested in Fully Packed Loops in a triangle (TFPLs), as introduced by Caselli at al. and studied by Thapper. We show that for Fully Packed Loops with a fixed link pattern (refined FPL), there exist linear recurrence relations with coefficients computed from TFPL configurations. We then give constraints and enumeration results for certain classes of TFPL configurations. For special boundary conditions, we show that TFPLs are counted by the famous Littlewood Richardson coefficients.

Nous nous intéressons aux configurations de "Fully Packed Loops'' dans un triangle (TFPL), introduites par Caselli et al. et étudiées par Thapper. Nous montrons que pour les Fully Packed Loops avec un couplage donné, il existe des relations de récurrence linéaires dont les coefficients sont calculés à partir de certains TFPLs. Nous donnons ensuite des contraintes et des résultats énumératifs pour certaines familles de TFPLs. Pour certaines conditions au bord, nous montrons que le nombre de TFPL est donné par les coefficients de Littlewood Richardson.
Weakly directed self-avoiding walks
Authors: Bacher Axel , Bousquet-Mélou Mireille
Published: August 2021

We define a new family of self-avoiding walks (SAW) on the square lattice, called $\textit{weakly directed walks}$. These walks have a simple characterization in terms of the irreducible bridges that compose them. We determine their generating function. This series has a complex singularity structure and in particular, is not D-finite. The growth constant is approximately 2.54 and is thus larger than that of all natural families of SAW enumerated so far (but smaller than that of general SAW, which is about 2.64). We also prove that the end-to-end distance of weakly directed walks grows linearly. Finally, we study a diagonal variant of this model.

Nous définissons une nouvelle famille de chemins auto-évitants (CAE) sur le réseau carré, appelés $\textit{chemins faiblement dirigés}$. Ces chemins ont une caractérisation simple en termes des ponts irréductibles qui les composent. Nous déterminons leur série génératrice. Cette série a une structure de singularité complexe et n'est en particulier pas D-finie. La constante de croissance est environ 2,54, ce qui est supérieur à toutes les familles naturelles de SAW étudiées jusqu'à présent, mais inférieur aux CAE généraux (dont la constante est environ 2,64). Nous prouvons également que la distance moyenne entre les extrémités du chemin croît linéairement. Enfin, nous étudions une variante diagonale du modèle.