bluuebunny/crossref_metadata_2025 huggingface dataset:
Evaluation of a Special Hankel Determinant of Binomial Coefficients
Authors: Eugeciouglu Ömer , Redmond Timothy , Ryavec Charles
Published: August 2021

This paper makes use of the recently introduced technique of $\gamma$-operators to evaluate the Hankel determinant with binomial coefficient entries $a_k = (3 k)! / (2k)! k!$. We actually evaluate the determinant of a class of polynomials $a_k(x)$ having this binomial coefficient as constant term. The evaluation in the polynomial case is as an almost product, i.e. as a sum of a small number of products. The $\gamma$-operator technique to find the explicit form of the almost product relies on differential-convolution equations and establishes a second order differential equation for the determinant. In addition to $x=0$, product form evaluations for $x = \frac{3}{5}, \frac{3}{4}, \frac{3}{2}, 3$ are also presented. At $x=1$, we obtain another almost product evaluation for the Hankel determinant with $a_k = ( 3 k+1) ! / (2k+1)!k!$.
An extremal problem on potentially K_p,1,1-graphic sequences
Authors: Lai Chunhui
Published: August 2021

A sequence S is potentially K_p,1,1 graphical if it has a realization containing a K_p,1,1 as a subgraph, where K_p,1,1 is a complete 3-partite graph with partition sizes p,1,1. Let σ (K_p,1,1, n) denote the smallest degree sum such that every n-term graphical sequence S with σ (S)≥ σ (K_p,1,1, n) is potentially K_p,1,1 graphical. In this paper, we prove that σ (K_p,1,1, n)≥ 2[((p+1)(n-1)+2)/2] for n ≥ p+2. We conjecture that equality holds for n ≥ 2p+4. We prove that this conjecture is true for p = 3. AMS Subject Classifications: 05C07, 05C35
Algebraic Elimination of epsilon-transitions
Authors: Duchamp Gérard , Kacem Hatem Hadj , Laugerotte Eric
Published: August 2021

We present here algebraic formulas associating a k-automaton to a k-epsilon-automaton. The existence depends on the definition of the star of matrices and of elements in the semiring k. For this reason, we present the theorem which allows the transformation of k-epsilon-automata into k-automata. The two automata have the same behaviour.
A Note on the Transience of Critical Branching Random Walks on the Line
Authors: Alsmeyer Gerold , Meiners Matthias
Published: August 2021

Gantert and Müller (2006) proved that a critical branching random walk (BRW) on the integer lattice is transient by analyzing this problem within the more general framework of branching Markov chains and making use of Lyapunov functions. The main purpose of this note is to show how the same result can be derived quite elegantly and even extended to the nonlattice case within the theory of weighted branching processes. This is done by an analysis of certain associated random weighted location measures which, upon taking expectations, provide a useful connection to the well established theory of ordinary random walks with i.i.d. increments. A brief discussion of the asymptotic behavior of the left- and rightmost particles in a critical BRW as time goes to infinity is provided in the final section by drawing on recent work by Hu and Shi (2008).
A note on the fragmentation of a stable tree
Authors: Marchal Philippe
Published: August 2021

We introduce a recursive algorithm generating random trees, which we identify as skeletons of a continuous, stable tree. We deduce a representation of a fragmentation process on these trees.
The size of random fragmentation intervals
Authors: Aguech Rafik
Published: August 2021

Two processes of random fragmentation of an interval are investigated. For each of them, there is a splitting probability at each step of the fragmentation process whose overall effect is to stabilize the global number of splitting events. More precisely, we consider two models. In the first model, the fragmentation stops which a probability $p$ witch can not depend on the fragment size. The number of stable fragments with sizes less than a given $t \geq 0$, denoted by $K(t)$, is introduced and studied. In the second one the probability to split a fragment of size $x$ is $p(x)=1-e^{-x}$. For this model we utilize the contraction method to show that the distribution of a suitably normalized version of the number of stable fragments converges in law. It's shown that the limit is the fixed-point solution (in the Wasserstein space) to a distributional equation. An explicit solution to the fixed-point equation is easily verified to be Gaussian.
A bijective proof of a factorization formula for Macdonald polynomials at roots of unity
Authors: Descouens F. , Morita H. , Numata Y.
Published: August 2021

We give a combinatorial proof of the factorization formula of modified Macdonald polynomials $\widetilde{H}_{\lambda} (X;q,t)$ when $t$ is specialized at a primitive root of unity. Our proof is restricted to the special case where $\lambda$ is a two columns partition. We mainly use the combinatorial interpretation of Haiman, Haglund and Loehr giving the expansion of $\widetilde{H}_{\lambda} (X;q,t)$ on the monomial basis.

Nous présentons une preuve combinatoire de la formule de factorisation des polynômes de Macdonald modifiés $\widetilde{H}_{\lambda} (X;q,t)$ quand $t$ est spécialisé à une racine primitive de l'unité. Notre preuve se restreint au cas particulier des partitions $\lambda$ n'ayant que deux colonnes. On utilise principalement l'interprétation combinatoire de Haglund, Haiman and Loehr donnant le développement de $\widetilde{H}_{\lambda} (X;q,t)$ sur la base des fonctions monomiales.
Delannoy numbers and Legendre polytopes
Authors: Hetyei Gábor
Published: August 2021

We construct an $n$-dimensional polytope whose boundary complex is compressed and whose face numbers for any pulling triangulation are the coefficients of the powers of $(x-1)/2$ in the $n$-th Legendre polynomial. We show that the non-central Delannoy numbers count all faces in the lexicographic pulling triangulation that contain a point in a given open quadrant. We thus provide a geometric interpretation of a relation between the central Delannoy numbers and Legendre polynomials, observed over 50 years ago. The polytopes we construct are closely related to the root polytopes introduced by Gelfand, Graev, and Postnikov. \par

No construisons un polytope de dimension $n$ dont le complexe de bord est comprimé et dont les nombres de faces dans toute triangulation "en tirant des sommets'' sont les coefficients des puissances de $(x-1)/2$ dans le $n$-ième polynôme de Legendre. Nous montrons que les nombres centraux de Delannoy comptent toutes les faces dans la triangulation "en tirant des sommets'' en ordre lexicographique qui contiennent un point dans un certain quadrant ouvert. Ainsi nous produisons une interprétation géométrique d'une relation entre les nombres de Delannoy centraux et les polynômes de Legendre, notée il y a 50 ans. Nos polytopes sont reliés intimement aux polytopes de racines introduits par Gelfand, Graev, et Postnikov.
Invariants in Non-Commutative Variables of the Symmetric and Hyperoctahedral Groups
Authors: Bergeron-Brlek Anouk
Published: August 2021

We consider the graded Hopf algebra $NCSym$ of symmetric functions with non-commutative variables, which is analogous to the algebra $Sym$ of the ordinary symmetric functions in commutative variables. We give formulaes for the product and coproduct on some of the analogues of the $Sym$ bases and expressions for a shuffle product on $NCSym$. We also consider the invariants of the hyperoctahedral group in the non-commutative case and a state a few results.

Nous considérons l'algèbre de Hopf graduée $NCSym$ des fonctions symétriques en variables non-commutatives, qui est analogue à l'algèbre $Sym$ des fonctions symétriques en variables commutatives. Nous donnons des formules pour le produit et coproduit sur certaines des bases analogues à celles de $Sym$, ainsi qu'une expression pour le produit $\textit{shuffle}$ sur $NCSym$. Nous considérons aussi les invariants du groupe hyperoctaédral dans le cas non-commutatif et énonçons quelques résultats.
Partitioned Cacti: a Bijective Approach to the Cycle Factorization Problem
Authors: Schaeffer Gilles , Vassilieva Ekaterina
Published: August 2021

In this paper we construct a bijection for partitioned 3-cacti that gives raise to a new formula for enumeration of factorizations of the long cycle into three permutations with given number of cycles.

Dans cet article, nous construisons une bijection pour 3-cacti partitionnés faisant apparaître une nouvelle formule pour l’énumération des factorisations d’un long cycle en trois permutations ayant un nombre donné de cycles.
Combinatorial properties of permutation tableaux
Authors: Burstein Alexander , Eriksen Niklas
Published: August 2021

We give another construction of a permutation tableau from its corresponding permutation and construct a permutation-preserving bijection between $1$-hinge and $0$-hinge tableaux. We also consider certain alignment and crossing statistics on permutation tableaux that have previously been shown to be equidistributed by mapping them to patterns in related permutations. We give two direct maps on tableaux that prove the equidistribution of those statistics by exchanging some statistics and preserving the rest. Finally, we enumerate some sets of permutations that are restricted both by pattern avoidance and by certain parameters of their associated permutation tableaux.

Nous donnons une nouvelle construction d'un tableau de permutation à partir de la permutation correspondante. Nous construisons ensuite une permutation qui préserve la bijection entre un tableau charnière $1$ et tableau charnière $0$. Nous considérons également certaines statistiques sur les alignements et croisements dans les tableaux de permutations. L'équidistribution de ces données statistiques est connue, et donnée par le biais d'une application très compliquée associant les alignements et croisements des tableaux a des motifs des permutations correspondantes. Nous construisons deux involutions définies sur les tableaux qui démontrent l'équidistribution des statistiques en échangeant certaines données tout en préservant d'autres. Enfin, nous dénombrons quelques ensembles de permutations définis non seulement par l'absence de certains motifs mais aussi par certains paramètres issus des tableaux de permutations.
On Plücker coordinates of a perfectly oriented planar network
Authors: Talaska Kelli
Published: August 2021

Let $G$ be a perfectly oriented planar graph. Postnikov's boundary measurement construction provides a rational map from the set of positive weight functions on the edges of $G$ onto the appropriate totally nonnegative Grassmann cell. We establish an explicit combinatorial formula for Postnikov's map by expressing each Plücker coordinate of the image as a ratio of two polynomials in the edge weights, with positive integer coefficients. These polynomials are weight generating functions for certain subsets of edges in $G$.
Chip-Firing and Rotor-Routing on $\mathbb{Z}^d$ and on Trees
Authors: Landau Itamar , Levine Lionel , Peres Yuval
Published: August 2021

The sandpile group of a graph $G$ is an abelian group whose order is the number of spanning trees of $G$. We find the decomposition of the sandpile group into cyclic subgroups when $G$ is a regular tree with the leaves are collapsed to a single vertex. This result can be used to understand the behavior of the rotor-router model, a deterministic analogue of random walk studied first by physicists and more recently rediscovered by combinatorialists. Several years ago, Jim Propp simulated a simple process called rotor-router aggregation and found that it produces a near perfect disk in the integer lattice $\mathbb{Z}^2$. We prove that this shape is close to circular, although it remains a challenge to explain the near perfect circularity produced by simulations. In the regular tree, we use the sandpile group to prove that rotor-router aggregation started from an acyclic initial condition yields a perfect ball.
The complexity of computing Kronecker coefficients
Authors: Bürgisser Peter , Ikenmeyer Christian
Published: August 2021

Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem $\mathrm{KRONCOEFF}$ of computing Kronecker coefficients is very difficult. More specifically, we prove that $\mathrm{KRONCOEFF}$ is #$\mathrm{P}$-hard and contained in the complexity class $\mathrm{GapP}$. Formally, this means that the existence of a polynomial time algorithm for $\mathrm{KRONCOEFF}$ is equivalent to the existence of a polynomial time algorithm for evaluating permanents.

Les coefficients de Kronecker sont les multiplicités dans la décomposition du produit tensoriel de deux représentations irréductibles du groupe symétrique. On peut aussi les voir comme les coefficients du développement du produit interne des polynômes de Schur. Nous montrons que le problème $\mathrm{KRONCOEFF}$ de calculer les coefficients de Kronecker est très difficile. Plus précisément, nous prouvons que $\mathrm{KRONCOEFF}$ est #$\mathrm{P}$-dur et que $\mathrm{KRONCOEFF}$ est dans la classe de complexité $\mathrm{GapP}$. Cela veut dire qu'il existe un algorithme pour $\mathrm{KRONCOEFF}$ s'exécutant en temps polynomial si et seulement s'il existe un algorithme pour l'évaluation du permanent s'exécutant en temps polynomial.
Affine and toric arrangements
Authors: Ehrenborg Richard , Readdy Margaret , Slone Michael
Published: August 2021

We extend the Billera―Ehrenborg―Readdy map between the intersection lattice and face lattice of a central hyperplane arrangement to affine and toric hyperplane arrangements. For toric arrangements, we also generalize Zaslavsky's fundamental results on the number of regions.

Nous étendons l'opérateur de Billera―Ehrenborg―Readdy entre le trellis d'intersection et la treillis de faces d'un arrangement hyperplans centraux aux arrangements affines et toriques. Pour les arrangements toriques, nous généralisons aussi les résultats fondamentaux de Zaslavsky sur le nombre de régions.
Total positivity for cominuscule Grassmannians
Authors: Lam Thomas , Williams Lauren
Published: August 2021

In this paper we explore the combinatorics of the non-negative part $(G/P)_{\geq 0}$ of a cominuscule Grassmannian. For each such Grassmannian we define Le-diagrams ― certain fillings of generalized Young diagrams which are in bijection with the cells of $(G/P)_{\geq 0}$. In the classical cases, we describe Le-diagrams explicitly in terms of pattern avoidance. We also define a game on diagrams, by which one can reduce an arbitrary diagram to a Le-diagram. We give enumerative results and relate our Le-diagrams to other combinatorial objects. Surprisingly, the totally non-negative cells in the open Schubert cell of the odd and even orthogonal Grassmannians are (essentially) in bijection with preference functions and atomic preference functions respectively.

Dans cet article nous schtroumpfons la combinatoire de la partie non-négative $(G/P)_{\geq 0}$ d'une Grassmannienne cominuscule. Pour chaque Grassmannienne de ce type nous définissons les Le-diagrammes ― certains remplissages de diagrammes de Young généralisés en bijection avec les cellules de $(G/P)_{\geq 0}$. Dans les cas classiques, nous décrivons les Le-diagrammes explicitement en termes d'évitement de certains motifs. Aussi nous définissons un jeu sur les diagrammes, avec lequel on peut réduire un diagramme arbitraire à un Le-diagramme. Nous donnons les résultats énumératifs et nous relions nos Le-diagrammes à d'autres objets combinatoires. Étonnamment, les cellules non-négatives dans la cellule de Schubert ouverte des Grassmanniennes orthogonales impaires et paires sont essentiellement en bijection avec les fonctions de préférence et les fonctions de préférence atomiques.
$q,t$-Fuß-Catalan numbers for complex reflection groups
Authors: Stump Christian
Published: August 2021

In type $A$, the $q,t$-Fuß-Catalan numbers $\mathrm{Cat}_n^{(m)}(q,t)$ can be defined as a bigraded Hilbert series of a module associated to the symmetric group $\mathcal{S}_n$. We generalize this construction to (finite) complex reflection groups and exhibit some nice conjectured algebraic and combinatorial properties of these polynomials in $q$ and $t$. Finally, we present an idea how these polynomials could be related to some graded Hilbert series of modules arising in the context of rational Cherednik algebras. This is work in progress.

Dans le cas du type $A$, les $q,t$-nombres de Fuß-Catalan $\mathrm{Cat}_n^{(m)}(q,t)$ peuvent être définis comme la série de Hilbert bigraduée d'un certain module associé au groupe symétrique $\mathcal{S}_n$. Nous généralisons cette construction aux groupes de réflexion complexes (finis) et nous formulons de jolies propriétés (conjecturales) algébriques et combinatoires de ces polynômes en $q$ et $t$. Enfin, nous décrivons une idée sur la manière dont ces polynômes pourraient être liés à certaines séries de Hilbert de modules apparaissant dans le contexte des algèbres de Cherednik rationnelles. Ceci est un travail en cours.
Multi-triangulations as complexes of star polygons
Authors: Pilaud Vincent , Santos Francisco
Published: August 2021

A $k$-triangulation of a convex polygon is a maximal set of diagonals so that no $k+1$ of them mutually cross. $k$-triangulations have received attention in recent literature, with motivation coming from several interpretations of them. We present a new way of looking at $k$-triangulations, where certain star polygons naturally generalize triangles for $k$-triangulations. With this tool we give new, direct proofs of the fundamental properties of $k$-triangulations (number of edges, definition of flip). This interpretation also opens up new avenues of research that we briefly explore in the last section.

Une $k$-triangulation d'un polygone convexe est un ensemble maximal de diagonales ne contenant pas $k+1$ arêtes qui se croisent deux à deux. Les $k$-triangulations ont été récemment étudiées sous divers aspects dans la littérature. On présente ici un nouveau point de vue sur les $k$-triangulations, en introduisant certains polygones étoilés comme généralisation des triangles pour les $k$-triangulations. En utilisant ce nouvel outil, on donne des preuves directes des propriétés fondamentales des $k$-triangulations (nombre d'arêtes, définition du flip). Notre point de vue ouvre par ailleurs de nouveaux horizons de recherche que l'on présente rapidement dans la dernière partie.
$n$-color overpartitions, lattice paths, and multiple basic hypergeometric series
Authors: Mallet Olivier
Published: August 2021

We define two classes of multiple basic hypergeometric series $V_{k,t}(a,q)$ and $W_{k,t}(a,q)$ which generalize multiple series studied by Agarwal, Andrews, and Bressoud. We show how to interpret these series as generating functions for special restricted lattice paths and for $n$-color overpartitions with weighted difference conditions. We also point out that some specializations of our series can be written as infinite products, which leads to combinatorial identities linking $n$-color overpartitions with ordinary partitions or overpartitions.

Nous définissons deux classes de séries hypergéométriques basiques multiples $V_{k,t}(a,q)$ et $W_{k,t}(a,q)$ qui généralisent des séries multiples étudiées par Agarwal, Andrews et Bressoud. Nous montrons comment interpréter ces séries comme les fonctions génératrices de chemins avec certaines restrictions et de surpartitions $n$-colorées vérifiant des conditions de différences pondérées. Nous remarquons aussi que certaines spécialisations de nos séries peuvent s'écrire comme des produits infinis, ce qui conduit à des identités combinatoires reliant les surpartitions $n$-colorées aux partitions ou surpartitions ordinaires.
Deodhar Elements in Kazhdan-Lusztig Theory
Authors: Jones Brant
Published: August 2021

The Kazhdan-Lusztig polynomials for finite Weyl groups arise in representation theory as well as the geometry of Schubert varieties. It was proved very soon after their introduction that they have nonnegative integer coefficients, but no simple all positive interpretation for them is known in general. Deodhar has given a framework, which generally involves recursion, to express the Kazhdan-Lusztig polynomials in a very attractive form. We use a new kind of pattern-avoidance that can be defined for general Coxeter groups to characterize when Deodhar's algorithm yields a non-recursive combinatorial formula for Kazhdan-Lusztig polynomials $P_{x,w}(q)$ of finite Weyl groups. This generalizes results of Billey-Warrington which identified the $321$-hexagon-avoiding permutations, and Fan-Green which identified the fully-tight Coxeter groups. We also show that the leading coefficient known as $\mu (x,w)$ for these Kazhdan―Lusztig polynomials is always either $0$ or $1$. Finally, we generalize the simple combinatorial formula for the Kazhdan―Lusztig polynomials of the $321$-hexagon-avoiding permutations to the case when $w$ is hexagon avoiding and maximally clustered.

Les polynômes de Kazhdan-Lusztig $P_{x,w}(q)$ des groupes de Weyl finis apparaissent en théorie des représentations, ainsi qu’en géométrie des variétés de Schubert. Il a été démontré peu après leur introduction qu’ils avaient des coefficients entiers positifs, mais on ne connaît toujours pas d’interprétation combinatoire simple de cette propriété dans le cas général. Deodhar a proposé un cadre donnant un algorithme, en général récursif, calculant des formules attractives pour les polynômes de Kazhdan-Lusztig. Billey-Warrington ont démontré que cet algorithme est non récursif lorsque$w$ évite les hexagones et les $321$ et qu’il donne des formules combinatoires simples. Nous introduisons une notion d’évitement de schémas dansles groupes de Coxeter quelconques nous permettant de généraliser les résultats de Billey-Warrington à tout groupe de Weyl fini. Nous montrons que le coefficient de tête $\mu (x,w)$ de ces polynômes de Kazhdan-Lusztig est toujours $0$ ou $1$. Cela généralise aussi des résultats de Fan-Greenqui identifient les groupes de Coxeter complètement serrés. Enfin, en type $A$, nous obtenons une classe plus large de permutations évitant la récursion.
Enumeration of orientable coverings of a non-orientable manifold
Authors: Kwak Jin Ho , Mednykh Alexander , Nedela Roman
Published: August 2021

In this paper we solve the known V.A. Liskovets problem (1996) on the enumeration of orientable coverings over a non-orientable manifold with an arbitrary finitely generated fundamental group. As an application we obtain general formulas for the number of chiral and reflexible coverings over the manifold. As a further application, we count the chiral and reflexible maps and hypermaps on a closed orientable surface by the number of edges. Also, by this method the number of self-dual and Petri-dual maps can be determined. This will be done in forthcoming papers by authors.
New combinatorial computational methods arising from pseudo-singletons
Authors: Labelle Gilbert
Published: August 2021

Since singletons are the connected sets, the species $X$ of singletons can be considered as the combinatorial logarithm of the species $E(X)$ of finite sets. In a previous work, we introduced the (rational) species $\widehat{X}$ of pseudo-singletons as the analytical logarithm of the species of finite sets. It follows that $E(X) = \exp (\widehat{X})$ in the context of rational species, where $\exp (T)$ denotes the classical analytical power series for the exponential function in the variable $T$. In the present work, we use the species $\widehat{X}$ to create new efficient recursive schemes for the computation of molecular expansions of species of rooted trees, of species of assemblies of structures, of the combinatorial logarithm species, of species of connected structures, and of species of structures with weighted connected components.

Puisque les singletons sont les ensembles connexes, l'espèce $X$ des singletons peut être considérée comme le logarithme combinatoire de l'espèce $E(X)$ des ensembles finis. Dans un travail antérieur, nous avons introduit l'espèce (rationnelle) $\widehat{X}$ des pseudo-singletons comme étant le logarithme analytique de l'espèce des ensembles finis. Il en découle que $E(X) = \exp (\widehat{X})$ dans le contexte des espèces rationnelles, où $\exp (T)$ désigne la série de puissances analytique classique de la fonction exponentielle dans la variable $T$. Dans le présent travail, nous utilisons l'espèce $\widehat{X}$ pour créer de nouveaux schémas computationnels récursifs efficaces pour le calcul du développement moléculaire de l'espèce des arborescences, d'espèces d'assemblées de structures, de l'espèce du logarithme combinatoire, d'espèces de structures connexes, et d'espèces de structures à composantes connexes pondérées.
P6- and triangle-free graphs revisited: structure and bounded clique-width
Authors: Brandstädt Andreas , Klembt Tilo , Mahfud Suhail
Published: August 2021

The Maximum Weight Stable Set (MWS) Problem is one of the fundamental problems on graphs. It is well-known to be NP-complete for triangle-free graphs, and Mosca has shown that it is solvable in polynomial time when restricted to P6- and triangle-free graphs. We give a complete structure analysis of (nonbipartite) P6- and triangle-free graphs which are prime in the sense of modular decomposition. It turns out that the structure of these graphs is extremely simple implying bounded clique-width and thus, efficient algorithms exist for all problems expressible in terms of Monadic Second Order Logic with quantification only over vertex predicates. The problems Vertex Cover, MWS, Maximum Clique, Minimum Dominating Set, Steiner Tree, and Maximum Induced Matching are among them. Our results improve the previous one on the MWS problem by Mosca with respect to structure and time bound but also extends a previous result by Fouquet, Giakoumakis and Vanherpe which have shown that bipartite P6-free graphs have bounded clique-width. Moreover, it covers a result by Randerath, Schiermeyer and Tewes on polynomial time 3-colorability of P6- and triangle-free graphs.
A Cartesian closed category of event structures with quotients
Authors: Abbes Samy
Published: August 2021

We introduce a new class of morphisms for event structures. The category obtained is cartesian closed, and a natural notion of quotient event structure is defined within it. We study in particular the topological space of maximal configurations of quotient event structures. We introduce the compression of event structures as an example of quotient: the compression of an event structure E is a minimal event structure with the same space of maximal configurations as E.
d-records in geometrically distributed random variables
Authors: Prodinger Helmut
Published: August 2021

We study d-records in sequences generated by independent geometric random variables and derive explicit and asymptotic formulæ for expectation and variance. Informally speaking, a d-record occurs, when one computes the d-largest values, and the variable maintaining it changes its value while the sequence is scanned from left to right. This is done for the "strict model," but a "weak model" is also briefly investigated. We also discuss the limit q → 1 (q the parameter of the geometric distribution), which leads to the model of random permutations.
NONCOMMUTATIVE SYMMETRIC FUNCTIONS ASSOCIATED WITH A CODE, LAZARD ELIMINATION, AND WITT VECTORS
Authors: Luque Jean-Gabriel , Thibon Jean-Yves
Published: August 2021

The construction of the universal ring of Witt vectors is related to Lazard's factorizations of free monoids by means of a noncommutative analogue. This is done by associating to a code a specialization of noncommutative symmetric functions.
On the complexity of the balanced vertex ordering problem
Authors: Kára Jan , Kratochvil Jan , Wood David R.
Published: August 2021

Graphs and Algorithms

We consider the problem of finding a balanced ordering of the vertices of a graph. More precisely, we want to minimise the sum, taken over all vertices v, of the difference between the number of neighbours to the left and right of v. This problem, which has applications in graph drawing, was recently introduced by Biedl et al. [Discrete Applied Math. 148:27―48, 2005]. They proved that the problem is solvable in polynomial time for graphs with maximum degree three, but NP-hard for graphs with maximum degree six. One of our main results is to close the gap in these results, by proving NP-hardness for graphs with maximum degree four. Furthermore, we prove that the problem remains NP-hard for planar graphs with maximum degree four and for 5-regular graphs. On the other hand, we introduce a polynomial time algorithm that determines whetherthere is a vertex ordering with total imbalance smaller than a fixed constant, and a polynomial time algorithm that determines whether a given multigraph with even degrees has an 'almost balanced' ordering.
Approximation and inapproximability results on balanced connected partitions of graphs
Authors: Chataigner Frédéric , Salgado Liliane R. B. , Wakabayashi Yoshiko
Published: August 2021

Graphs and Algorithms

Let G=(V,E) be a connected graph with a weight function w: V \to \mathbbZ₊, and let q ≥q 2 be a positive integer. For X⊆ V, let w(X) denote the sum of the weights of the vertices in X. We consider the following problem on G: find a q-partition P=(V₁,V₂, \ldots, V_q) of V such that G[V_i] is connected (1≤q i≤q q) and P maximizes \rm min\w(V_i): 1≤q i≤q q\. This problem is called \textitMax Balanced Connected q-Partition and is denoted by BCP_q. We show that for q≥q 2 the problem BCP_q is NP-hard in the strong sense, even on q-connected graphs, and therefore does not admit a FPTAS, unless \rm P=\rm NP. We also show another inapproximability result for BCP₂ on arbitrary graphs. On q-connected graphs, for q=2 the best result is a \frac43-approximation algorithm obtained by Chleb\'ıková; for q=3 and q=4 we present 2-approximation algorithms. When q is not fixed (it is part of the instance), the corresponding problem is called \textitMax Balanced Connected Partition, and denoted as BCP. We show that BCP does not admit an approximation algorithm with ratio smaller than 6/5, unless \rm P=\rm NP.
Note on the weighted internal path length of b-ary trees
Authors: Rüschendorf Ludger , Schopp Eva-Maria
Published: August 2021

Analysis of Algorithms

In a recent paper Broutin and Devroye (2005) have studied the height of a class of edge-weighted random trees.This is a class of trees growing in continuous time which includes many wellknown trees as examples. In this paper we derive a limit theorem for the internal path length for this class of trees.For the proof we extend a limit theorem in Neininger and Rüschendorf (2004) to recursive sequences of random variables with continuous time parameter.
Words and bisimulations of dynamical systems
Authors: Brihaye Thomas
Published: August 2021

In this paper we study bisimulations on dynamical systems through a given partition. Our aim is to give a new vision of the notion of bisimulation by using words. To achieve this goal, we encode the trajectories of the transition system as words. This method was introduced in our paper ''On o-minimal hybrid systems'' in order to give a new proof of the existence of a finite bisimulation for o-minimal hybrid systems (as previously proved in a paper by Lafferriere G., Pappas G.J. and Sastry S.). Here we want to provide a systematic study of this method in order to obtain a procedure for building finite bisimulations based on words.
Regular languages and associative language descriptions
Authors: Anselmo Marcella , Cherubini Alessandra , San Pietro Pierluigi
Published: August 2021

The Associative Language Description model (ALD) is a combination of locally testable and constituent structure ideas. It is consistent with current views on brain organization and can rather conveniently describe typical technical languages such as Pascal or HTML. ALD languages are strictly enclosed in context-free languages but in practice the ALD model equals CF grammars in explanatory adequacy. Various properties of ALD have been investigated, but many theoretical questions are still open. For instance, it is unknown, at the present, whether the ALD family includes the regular languages. Here it is proved that several known classes of regular languages are ALD: threshold locally testable languages, group languages, positive commutative languages and commutative languages on 2-letter alphabets. Moreover, we show that there is an ALD language in each level of (restricted) star height hierarchy. These results seem to show that ALD languages are well-distributed over the class of regular languages.
On the kth Eigenvalues of Trees with Perfect Matchings
Authors: Chang An , Shiu Wai Chee
Published: August 2021

Graphs and Algorithms

Résumé comportant des formules mathématiques, disponible sur le ficher pdf / Abstract with mathematical formulas, available on pdf file.
Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
Authors: Kheddouci Hamamache , Togni Olivier
Published: August 2021

Graphs and Algorithms

For a set D ⊂ Zn, the distance graph Pn(D) has Zn as its vertex set and the edges are between vertices i and j with |i − j| ∈ D. The circulant graph Cn(D) is defined analogously by considering operations modulo n. The minimum feedback vertex set problem consists in finding the smallest number of vertices to be removed in order to cut all cycles in the graph. This paper studies the minimum feedback vertex set problem for some families of distance graphs and circulant graphs depending on the value of D.
On-line Ramsey numbers for paths and stars
Authors: Grytczuk J. A. , Kierstead H. A. , Prałat P.
Published: August 2021

Graphs and Algorithms

We study on-line version of size-Ramsey numbers of graphs deﬁned via a game played between Builder and Painter: in one round Builder joins two vertices by an edge and Painter paints it red or blue. The goal of Builder is to force Painter to create a monochromatic copy of a ﬁxed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number r(H) of the graph H. We determine exact values of r(H) for a few short paths and obtain a general upper bound r(Pn) ≤ 4n −7. We also study asymmetric version of this parameter when one of the target graphs is a star Sn with n edges. We prove that r(Sn, H) ≤ n*e(H) when H is any tree, cycle or clique
Culminating paths
Authors: Bousquet-Mélou Mireille , Ponty Yann
Published: August 2021

Let a and b be two positive integers. A culminating path is a path of Z^2 that starts from (0,0), consists of steps (1,a) and (1,-b), stays above the x-axis and ends at the highest ordinate it ever reaches. These paths were first encountered in bioinformatics, in the analysis of similarity search algorithms. They are also related to certain models of Lorentzian gravity in theoretical physics. We first show that the language on a two letter alphabet that naturally encodes culminating paths is not context-free. Then, we focus on the enumeration of culminating paths. A step by step approach, combined with the kernel method, provides a closed form expression for the generating fucntion of culminating paths ending at a (generic) height k. In the case a=b, we derive from this expression the asymptotic behaviour of the number of culminating paths of length n. When a>b, we obtain the asymptotic behaviour by a simpler argument. When a= b, with no precomputation stage nor non-linear storage required. The choice of the best algorithm is not as clear when a
The Laplacian spread of a tree
Authors: Fan Yi-Zheng , Xu Jing , Wang Yi , Liang Dong
Published: August 2021

Graphs and Algorithms

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In this paper, we show that the star is the unique tree with maximal Laplacian spread among all trees of given order, and the path is the unique one with minimal Laplacian spread among all trees of given order.
Spanning forests on the Sierpinski gasket
Authors: Chang Shu-Chiuan , Chen Lung-Chi
Published: August 2021

Combinatorics

We study the number of spanning forests on the Sierpinski gasket SGd(n) at stage n with dimension d equal to two, three and four, and determine the asymptotic behaviors. The corresponding results on the generalized Sierpinski gasket SGd;b(n) with d = 2 and b = 3 ; 4 are obtained. We also derive upper bounds for the asymptotic growth constants for both SGd and SG2,b.
Multidimensional cellular automata and generalization of Fekete's lemma
Authors: Capobianco Silvio
Published: August 2021

Automata, Logic and Semantics

Fekete's lemma is a well-known combinatorial result on number sequences: we extend it to functions defined on d-tuples of integers. As an application of the new variant, we show that nonsurjective d-dimensional cellular automata are characterized by loss of arbitrarily much information on finite supports, at a growth rate greater than that of the support's boundary determined by the automaton's neighbourhood index.
On economical set representations of graphs
Authors: Kong Jing , Wu Yaokun
Published: August 2021

Graphs and Algorithms

In this paper we discuss the bounds of and relations among various kinds of intersection numbers of graphs. Especially, we address extremal graphs with respect to the established bounds. The uniqueness of the minimum-size intersection representations for some graphs is also studied. In the course of this work, we introduce a superclass of chordal graphs, defined in terms of a generalization of simplicial vertex and perfect elimination ordering.
Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
Authors: Bacsó Gábor , Tuza Zsolt
Published: August 2021

Graphs and Algorithms

A clique-transversal set in a graph is a subset of the vertices that meets all maximal complete subgraphs on at least two vertices. We prove that every connected graph of order n and maximum degree three has a clique-transversal set of size left perpendicular19n/30 + 2/15right perpendicular. This bound is tight, since 19n/30 - 1/15 is a lower bound for infinitely many values of n. We also prove that the vertex set of any connected claw-free graph of maximum degree at most four, other than an odd cycle longer than three, can be partitioned into two clique-transversal sets. The proofs of both results yield polynomial-time algorithms that find corresponding solutions.
The distribution of ascents of size d or more in compositions
Authors: Brennan Charlotte , Knopfmacher Arnold
Published: August 2021

Combinatorics

A composition of a positive integer n is a finite sequence of positive integers a(1), a(2), ..., a(k) such that a(1) + a(2) + ... + a(k) = n. Let d be a fixed nonnegative integer. We say that we have an ascent of size d or more if a(i+1) >= a(i) + d. We determine the mean, variance and limiting distribution of the number of ascents of size d or more in the set of compositions of n. We also study the average size of the greatest ascent over all compositions of n.
On the length of shortest 2-collapsing words
Authors: Cherubini Alessandra , Kisielewicz Andrzej , Piochi Brunetto
Published: August 2021

Automata, Logic and Semantics

Given a word w over a finite alphabet Sigma and a finite deterministic automaton A = < Q,Sigma,delta >, the inequality vertical bar delta(Q,w)vertical bar <= vertical bar Q vertical bar - k means that under the natural action of the word w the image of the state set Q is reduced by at least k states. The word w is k-collapsing (k-synchronizing) if this inequality holds for any deterministic finite automaton ( with k + 1 states) that satisfies such an inequality for at least one word. We prove that for each alphabet Sigma there is a 2-collapsing word whose length is vertical bar Sigma vertical bar(3)+6 vertical bar Sigma vertical bar(2)+5 vertical bar Sigma vertical bar/2. Then we produce shorter 2-collapsing and 2-synchronizing words over alphabets of 4 and 5 letters.
Number of connected spanning subgraphs on the Sierpinski gasket
Authors: Chang Shu-Chiuan , Chen Lung-Chi
Published: August 2021

Combinatorics

We study the number of connected spanning subgraphs f(d,b) (n) on the generalized Sierpinski gasket SG(d,b) (n) at stage n with dimension d equal to two, three and four for b = 2, and layer b equal to three and four for d = 2. The upper and lower bounds for the asymptotic growth constant, defined as zSG(d,b) = lim(v ->infinity) ln f(d,b)(n)/v where v is the number of vertices, on SG(2,b) (n) with b = 2, 3, 4 are derived in terms of the results at a certain stage. The numerical values of zSG(d,b) are obtained.
Asymptotic enumeration on self-similar graphs with two boundary vertices
Authors: Teufl Elmar , Wagner Stephan
Published: August 2021

Combinatorics

We study two graph parameters, namely the number of spanning forests and the number of connected subgraphs, for self-similar graphs with exactly two boundary vertices. In both cases, we determine the general behavior for these and related auxiliary quantities by means of polynomial recurrences and a careful asymptotic analysis. It turns out that the so-called resistance scaling factor of a graph plays an essential role in both instances, a phenomenon that was previously observed for the number of spanning trees. Several explicit examples show that our findings are likely to hold in an even more general setting.
New decidable upper bound of the second level in the Straubing-Therien concatenation hierarchy of star-free languages
Authors: Almeida Jorge , Klima Ondrej
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications

In a recent paper we gave a counterexample to a longstanding conjecture concerning the characterization of regular languages of level 2 in the Straubing-Therien concatenation hierarchy of star-free languages. In that paper a new upper bound for the corresponding pseudovariety of monoids was implicitly given. In this paper we show that it is decidable whether a given monoid belongs to the new upper bound. We also prove that this new upper bound is incomparable with the previous upper bound.
Asymptotics of the Stirling numbers of the first kind revisited: A saddle point approach
Authors: Louchard Guy
Published: August 2021

Using the saddle point method, we obtain from the generating function of the Stirling numbers of the first kind [n j] and Cauchy's integral formula, asymptotic results in central and non-central regions. In the central region, we revisit the celebrated Goncharov theorem with more precision. In the region j = n - n(alpha); alpha > 1/2, we analyze the dependence of [n j] on alpha.
Asymptotic enumeration of orientations
Authors: Felsner Stefan , Fusy Eric , Noy Marc
Published: August 2021

We find the asymptotic number of 2-orientations of quadrangulations with n inner faces, and of 3-orientations of triangulations with n inner vertices. We also find the asymptotic number of prime 2-orientations (no separating quadrangle) and prime 3-orientations (no separating triangle). The estimates we find are of the form c . n(-alpha)gamma(n), for suitable constants c, alpha, gamma with alpha = 4 for 2-orientations and alpha = 5 for 3-orientations. The proofs are based on singularity analysis of D-finite generating functions, using the Fuchsian theory of complex linear differential equations.
Succinctness of two-way probabilistic and quantum finite automata
Authors: Yakaryilmaz Abuzer , Say A. C. Cem
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications

We introduce a new model of two-way finite automaton, which is endowed with the capability of resetting the position of the tape head to the left end of the tape in a single move during the computation. Several variants of this model are examined, with the following results: The weakest known model of computation where quantum computers recognize more languages with bounded error than their classical counterparts is identified. We prove that two-way probabilistic and quantum finite automata (2PFAs and 2QFAs) can be considerably more concise than both their one-way versions (1PFAs and 1QFAs), and two-way nondeterministic finite automata (2NFAs). For this purpose, we demonstrate several infinite families of regular languages which can be recognized with some fixed probability greater than 1 2 by just tuning the transition amplitudes of a 2QFA (and, in one case, a 2PFA) with a constant number of states, whereas the sizes of the corresponding 1PFAs, 1QFAs and 2NFAs grow without bound. We also show that 2QFAs with mixed states can support highly efficient probability amplification.
Noneffective Regularity of Equality Languages and Bounded Delay Morphisms
Authors: Karhumaki Juhani , Saarela Aleksi
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications

We give an instance of a class of morphisms for which it is easy to prove that their equality set is regular, but its emptiness is still undecidable. The class is that of bounded delay 2 morphisms.
Grammatical compression: compressed equivalence and other problems
Authors: Bertoni Alberto , Radicioni Roberto
Published: August 2021

special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Applications

In this work, we focus our attention to algorithmic solutions for problems where the instances are presented as straight-line programs on a given algebra. In our exposition, we try to survey general results by presenting some meaningful examples; moreover, where possible, we outline the proofs in order to give an insight of the methods and the techniques. We recall some recent results for the problem PosSLP, consisting of deciding if the integer defined by a straight-line program on the ring Z is greater than zero; we discuss some implications in the areas of numerical analysis and strategic games. Furthermore, we propose some methods for reducing Compressed Word Problem from an algebra to another; reductions from trace monoids to the semiring of nonnegative integers are exhibited and polynomial time algorithms for compressed equivalence in monoids related to Dyck reductions are shown. Finally, we consider inclusion problems for context-free languages, proving how in some cases efficient algorithms for these problems benefit from the ability to work with compressed data.
A de Bruijn - Erdos theorem and metric spaces
Authors: Chiniforooshan Ehsan , Chvatal Vasek
Published: August 2021

Combinatorics

De Bruijn and Erdos proved that every noncollinear set of n points in the plane determines at least n distinct lines. Chen and Chvatal suggested a possible generalization of this theorem in the framework of metric spaces. We provide partial results in this direction.
Computing tensor decompositions of finite matrix groups
Authors: Ankaralioglu Nurullah , Seress Akos
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

We describe an algorithm to compute tensor decompositions of central products of groups. The novelty over previous algorithms is that in the case of matrix groups that are both tensor decomposable and imprimitive, the new algorithm more often outputs the more desirable tensor decomposition.
The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words
Authors: Kufleitner Manfred , Lauser Alexander
Published: August 2021

Automata, Logic and Semantics

The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classes of finite monoids. Their join is known to be decidable due to a result of Almeida and Azevedo. In this paper, we give a new proof for Almeida and Azevedo's effective characterization of the join of R-trivial and L-trivial monoids. This characterization is a single identity of omega-terms using three variables.