bluuebunny/crossref_metadata_2025_split huggingface dataset:
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.
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.
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.
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
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.