bluuebunny/crossref_metadata_2025 huggingface dataset:
Cost-effectiveness of algorithms
Authors: Farr Graham
Published: August 2021

Discrete Algorithms

In this paper we discuss how to assess the performance of algorithms for optimisation problems in a way that balances solution quality and time. We propose measures of cost-effectiveness for such algorithms. These measures give the gain in solution quality per time unit over a sequence of inputs, and give a basis for deciding which algorithm to use when aiming for best accumulated solution quality for a given time investment over such an input sequence. Cost-effectiveness measures can be defined for both average-case and worst-case performance. We apply these ideas to three problems: maximum matching, graph colouring and Kolmogorov complexity. For the latter, we propose a cost-effectiveness measure for the time-bounded complexity Kτ(x), and argue that it can be used to measure the cost-effectiveness both of finding a short program to output x and of generating x from such a program. Under mild assumptions, we show that (roughly speaking) if the time-bounded complexity Kτ(x) is to be a cost-effective approximation to K(x) then τ(n)=O(n2).
Bootstrapping and double-exponential limit laws
Authors: Prodinger Helmut , Wagner Stephan
Published: August 2021

Combinatorics

We provide a rather general asymptotic scheme for combinatorial parameters that asymptotically follow a discrete double-exponential distribution. It is based on analysing generating functions Gh(z) whose dominant singularities converge to a certain value at an exponential rate. This behaviour is typically found by means of a bootstrapping approach. Our scheme is illustrated by a number of classical and new examples, such as the longest run in words or compositions, patterns in Dyck and Motzkin paths, or the maximum degree in planted plane trees.
The double competition multigraph of a digraph
Authors: Sano Yoshio , Park Jeongmi
Published: August 2021

In this article, we introduce the notion of the double competition multigraph of a digraph. We give characterizations of the double competition multigraphs of arbitrary digraphs, loopless digraphs, reflexive digraphs, and acyclic digraphs in terms of edge clique partitions of the multigraphs.
Classical Automata on Promise Problems
Authors: Geffert Viliam , Yakaryilmaz Abuzer
Published: August 2021

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and one-way deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential. Last, we show that the situation is different for one-way probabilistic automata with two-sided bounded-error. We present a family of unary promise problems that is very easy for these machines; solvable with only two states, but the number of states in two-way alternating or any simpler automata is not limited by a constant. Moreover, we show that one-way bounded-error probabilistic automata can solve promise problems not solvable at all by any other classical model.
Arithmetic completely regular codes
Authors: Koolen Jacobus , Sun Lee Woo , Martin William , Tanaka Hajime
Published: August 2021

In this paper, we explore completely regular codes in the Hamming graphs and related graphs. Experimental evidence suggests that many completely regular codes have the property that the eigenvalues of the code are in arithmetic progression. In order to better understand these "arithmetic completely regular codes", we focus on cartesian products of completely regular codes and products of their corresponding coset graphs in the additive case. Employing earlier results, we are then able to prove a theorem which nearly classifies these codes in the case where the graph admits a completely regular partition into such codes (e.g, the cosets of some additive completely regular code). Connections to the theory of distance-regular graphs are explored and several open questions are posed.
Connected Tropical Subgraphs in Vertex-Colored Graphs
Authors: Anglès d'Auriac Jean-Alexandre , Cohen Nathann , El Mafthoui Hakim , Harutyunyan Ararat , Legay Sylvain , Manoussakis Yannis
Published: August 2021

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the graph. In this work we study the problem of finding a minimal connected tropical subgraph. We first show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when the number of colors is logarithmic in terms of the order of the graph (i.e. FPT). We then provide upper bounds for the order of the minimal connected tropical subgraph under various conditions. We finally study the problem of finding a connected tropical subgraph in a randomly vertex-colored random graph.
An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size
Authors: Zeng De-Yan , Yin Jian-Hua
Published: August 2021

A graph $G$ is a $2$-tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.
Rainbow eulerian multidigraphs and the product of cycles
Authors: López Susana , Muntaner-Batle Francesc-Antoni
Published: August 2021

An arc colored eulerian multidigraph with $l$ colors is rainbow eulerian if there is an eulerian circuit in which a sequence of $l$ colors repeats. The digraph product that refers the title was introduced by Figueroa-Centeno et al. as follows: let $D$ be a digraph and let $\Gamma$ be a family of digraphs such that $V(F)=V$ for every $F\in \Gamma$. Consider any function $h:E(D) \longrightarrow \Gamma$. Then the product $D \otimes_h \Gamma$ is the digraph with vertex set $V(D) \times V$ and $((a,x),(b,y)) \in E(D \otimes_h \Gamma)$ if and only if $(a,b) \in E(D)$ and $(x,y) \in E(h (a,b))$. In this paper we use rainbow eulerian multidigraphs and permutations as a way to characterize the $\otimes_h$-product of oriented cycles. We study the behavior of the $\otimes_h$-product when applied to digraphs with unicyclic components. The results obtained allow us to get edge-magic labelings of graphs formed by the union of unicyclic components and with different magic sums.
Characterization of Lattices Induced by (extended) Chip Firing Games
Authors: Magnien Clémence , Phan Ha Duong , Vuillon Laurent
Published: August 2021

The Chip Firing Game (CFG) is a discrete dynamical model used in physics, computer science and economics. It is known that the set of configurationsreachable from an initial configuration (this set is called the \textitconfiguration space) can be ordered as a lattice. We first present a structural result about this model, which allows us to introduce some useful tools for describing those lattices. Then we establish that the class of lattices that are the configuration space of a CFG is strictly between the class of distributive lattices and the class of upper locally distributive (or ULD) lattices. Finally we propose an extension of the model, the \textitcoloured Chip Firing Game, which generates exactly the class of ULD lattices.
Representing Reversible Cellular Automata with Reversible Block Cellular Automata
Authors: Durand-Lose Jérôme
Published: August 2021

Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks.We prove that any d-dimensional reversible cellular automaton can be exp ressed as thecomposition of d+1 block permutations.We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus (Physica D 45) improved by Kari in 1996 (Mathematical System Theory 29).
Pseudo-Permutations II: Geometry and Representation Theory
Authors: Boulier François , Hivert Florent , Krob Daniel , Novelli Jean-Christophe
Published: August 2021

In this paper, we provide the second part of the study of the pseudo-permutations. We first derive a complete analysis of the pseudo-permutations, based on hyperplane arrangements, generalizing the usual way of translating the permutations. We then study the module of the pseudo-permutations over the symmetric group and provide the characteristics of this action.
Experimental study of Elementary Cellular Automata dynamics using the density parameter
Authors: Fatès Nazim
Published: August 2021

Classifying cellular automata in order to capture the notion of chaos algorithmically is a challenging problem than can be tackled in many ways.We here give a classification based on the computation of a macroscopic parameter, the $d$-spectrum, and show how our classifying scheme can be used to separate the chaotic ECA from the non-chaotic ones.
Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.
Authors: Barrett Christopher L. , Hunt Harry , Marathe Madhav V. , Ravi S. S. , Rosenkrantz Daniel J. , Stearns Richard E.
Published: August 2021

A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was introduced in [BR99] as a formal model for analyzing simulation systems. Here, we address the complexity of two basic problems and their generalizations for SDSs.Given an SDS $\mathcal{S}$ and a configuration $\mathcal{C}$, the PREDECESSOR EXISTENCE (or PRE) problem is to determine whether there is a configuration $\mathcal{C}'$ such that $\mathcal{S}$ has a transition from $\mathcal{C}'$ to $\mathcal{C}$. Our results provide separations between efficiently solvable and computationally intractable instances of the PRE problem. For example, we show that the PRE problem can be solved efficiently for SDSs with Boolean state values when the node functions are symmetric and the underlying graph is of bounded tree width. In contrast, we show that allowing just one non-symmetric node function renders the problem $\mathbf{NP}$-complete even when the underlying graph is a star (which has a tree width of 1). Our results extend some of the earlier results by Sutner [Su95] and Green [Gr87] on the complexity of the PREDECESSOR EXISTENCE problem for 1-dimensional cellular automata.Given two configurations $\mathcal{C}$ and $\mathcal{C}'$ of a partial SDS $\mathcal{S}$, the PERMUTATION EXISTENCE (or PME) problem is to determine whether there is a permutation of nodes such that $\mathcal{S}$ has a transition from $\mathcal{C}'$ to $\mathcal{C}$ in one step. We show that the PME problem is $\mathbf{NP}$-complete even when the function associated with each node is a simple-threshold function. We also show that the problem can be solved efficiently for SDSs whose underlying graphs are of bounded degree and bounded tree width. We consider a generalized version (GEN-PME) of the PME problem and show that the problem is $\mathbf{NP}$-complete for SDSs where each node function is NOR and the underlying graph has a maximum node degree of 3. When each node computes the OR function or when each node computes the AND function, we show that the GEN-PME problem is solvable in polynomial time.
A Hopf-power Markov chain on compositions
Authors: Pang C.Y. Amy
Published: August 2021

In a recent paper, Diaconis, Ram and I constructed Markov chains using the coproduct-then-product map of a combinatorial Hopf algebra. We presented an algorithm for diagonalising a large class of these "Hopf-power chains", including the Gilbert-Shannon-Reeds model of riffle-shuffling of a deck of cards and a rock-breaking model. A very restrictive condition from that paper is removed in my thesis, and this extended abstract focuses on one application of the improved theory. Here, I use a new technique of lumping Hopf-power chains to show that the Hopf-power chain on the algebra of quasisymmetric functions is the induced chain on descent sets under riffle-shuffling. Moreover, I relate its right and left eigenfunctions to Garsia-Reutenauer idempotents and ribbon characters respectively, from which I recover an analogous result of Diaconis and Fulman (2012) concerning the number of descents under riffle-shuffling.

Dans un récent article avec Diaconis et Ram, nous avons construit des chaînes de Markov en utilisant une composition du coproduit et produit d’une algèbre de Hopf combinatoire. Nous avons présenté un algorithme pour diagonaliser une large classe de ces “chaînes de Hopf puissance”, en particulier nous avons diagonalisé le modèle de Gilbert-Shannon-Reeds de mélange de cartes en “riffle shuffle” (couper en deux, puis intercaler) et un modèle de cassage de pierres. Dans mon travail de thèse, nous supprimons une condition très restrictive de cet article, et ce papier se concentre surune application de cette amélioration. Nous utilisons ici une nouvelle technique de projection de chaînes de Hopf puissance pour montrer que la chaîne de Hopf puissance sur l’algèbre des fonctions quasi-symétriques est la chaîne de Markov induite sur les ensembles des descentes dans le “riffle shuffling”. De plus, nous faisons le lien entre les fonctions propres à droite et à gauche et respectivement les idempotents de Garsia-Reutenauer et les caractères en rubans, ce qui nous permet de retrouver un résultat analogue à Diaconis et Fulman (2012) concernant le nombre de descentes dans le “riffle shuffling”.
Singularity analysis via the iterated kernel method
Authors: Melczer Stephen , Mishna Marni
Published: August 2021

We provide exact and asymptotic counting formulas for five singular lattice path models in the quarter plane. Furthermore, we prove that these models have a non D-finite generating function.

Nous présentons des résultats énumératifs pour les cinq modèles de marche dans le quart de plan dites "singulière''. Nous prouvons que ces modèles sont non-holonomes.
Structure coefficients of the Hecke algebra of $(\mathcal{S}_{2n}, \mathcal{B}_n)$
Authors: Tout Omar
Published: August 2021

The Hecke algebra of the pair $(\mathcal{S}_{2n}, \mathcal{B}_n)$, where $\mathcal{B}_n$ is the hyperoctahedral subgroup of $\mathcal{S}_{2n}$, was introduced by James in 1961. It is a natural analogue of the center of the symmetric group algebra. In this paper, we give a polynomiality property of its structure coefficients. Our main tool is a combinatorial universal algebra which projects on the Hecke algebra of $(\mathcal{S}_{2n}, \mathcal{B}_n)$ for every $n$. To build it, we introduce new objects called partial bijections.

L’algèbre de Hecke de la paire $(\mathcal{S}_{2n}, \mathcal{B}_n)$ , où $\mathcal{B}_n$ est le sous-groupe hyperoctaèdral de $\mathcal{S}_{2n}$, aété introduite par James en 1961. C’est un analogue naturel du centre de l’algèbre du groupe symétrique. Dans ce papier, on donne une propriété de polynomialité de ses coefficients de structure. On utilise une algèbre universelle construite d’une façon combinatoire et qui se projette sur toutes les algèbres de Hecke de $(\mathcal{S}_{2n}, \mathcal{B}_n)$. Pour la construire, on introduit de nouveaux objets appelés bijections partielles.
Extending the parking space
Authors: Berget Andrew , Rhoades Brendon
Published: August 2021

The action of the symmetric group $S_n$ on the set $\mathrm{Park}_n$ of parking functions of size $n$ has received a great deal of attention in algebraic combinatorics. We prove that the action of $S_n$ on $\mathrm{Park}_n$ extends to an action of $S_{n+1}$. More precisely, we construct a graded $S_{n+1}$-module $V_n$ such that the restriction of $V_n$ to $S_n$ is isomorphic to $\mathrm{Park}_n$. We describe the $S_n$-Frobenius characters of the module $V_n$ in all degrees and describe the $S_{n+1}$-Frobenius characters of $V_n$ in extreme degrees. We give a bivariate generalization $V_n^{(\ell, m)}$ of our module $V_n$ whose representation theory is governed by a bivariate generalization of Dyck paths. A Fuss generalization of our results is a special case of this bivariate generalization.

L’action du groupe symétrique $S_n$ sur l’ensemble $\mathrm{Park}_n$ des fonctions de stationnement de longueur $n$ a reçu beaucoup d’attention dans la combinatoire algébrique. Nous démontrons que l’action de $S_n$ sur $\mathrm{Park}_n$ s’étend à une action de $S_{n+1}$. Plus précisément, nous construisons un gradué $S_{n+1}$-module $V_n$ telles que la restriction de $S_n$ est isomorphe à $\mathrm{Park}_n$. Nous décrivons la $S_n$-Frobenius caractères des modules $V_n$ à tous les degrés et décrivent le $S_{n+1}$-Frobenius caractères de $V_n$ en degrés extrêmes. Nous donnons une généralisation bivariée $V_n^{(\ell, m)}$ de notre module $V_n$ dont la représentation théorie est régie par une généralisation bivariée des chemins de Dyck. Une généralisation Fuss de nos résultats est un cas particulier de cette généralisation bivariée.
On the ranks of configurations on the complete graph
Authors: Cori Robert , Borgne Yvan Le
Published: August 2021

We consider the parameter rank introduced for graph configurations by M. Baker and S. Norine. We focus on complete graphs and obtain an efficient algorithm to determine the rank for these graphs. The analysis of this algorithm leads to the definition of a parameter on Dyck words, which we call prerank. We prove that the distribution of area and prerank on Dyck words of given length $2n$ leads to a polynomial with variables $q,t$ which is symmetric in these variables. This polynomial is different from the $q,t-$Catalan polynomial studied by A. Garsia, J. Haglund and M. Haiman.
Operators of equivalent sorting power and related Wilf-equivalences
Authors: Albert Michael , Bouvel Mathilde
Published: August 2021

We study sorting operators $\textrm{A}$ on permutations that are obtained composing Knuth's stack sorting operator \textrmS and the reverse operator $\textrm{R}$, as many times as desired. For any such operator $\textrm{A}$, we provide a bijection between the set of permutations sorted by $\textrm{S} \circ \textrm{A}$ and the set of those sorted by $\textrm{S} \circ \textrm{R} \circ \textrm{A}$, proving that these sets are enumerated by the same sequence, but also that many classical permutation statistics are equidistributed across these two sets. The description of this family of bijections is based on an apparently novel bijection between the set of permutations avoiding the pattern $231$ and the set of those avoiding $132$ which preserves many permutation statistics. We also present other properties of this bijection, in particular for finding families of Wilf-equivalent permutation classes.
A generalization of Mehta-Wang determinant and Askey-Wilson polynomials
Authors: Guo Victor J. W. , Ishikawa Masao , Tagawa Hiroyuki , Zeng Jiang
Published: August 2021

Motivated by the Gaussian symplectic ensemble, Mehta and Wang evaluated the $n×n$ determinant $\det ((a+j-i)Γ (b+j+i))$ in 2000. When $a=0$, Ciucu and Krattenthaler computed the associated Pfaffian $\mathrm{Pf}((j-i)Γ (b+j+i))$ with an application to the two dimensional dimer system in 2011. Recently we have generalized the latter Pfaffian formula with a $q$-analogue by replacing the Gamma function by the moment sequence of the little $q$-Jacobi polynomials. On the other hand, Nishizawa has found a q-analogue of the Mehta–Wang formula. Our purpose is to generalize both the Mehta-Wang and Nishizawa formulae by using the moment sequence of the little $q$-Jacobi polynomials. It turns out that the corresponding determinant can be evaluated explicitly in terms of the Askey-Wilson polynomials.
Cycles and sorting index for matchings and restricted permutations
Authors: Poznanović Svetlana
Published: August 2021

We prove that the Mahonian-Stirling pairs of permutation statistics $(sor, cyc)$ and $(∈v , \mathrm{rlmin})$ are equidistributed on the set of permutations that correspond to arrangements of $n$ non-atacking rooks on a fixed Ferrers board with $n$ rows and $n$ columns. The proofs are combinatorial and use bijections between matchings and Dyck paths and a new statistic, sorting index for matchings, that we define. We also prove a refinement of this equidistribution result which describes the minimal elements in the permutation cycles and the right-to-left minimum letters.
Dual Equivalence Graphs Revisited
Authors: Roberts Austin
Published: August 2021

In 2007 Sami Assaf introduced dual equivalence graphs as a method for demonstrating that a quasisymmetric function is Schur positive. The method involves the creation of a graph whose vertices are weighted by Ira Gessel's fundamental quasisymmetric functions so that the sum of the weights of a connected component is a single Schur function. In this paper, we improve on Assaf's axiomatization of such graphs, giving locally testable criteria that are more easily verified by computers. We then demonstrate the utility of this result by giving explicit Schur expansions for a family of Lascoux-Leclerc-Thibon polynomials. This family properly contains the previously known case of polynomials indexed by two skew shapes, as was described in a 1995 paper by Christophe Carré and Bernard Leclerc. As an immediate corollary, we gain an explicit Schur expansion for a family of modified Macdonald polynomials in terms of Yamanouchi words. This family includes all polynomials indexed by shapes with less than four cells in the first row and strictly less than three cells in the second row, a slight improvement over the known two column case described in 2005 by James Haglund, Mark Haiman, and Nick Loehr.
Homomesy in products of two chains
Authors: Propp James , Roby Tom
Published: August 2021

Many cyclic actions $τ$ on a finite set $\mathcal{S}$ ; of combinatorial objects, along with a natural statistic $f$ on $\mathcal{S}$, exhibit ``homomesy'': the average of $f$ over each $τ$-orbit in $\mathcal{S} $ is the same as the average of $f$ over the whole set $\mathcal{S} $. This phenomenon was first noticed by Panyushev in 2007 in the context of antichains in root posets; Armstrong, Stump, and Thomas proved Panyushev's conjecture in 2011. We describe a theoretical framework for results of this kind and discuss old and new results for the actions of promotion and rowmotion on the poset that is the product of two chains.
The Gaussian free field and strict plane partitions
Authors: Vuletić Mirjana
Published: August 2021

We study height fluctuations around the limit shape of a measure on strict plane partitions. It was shown in our earlier work that this measure is a Pfaffian process. We show that the height fluctuations converge to a pullback of the Green's function for the Laplace operator with Dirichlet boundary conditions on the first quadrant. We use a Pfaffian formula for higher moments to show that the height fluctuations are governed by the Gaussian free field. The results follow from the correlation kernel asymptotics which is obtained by the steepest descent method.
Convolution Powers of the Identity
Authors: Aguiar Marcelo , Lauve Aaron
Published: August 2021

We study convolution powers $\mathtt{id}^{\ast n}$ of the identity of graded connected Hopf algebras $H$. (The antipode corresponds to $n=-1$.) The chief result is a complete description of the characteristic polynomial - both eigenvalues and multiplicity - for the action of the operator $\mathtt{id}^{\ast n}$ on each homogeneous component $H_m$. The multiplicities are independent of $n$. This follows from considering the action of the (higher) Eulerian idempotents on a certain Lie algebra $\mathfrak{g}$ associated to $H$. In case $H$ is cofree, we give an alternative (explicit and combinatorial) description in terms of palindromic words in free generators of $\mathfrak{g}$. We obtain identities involving partitions and compositions by specializing $H$ to some familiar combinatorial Hopf algebras.

Nous étudions les puissances de convolution $\mathtt{id}^{\ast n}$ de l’identité d’une algèbre de Hopf graduée et connexe $H$ quelconque. (L’antipode correspond à $n=-1$.) Le résultat principal est une description complète du polynôme caractéristique (des valeurs propres et de leurs multiplicités) de l’opérateur $\mathtt{id}^{\ast n}$ agissant sur chaque composante homogène $H_m$. Les multiplicités sont indépendants de $n$. Ceci résulte de l’examen de l’action des idempotents eulériens (supérieures) sur une algèbre de Lie $\mathfrak{g}$ associée à $H$. Dans le cas où $H$ est colibre, nous donnons une description alternative (explicite et combinatoire) en termes de mots palindromes dans les générateurs libres de $\mathfrak{g}$. Nous obtenons des identités impliquant des partitions et compositions en choisissant comme $H$ certaines algèbres de Hopf combinatoires connues.
BERGMAN under MS-DOS and Anick's resolution
Authors: Cojocaru S. , Ufnarovski V.
Published: August 2021

Noncommutative algebras, defined by the generators and relations, are considered. The definition and main results connected with the Gröbner basis, Hilbert series and Anick's resolution are formulated. Most attention is paid to universal enveloping algebras. Four main examples illustrate the main concepts and ideas. Algorithmic problems arising in the calculation of the Hilbert series are investigated. The existence of finite state automata, defining thebehaviour of the Hilbert series, is discussed. The extensions of the BERGMAN package for IBM PC compatible computers are described. A table is provided permitting a comparison of the effectiveness of the calculations in BERGMAN with the other systems.
Splines, lattice points, and (arithmetic) matroids
Authors: Lenz Matthias
Published: August 2021

Let $X$ be a $(d \times N)$-matrix. We consider the variable polytope $\Pi_X(u) = \left\{ w \geq 0 : Xw = u \right\}$. It is known that the function $T_X$ that assigns to a parameter $u \in \mathbb{R}^N$ the volume of the polytope $\Pi_X(u)$ is piecewise polynomial. Formulas of Khovanskii-Pukhlikov and Brion-Vergne imply that the number of lattice points in $\Pi_X(u)$ can be obtained by applying a certain differential operator to the function $T_X$. In this extended abstract we slightly improve the formulas of Khovanskii-Pukhlikov and Brion-Vergne and we study the space of differential operators that are relevant for $T_X$ (ıe operators that do not annihilate $T_X$) and the space of nice differential operators (ıe operators that leave $T_X$ continuous). These two spaces are finite-dimensional homogeneous vector spaces and their Hilbert series are evaluations of the Tutte polynomial of the (arithmetic) matroid defined by $X$.

Soit $X$ une matrice $(d \times N)$. Nous considérons le polytope variable $\Pi_X(u) = \left\{ w \geq 0 : Xw = u \right\}$. Il est connu que la fonction $T_X$ qui attribue à un paramètre $u$ le volume du polytope $\Pi_X(u)$ est polynomiale par morceaux. Des formules de Khovanskii-Pukhlikov et de Brion-Vergne impliquent que le nombre de points de réseau dans $\Pi_X(u)$ peut être obtenu en appliquant un certain opérateur différentiel à la fonction $T_X$. Dans ce résumé élargi nous améliorons un peu les formules de Khovanskii-Pukhlikov et de Brion-Vergne et nous étudions l’espaced’opérateurs différentiels qui sont importants pour $T_X$ (c’est-à-dire les opérateurs qui n’annulent pas $T_X$) et l’espace d’opérateurs différentiels bons (c’est-à-dire les opérateurs qui laissent $T_X$ continue). Ces deux espaces sont espaces vectoriels homogène de dimension finie et leurs séries de Hilbert sont des évaluations du polynôme de Tutte du matroïde (arithmétique) défini par $X$.
A generalization of the carries process
Authors: Fujita Takahiko , Nakano Fumihiko , Sadahiro Taizo
Published: August 2021

We consider a carries process which is a generalization of that by Holte in the sense that (i) we take various digit sets, and (ii) we also consider negative base. Our results are : (i) eigenvalues and eigenvectors of the transition probability matrices, and their connection to combinatorics and representation theory, (ii) an application to the computation of the distribution of the sum of i.i.d. uniform r.v.'s on [0,1], (iii) a relation to riffle shuffle.
Boyd-Maxwell ball packings
Authors: Chen Hao , Labbé Jean-Philippe
Published: August 2021

In the recent study of infinite root systems, fractal patterns of ball packings were observed while visualizing roots in affine space. In fact, the observed fractals are exactly the ball packings described by Boyd and Maxwell. This correspondence is a corollary of a more fundamental result: given a geometric representation of a Coxeter group in Lorentz space, the set of limit directions of weights equals the set of limit roots.
Many neighborly inscribed polytopes and Delaunay triangulations
Authors: Gonska Bernd , Padrol Arnau
Published: August 2021

We present a very simple explicit technique to generate a large family of point configurations with neighborly Delaunay triangulations. This proves that there are superexponentially many combinatorially distinct neighborly $d$-polytopes with $n$ vertices that admit realizations inscribed on the sphere. These are the first examples of inscribable neighborly polytopes that are not cyclic polytopes, and provide the current best lower bound for the number of combinatorial types of inscribable polytopes (and thus also of Delaunay triangulations). It coincides with the current best lower bound for the number of combinatorial types of polytopes.

Nous présentons une technique explicite simple pour générer une large famille de configurations de points dont les triangulations de Delaunay sontneighborly. Cela prouve que le nombre de $d$-polytopes combinatoirement distincts avec $n$ sommets et admettant une réalisation inscrite sur la sphère est surexponentiel. Ce sont les premiers exemples de polytopes inscriptibles neighborly qui ne sont pas des polytopes cycliques et ils donnent la meilleure borne inférieure actuelle pour le nombre de types combinatoires de polytopes inscriptibles (et donc aussi de triangulations de Delaunay). Cette borne coïncide avec la meilleure borne inférieure actuelle pour le nombre de types combinatoires de polytopes.
The purity of set-systems related to Grassmann necklaces
Authors: Danilov Vladimir , Karzanov Alexander , Koshevoy Gleb
Published: August 2021

Studying the problem of quasicommuting quantum minors, Leclerc and Zelevinsky introduced in 1998 the notion of weakly separated sets in $[n]:=\{1,\ldots, n\}$. Moreover, they raised several conjectures on the purity for this symmetric relation, in particular, on the Boolean cube $2^{[n]}$. In 0909.1423[math.CO] we proved these purity conjectures for the Boolean cube $2^{[n]}$, the discrete Grassmanian $\binom{[n]}{r}$, and some other set-systems. Oh, Postnikov, and Speyer in arxiv:1109.4434 proved the purity for weakly separated collections inside a positroid which contain a Grassmann necklace $\mathcal {N}$ defining the positroid. We denote such set-systems as $\mathcal{Int}(\mathcal {N} )$. In this paper we give an alternative (and shorter) proof of the purity of $\mathcal{Int}(\mathcal {N} )$ and present a stronger result. More precisely, we introduce a set-system $\mathcal{Out}(\mathcal {N} )$ complementary to $\mathcal{Int}(\mathcal {N })$, in a sense, and establish its purity. Moreover, we prove (Theorem~3) that these two set-systems are weakly separated from each other. As a consequence of Theorem~3, we obtain the purity of set-systems related to pairs of weakly separated necklaces (Proposition 4 and Corollaries 1 and 2). Finally, we raise a conjecture on the purity of both the interior and exterior of a generalized necklace.
E-unification by means of tree tuple synchronized grammars
Authors: Limet Sébastien , Réty Pierre
Published: August 2021

The goal of this paper is both to give an E-unification procedure that always terminates, and to decide unifiability. For this, we assume that the equational theory is specified by a confluent and constructor-based rewrite system, and that four additional restrictions are satisfied. We give a procedure that represents the (possibly infinite) set of solutions thanks to a tree tuple synchronized grammar, and that can decide upon unifiability thanks to an emptiness test. Moreover, we show that if only three of the four additional restrictions are satisfied then unifiability is undecidable.
Electrical network and Lie theory
Authors: Su Yi
Published: August 2021

Curtis-Ingerman-Morrow studied the space of circular planar electrical networks, and classified all possible response matrices for such networks. Lam and Pylyavskyy found a Lie group $EL_{2n}$ whose positive part $(EL_{2n})_{\geq 0}$ naturally acts on the circular planar electrical network via some combinatorial description, where the action is inspired by the star-triangle transformation of the electrical networks. The Lie algebra $el_{2n}$ is semisimple and isomorphic to the symplectic algebra. In the end of their paper, they suggest a generalization of electrical Lie algebras to all finite Dynkin types. We give the structure of the type $B$ electrical Lie algebra $e_{b_{2n}}$. The nonnegative part $(E_{B_{2n}})_{\geq 0}$ of the corresponding Lie group conjecturally acts on a class of "mirror symmetric circular planar electrical networks". This class of networks has interesting combinatorial properties. Finally, we mention some partial results for type $C$ and $D$ electrical Lie algebras, where an analogous story needs to be developed.

Curtis, Ingerman et Morrow ont étudié l’espace des réseaux électriques circulaires plans et ont classifié toutes les matrices de réponses possibles pour ces réseaux. Lam et Pylyavskyy ont trouvé un groupe de Lie $EL_{2n}$ dont la partie positive $(EL_{2n})_{\geq 0}$ agit naturellement sur le réseau électrique circulaire plan par une description combinatoire, où l’action est inspirée par la transformation étoile vers triangle des réseaux électriques. L’algèbre de Lie $el_{2n}$ est semi-simple et isomorphe à l’algèbre symplectique. A la fin de leur article, ils proposent une généralisation des algèbres de Lie électriques pour tous les types de Dynkin finis. Nous donnons la structure de l’algèbre de Lie électrique $e_{b_{2n}}$ du type $B$. La partie positive $(E_{B_{2n}})_{\geq 0}$ du groupe de Lie correspondant agit conjecturalement sur une famille de ”miroirs réseaux électriques circulaires symétriques plans”. Cette famille de réseaux a des propriétés combinatoires intéressantes. Nous donnons enfin quelques résultats partiels de l’algèbre de Lie électrique du type $C$ et du type $D$, où une étude analogue doit être développée.
On Bruhat posets associated to compositions
Authors: Can Mahir Bilen , Cherniavsky Yonah
Published: August 2021

The purpose of this work is to initiate a combinatorial study of the Bruhat-Chevalley ordering on certain sets of permutations obtained by omitting the parentheses from their standard cyclic notation. In particular, we show that these sets form bounded, graded, unimodal, rank-symmetric and EL-shellable posets. Moreover, we determine the homotopy types of the associated order complexes.

Le but de ce travail est de lancer une étude combinatoire de l’ordre de Bruhat-Chevalley sur certains ensembles de permutations obtenues en omettant les parenthèses de leur notation cyclique standard. En particulier, nous montrons que ces ensembles forment des posets bornés, classés, unimodaux, rang-symétriques et EL-shellable. De plus, nous déterminons les types de complexes d’ordre associés d’homotopie.
A bijection between irreducible k-shapes and surjective pistols of height $k-1$
Authors: Bigeni Ange
Published: August 2021

This paper constructs a bijection between irreducible $k$-shapes and surjective pistols of height $k-1$, which carries the "free $k$-sites" to the fixed points of surjective pistols. The bijection confirms a conjecture of Hivert and Mallet (FPSAC 2011) that the number of irreducible $k$-shape is counted by the Genocchi number $G_{2k}$.

On construit une bijection entre les $k$-formes irréductibles et les pistolets surjectifs de hauteur $k-1$ qui envoie les ”$k$-sites libres” sur les points fixes des pistolets. Cette bijection démontre une conjecture de Hivert et Mallet (FPSAC 2011), selon laquelle les $k$-formes irréductibles sont comptées par les nombres de Genocchi $G_{2k}$.
A diagrammatic approach to Kronecker squares
Authors: Vallejo Ernesto
Published: August 2021

In this paper we improve a method of Robinson and Taulbee for computing Kronecker coefficients and show that for any partition $\overline{ν}$ of $d$ there is a polynomial $k_{\overline{ν}}$ with rational coefficients in variables $x_C$, where $C$ runs over the set of isomorphism classes of connected skew diagrams of size at most $d$, such that for all partitions $\lambda$ of $n$, the Kronecker coefficient $\mathsf{g}(\lambda, \lambda, (n-d, \overline{ν}))$ is obtained from $k_{\overline{ν}}(x_C)$ substituting each $x_C$ by the number of $\lambda$-removable diagrams in $C$. We present two applications. First we show that for $\rho_{k} = (k, k-1,\ldots, 2, 1)$ and any partition $\overline{ν}$ of size $d$ there is a piecewise polynomial function $s_{\overline{ν}}$ such that $\mathsf{g}(\rho_k, \rho_k, (|\rho_k| - d, \overline{ν})) = s_{\overline{ν}} (k)$ for all $k$ and that there is an interval of the form $[c, \infty)$ in which $s_{\overline{ν}}$ is polynomial of degree $d$ with leading coefficient the number of standard Young tableaux of shape $\overline{ν}$. The second application is new stability property for Kronecker coefficients.

Dans ce papier nous améliorons une méthode de Robinson-Taulbee pour calculer les coefficients de Kronecker et montrons que pour toute partition $\overline{ν}$ de $d$ il y a un polynôme $k_{\overline{ν}}$ avec coefficients rationnels dans les variables $x_C$, où $C$ est dans l’ensemble de classes d’isomorphisme des diagrammes gauches connexes de taille non plus que $d$, tel que pour toute partition $\lambda$ de $n$, le coefficient de Kronecker $\mathsf{g}(\lambda, \lambda, (n-d, \overline{ν}))$ est obtenu de $k_{\overline{ν}}(x_C)$ en substituant chaque $x_C$ pour le nombre de diagrammes $\lambda$-removables en $C$. Nous présentons deux applications. Premièrement nous montrons que pour $\rho_{k} = (k, k-1,\ldots, 2, 1)$ et une partition $\overline{ν}$ de taille $d$ il y a une fonction polynôme par morceaux $s_{\overline{ν}}$ tel que pour toute $k$ on a $\mathsf{g}(\rho_k, \rho_k, (|\rho_k| - d, \overline{ν})) = s_{\overline{ν}} (k)$ et qu'il y a une intervalle de la forme $[c, \infty)$ dans laquelle $s_{\overline{ν}}$ est polynôme de degré $d$ avec coefficient principal le nombre de tableaux de Young standard de forme $\overline{ν}$. La seconde application est une nouveau propriété de stabilité des coefficients de Kronecker.
Piecewise-linear and birational toggling
Authors: Einstein David , Propp James
Published: August 2021

We define piecewise-linear and birational analogues of toggle-involutions, rowmotion, and promotion on order ideals of a poset $P$ as studied by Striker and Williams. Piecewise-linear rowmotion relates to Stanley's transfer map for order polytopes; piecewise-linear promotion relates to Schützenberger promotion for semistandard Young tableaux. When $P = [a] \times [b]$, a reciprocal symmetry property recently proved by Grinberg and Roby implies that birational rowmotion (and consequently piecewise-linear rowmotion) is of order $a+b$. We prove some homomesy results, showing that for certain functions $f$, the average of $f$ over each rowmotion/promotion orbit is independent of the orbit chosen.

Nous définissons et étudions certains analogues linéaires-par-morceaux et birationnels d’involutions toggles, rowmotion et promotion sur les idéaux d’un poset $P$, comme étudié par Striker et Williams. La rowmotion linéaire-par-morceaux est liée à la fonction transfert de Stanley pour les polytopes d’ordre; la promotion linéaire-par-morceaux se rapporte à la promotion de Schützenberger pour les tableaux semi-standards de Young. Lorsque $P = [a] \times [b]$, une propriété de symétrie réciproque récemment prouvée par Grinberg et Roby implique que la rowmotion birationnelle (et par conséquent la rowmotion linéaire-par-morceaux) est de l’ordre $a+b$. Nous démontrons quelques résultats d’homomésie, montrant que pour certaines fonctions $f$, la moyenne de $f$ sur chaque orbite de rowmotion/promotion est indépendante de l’orbite choisie.
Computations in finite-dimensional Lie algebras
Authors: Cohen A. M. , Graaf W. A. , Rónyai L.
Published: August 2021

This paper describes progress made in context with the construction of a general library of Lie algebra algorithms, called ELIAS (Eindhoven Lie Algebra System), within the computer algebra package GAP. A first sketch of the package can be found in Cohen and de Graaf[1]. Since then, in a collaborative effort with G. Ivanyos, the authors have continued to develop algorithms which were implemented in ELIAS by the second author. These activities are part of a bigger project, called ACELA and financed by STW, the Dutch Technology Foundation, which aims at an interactive book on Lie algebras (cf. Cohen and Meertens [2]). This paper gives a global description of the main ways in which to present Lie algebras on a computer. We focus on the transition from a Lie algebra abstractly given by an array of structure constants to a Lie algebra presented as a subalgebra of the Lie algebra of n×n matrices. We describe an algorithm typical of the structure analysis of a finite-dimensional Lie algebra: finding a Levi subalgebra of a Lie algebra.
Selberg integrals and Hankel determinants
Authors: Ishikawa Masao , Zeng Jiang
Published: August 2021

In our previous works "Pfaffian decomposition and a Pfaffian analogue of $q$-Catalan Hankel determinants'' (by M.Ishikawa, H. Tagawa and J. Zeng, J. Combin. Theory Ser. A, 120, 2013, 1263-1284) we have proposed several ways to evaluate certain Catalan-Hankel Pffafians and also formulated several conjectures. In this work we propose a new approach to compute these Catalan-Hankel Pffafians using Selberg's integral as well as their $q$-analogues. In particular, this approach permits us to settle most of the conjectures in our previous paper.

Dans nos travaux précédents “Pfaffian decomposition and a Pfaffian analogue of $q$-Catalan Hankel determinants” (by M.Ishikawa, H. Tagawa and J. Zeng, J. Combin. Theory Ser. A, 120, 2013, 1263–1284) nous avons proposé plusieurs méthodes pour évaluer certains Catalan–Pffafian déterminants de Hankel et avons aussi formulé plusieurs conjectures. Dans ce travail nous proposons une nouvelle approche pour calculer ces Catalan-Pffafian déterminants de Hankel en utilisant l’intégrale de Selberg ainsi que leurs $q$-analogues. En particulier, cette approche nous permet de confirmer la plus part de nos conjectures précédentes.
A simple recurrence formula for the number of rooted maps on surfaces by edges and genus
Authors: Carrell Sean , Chapuy Guillaume
Published: August 2021

We establish a simple recurrence formula for the number $Q_g^n$ of rooted orientable maps counted by edges and genus. The formula is a consequence of the KP equation for the generating function of bipartite maps, coupled with a Tutte equation, and it was apparently unnoticed before. It gives by far the fastest known way of computing these numbers, or the fixed-genus generating functions, especially for large $g$. The formula is similar in look to the one discovered by Goulden and Jackson for triangulations (although the latter does not rely on an additional Tutte equation). Both of them have a very combinatorial flavour, but finding a bijective interpretation is currently unsolved - should such an interpretation exist, the history of bijective methods for maps would tend to show that the case treated here is easier to start with than the one of triangulations.

Nous établissons une formule de récurrence simple pour le nombre $Q_g^n$ de cartes enracinées de genre $g$ à $n$ arêtes. Cette formule est une conséquence relativement simple du fait que la série génératrice des cartes biparties est une solution de l’équation KP et d’une équation de Tutte, et elle était apparemment passée inaperçue jusque là. Elle donne de loin le moyen le plus rapide pour calculer ces nombres, en particulier quand $g$est grand. La formule est d’apparence similaire à celle découverte par Goulden et Jackson pour les triangulations (quoique cette dernière ne repose pas sur une équation de Tutte additionnelle). Les deux formules ont une saveur très combinatoire, mais trouver une interprétation bijective reste un problème ouvert – mais si une telle interprétation existe, l’histoire des méthodes bijectives pour les cartes tendrait à montrer que le cas traité ici est plus facile pour commencer que celui des triangulations.
The order of birational rowmotion
Authors: Grinberg Darij , Roby Tom
Published: August 2021

Various authors have studied a natural operation (under various names) on the order ideals (equivalently antichains) of a finite poset, here called \emphrowmotion. For certain posets of interest, the order of this map is much smaller than one would naively expect, and the orbits exhibit unexpected properties. In very recent work (inspired by discussions with Berenstein) Einstein and Propp describe how rowmotion can be generalized: first to the piecewise-linear setting of order polytopes, then via detropicalization to the birational setting. In the latter setting, it is no longer \empha priori clear even that birational rowmotion has finite order, and for many posets the order is infinite. However, we are able to show that birational rowmotion has the same order, p+q, for the poset P=[p]×[q] (product of two chains), as ordinary rowmotion. We also show that birational (hence ordinary) rowmotion has finite order for some other classes of posets, e.g., the upper, lower, right and left halves of the poset above, and trees having all leaves on the same level. Our methods are based on those used by Volkov to resolve the type AA (rectangular) Zamolodchikov Periodicity Conjecture.