bluuebunny/crossref_metadata_2025_split huggingface dataset:
Uniquely monopolar-partitionable block graphs
Authors: Chen Xuegang , Huang Jing 
Published: August 2021

Special issue PRIMA 2013
As a common generalization of bipartite and split graphs, monopolar graphs are defined in terms of the existence of certain vertex partitions. It has been shown that to determine whether a graph has such a partition is NP-complete for general graphs and polynomial for several classes of graphs. In this paper, we investigate graphs that admit a unique such partition and call them uniquely monopolar-partitionable graphs. By employing a tree trimming technique, we obtain a characterization of uniquely monopolar-partitionable block graphs. Our characterization implies a polynomial time algorithm for recognizing them.
Generalized dynamic storage allocation
Authors: Kierstead H. A. , Saoub Karin R. 
Published: August 2021

Graph Theory
Dynamic Storage Allocation is a problem concerned with storing items that each have weight and time restrictions. Approximate algorithms have been constructed through online coloring of interval graphs. We present a generalization that uses online coloring of tolerance graphs. We utilize online-with-representation algorithms on tolerance graphs, which are online algorithms in which the corresponding tolerance representation of a vertex is also presented. We find linear bounds for the online-with-representation chromatic number of various classes of tolerance graphs and apply these results to a generalization of Dynamic Storage Allocation, giving us a polynomial time approximation algorithm with linear performance ratio.
A four-sweep LBFS recognition algorithm for interval graphs
Authors: Li Peng , Wu Yaokun 
Published: August 2021

Graph Theory
In their 2009 paper, Corneil et al. design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to the LBFS structure theory established mainly by Corneil et al., we are able to present a 4-sweep LBFS algorithm which determines whether or not the input graph is a unit interval graph or an interval graph. Like the algorithm of Corneil et al., our algorithm does not involve any complicated data structure and can be executed in linear time.
Parameterized complexity of synchronization and road coloring
Authors: Vorel Vojtěch , Roman Adam 
Published: August 2021

Automata, Logic and Semantics
First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.
On substitution tilings of the plane with n-fold rotational symmetry
Authors: Maloney Gregory R. 
Published: August 2021

Discrete Algorithms
A method is described for constructing, with computer assistance, planar substitution tilings that have n-fold rotational symmetry. This method uses as prototiles the set of rhombs with angles that are integer multiples of pi/n, and includes various special cases that have already been constructed by hand for low values of n. An example constructed by this method for n = 11 is exhibited; this is the first substitution tiling with elevenfold symmetry appearing in the literature.
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.
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.
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.
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$.
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.
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.