bluuebunny/crossref_metadata_2025 huggingface dataset:
Cell-paths in mono- and bichromatic line arrangements in the plane
Authors: Aichholzer Oswin , Cardinal Jean , Hackl Thomas , Hurtado Ferran , Korman Matias , Pilz Alexander , Silveira Rodrigo I. , Uehara Ryuhei , Valtr Pavel , Vogtenhuber Birgit , Welzl Emo
Published: August 2021

Combinatorics

We prove that the dual graph of any arrangement of n lines in general position always contains a path of length at least n2/4. Further, we show that in every arrangement of n red and blue lines — in general position and not all of the same color — there is a simple path through at least n cells where red and blue lines are crossed alternatingly.
Packing and covering the balanced complete bipartite multigraph with cycles and stars
Authors: Lee Hung-Chih
Published: August 2021

Graph Theory

Let Ck denote a cycle of length k and let Sk denote a star with k edges. For multigraphs F, G and H, an (F,G)-decomposition of H is an edge decomposition of H into copies of F and G using at least one of each. For L⊆H and R⊆rH, an (F,G)-packing (resp. (F,G)-covering) of H with leave L (resp. padding R) is an (F,G)-decomposition of H-E(L) (resp. H+E(R)). An (F,G)-packing (resp. (F,G)-covering) of H with the largest (resp. smallest) cardinality is a maximum (F,G)-packing (resp. minimum (F,G)-covering), and its cardinality is referred to as the (F,G)-packing number (resp. (F,G)-covering number) of H. In this paper, we determine the packing number and the covering number of λKn,n with Ck's and Sk's for any λ, n and k, and give the complete solution of the maximum packing and the minimum covering of λKn,n with 4-cycles and 4-stars for any λ and n with all possible leaves and paddings.
Balancedness of subclasses of circular-arc graphs
Authors: Bonomo Flavia , Duran Guillermo , Safe Martın D. , Wagler Annegret K.
Published: August 2021

Graph Theory

A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of circular-arc graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. In this work, we characterize when a given graph G is balanced in terms of minimal forbidden induced subgraphs, by restricting the analysis to the case where G belongs to certain classes of circular-arc graphs, including Helly circular-arc graphs, claw-free circular-arc graphs, and gem-free circular-arc graphs. In the case of gem-free circular-arc graphs, analogous characterizations are derived for two superclasses of balanced graphs: clique-perfect graphs and coordinated graphs.
On the Hausdorff measure of regular ω-languages in Cantor space
Authors: Staiger Ludwig
Published: August 2021

Automata, Logic and Semantics

This paper deals with the calculation of the Hausdorff measure of regular ω-languages, that is, subsets of the Cantor space definable by finite automata. Using methods for decomposing regular ω-languages into disjoint unions of parts of simple structure we derive two sufficient conditions under which ω-languages with a closure definable by a finite automaton have the same Hausdorff measure as this closure. The first of these condition is related to the homogeneity of the local behaviour of the Hausdorff dimension of the underlying set, and the other with a certain topological density of the set in its closure.
Classification of skew translation generalized quadrangles, I
Authors: Thas Koen
Published: August 2021

Combinatorics

We describe new classification results in the theory of generalized quadrangles (= Tits-buildings of rank 2 and type B2), more precisely in the (large) subtheory of skew translation generalized quadrangles (``STGQs''). Some of these involve, and solve, long-standing open problems.
Symmetric bipartite graphs and graphs with loops
Authors: Cairns Grant , Mendan Stacey
Published: August 2021

Graph Theory

We show that if the two parts of a finite bipartite graph have the same degree sequence, then there is a bipartite graph, with the same degree sequences, which is symmetric, in that it has an involutive graph automorphism that interchanges its two parts. To prove this, we study the relationship between symmetric bipartite graphs and graphs with loops.
Avoider-enforcer star games
Authors: Grzesik Andrzej , Mikalački Mirjana , Nagy Zoltán Lóránt , Naor Alon , Patkós Balázs , Skerman Fiona
Published: August 2021

Combinatorics

In this paper, we study (1 : b) Avoider-Enforcer games played on the edge set of the complete graph on n vertices. For every constant k≥3 we analyse the k-star game, where Avoider tries to avoid claiming k edges incident to the same vertex. We consider both versions of Avoider-Enforcer games — the strict and the monotone — and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases fmonF, f-F and f+F, where F is the hypergraph of the game.
A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon
Authors: Cabello Sergio , Saumell Maria
Published: August 2021

Discrete Algorithms

We present a randomized algorithm to compute a clique of maximum size in the visibility graph G of the vertices of a simple polygon P. The input of the problem consists of the visibility graph G, a Hamiltonian cycle describing the boundary of P, and a parameter δ∈(0,1) controlling the probability of error of the algorithm. The algorithm does not require the coordinates of the vertices of P. With probability at least 1-δ the algorithm runs in O( |E(G)|2 / ω(G) log(1/δ)) time and returns a maximum clique, where ω(G) is the number of vertices in a maximum clique in G. A deterministic variant of the algorithm takes O(|E(G)|2) time and always outputs a maximum size clique. This compares well to the best previous algorithm by Ghosh et al. (2007) for the problem, which is deterministic and runs in O(|V(G)|2 |E(G)|) time.
The game chromatic number of trees and forests
Authors: Dunn Charles , Larsen Victor , Lindke Kira , Retter Troy , Toci Dustin
Published: August 2021

While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4. This gives partial progress on the open question of the computational complexity of the game chromatic number of a forest.
Cubical coloring — fractional covering by cuts and semidefinite programming
Authors: Šámal Robert
Published: August 2021

We introduce a new graph parameter that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings. We study the relations with chromatic number, bipartite density, and other graph parameters. We find the value of our parameter for a family of graphs based on hypercubes. These graphs play for our parameter the role that cliques play for the chromatic number and Kneser graphs for the fractional chromatic number. The fact that the defined parameter attains on these graphs the correct value suggests that our definition is a natural one. In the proof we use the eigenvalue bound for maximum cut and a recent result of Engström, Färnqvist, Jonsson, and Thapper [An approximability-related parameter on graphs – properties and applications, DMTCS vol. 17:1, 2015, 33–66]. We also provide a polynomial time approximation algorithm based on semidefinite programming and in particular on vector chromatic number (defined by Karger, Motwani and Sudan [Approximate graph coloring by semidefinite programming, J. ACM 45 (1998), no. 2, 246–265]).
Improving Vertex Cover as a Graph Parameter
Authors: Ganian Robert
Published: August 2021

Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however, the drawback of vertex cover is that bounding it severely restricts admissible graph classes. We introduce a generalization of vertex cover called twin-cover and show that FPT algorithms exist for a wide range of difficult problems when parameterized by twin-cover. The advantage of twin-cover over vertex cover is that it imposes a lesser restriction on the graph structure and attains low values even on dense graphs. Apart from introducing the parameter itself, this article provides a number of new FPT algorithms parameterized by twin-cover with a special emphasis on solving problems which are not in FPT even when parameterized by tree-width. It also shows that MS1 model checking can be done in elementary FPT time parameterized by twin-cover and discusses the field of kernelization.
The irregularity of two types of trees
Authors: Jianxi Li , Liu Yang , Shiu Wai
Published: August 2021

The irregularity of a graph $G$ is defined as the sum of weights $|d(u)-d(v)|$ of all edges $uv$ of $G$, where $d(u)$ and $d(v)$ are the degrees of the vertices $u$ and $v$ in $G$, respectively. In this paper, some structural properties on trees with maximum (or minimum) irregularity among trees with given degree sequence and trees with given branching number are explored, respectively. Moreover, the corresponding trees with maximum (or minimum) irregularity are also found, respectively.
Avoiding patterns in irreducible permutations
Authors: Baril Jean-Luc
Published: August 2021

We explore the classical pattern avoidance question in the case of irreducible permutations, i.e., those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.
Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights
Authors: Lu Hongliang
Published: August 2021

Let $G$ be a graph and $\mathcal{S}$ be a subset of $Z$. A vertex-coloring $\mathcal{S}$-edge-weighting of $G$ is an assignment of weights by the elements of $\mathcal{S}$ to each edge of $G$ so that adjacent vertices have different sums of incident edges weights. It was proved that every 3-connected bipartite graph admits a vertex-coloring $\mathcal{S}$-edge-weighting for $\mathcal{S} = \{1,2 \}$ (H. Lu, Q. Yu and C. Zhang, Vertex-coloring 2-edge-weighting of graphs, European J. Combin., 32 (2011), 22-27). In this paper, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring $\mathcal{S}$-edge-weighting for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$. These bounds we obtain are tight, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring $\mathcal{S}$-edge-weightings for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$.
Linear recognition of generalized Fibonacci cubes $Q_h(111)$
Authors: Rho Yoomi , Vesel Aleksander
Published: August 2021

The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 \ldots b_h$ containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.
A Sequential Search Distribution: Proofreading, Russian Roulette, and the Incomplete q-Eulerian Polynomials
Authors: Herbranson Travis , Rawlings Don
Published: August 2021

The distribution for the number of searches needed to find k of n lost objects is expressed in terms of a refinement of the q-Eulerian polynomials, for which formulae are developed involving homogeneous symmetric polynomials. In the case when k=n and the find probability remains constant, relatively simple and efficient formulas are obtained.From our main theorem, we further (1) deduce the inverse absorption distribution and (2) determine the expected number of times the survivor pulls the trigger in an n-player game of Russian roulette.
Tiling the Line with Triples
Authors: Meyerowitz Aaron
Published: August 2021

It is known the one dimensional prototile $0,a,a+b$ and its reflection $0,b,a+b$ always tile some interval. The subject has not received a great deal of further attention, although many interesting questions exist. All the information about tilings can be encoded in a finite digraph $D_{ab}$. We present several results about cycles and other structures in this graph. A number of conjectures and open problems are given.In [Go] an elegant proof by contradiction shows that a greedy algorithm will produce an interval tiling. We show that the process of converting to a direct proof leads to much stronger results.
Tilings, Quasicrystals, Discrete Planes, Generalized Substitutions, and Multidimensional Continued Fractions
Authors: Arnoux Pierre , Berthe Valerie , Ei Hiromi , Ito Shunji
Published: August 2021

The aim of this paper is to give an overview of recent results about tilings, discrete approximations of lines and planes, and Markov partitions for toral automorphisms.The main tool is a generalization of the notion of substitution. The simplest examples which correspond to algebraic parameters, are related to the iteration of one substitution, but we show that it is possible to treat arbitrary irrationalexamples by using multidimensional continued fractions.We give some non-trivial applications to Diophantine approximation, numeration systems and tilings, and we expose the main unsolved questions.
Enumerating Triangulations of Convex Polytopes
Authors: Bespamyatnikh Sergei
Published: August 2021

A triangulation of a finite point set A in $\mathbb{R}^d$ is a geometric simplicial complex which covers the convex hull of $A$ and whose vertices are points of $A$. We study the graph of triangulations whose vertices represent the triangulations and whose edges represent geometric bistellar flips. The main result of this paper is that the graph of triangulations in three dimensions is connected when the points of $A$ are in convex position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in $O(log log n)$ time per triangulation.
Number conserving cellular automata: new results on decidability and dynamics
Authors: Durand Bruno , Formenti Enrico , Grange Aristide , Róka Zsuzsanna
Published: August 2021

This paper is a survey on our recent results about number conserving cellular automata. First, we prove the linear time decidability of the property of number conservation. The sequel focuses on dynamical evolutions of number conserving cellular automata.
On undecidability of equicontinuity classification for cellular automata
Authors: Durand Bruno , Formenti Enrico , Varouchas Georges
Published: August 2021

Equicontinuity classification is a popular classification of cellular automata based on their dynamical behavior. In this paper we prove that most of its classes are undecidable.
Formalizing the transformations of a cognitive universe
Authors: Lafaye de Micheaux N. , López G. , Vitiello P. , Beauvois J. L.
Published: August 2021

In an effort to continue the pioneering work of Harary in USA and Flament in France, we have undertaken to develop, on an experimental basis, a formalized theory of systems of beliefs and their modifications. This theory uses the psycho-social concepts of theories of cognitive consistency and of the tools of discrete mathematics, such as rewriting and intervals within graphs. The axioms and rewriting rules are elaborated from experimental data, and we demonstrate that the system we have built has the property of termination. This result is in accordance with experimental observations that show that every subject having an inconsistent system of beliefs (i.e., one containing contradictions) makes this system evolve towards consistency to reach a simple, consistent reference framework.
Eulerian polynomials of type $D$ have only real roots
Authors: Savage Carla D. , Visontai Mirkó
Published: August 2021

We give an intrinsic proof of a conjecture of Brenti that all the roots of the Eulerian polynomial of type $D$ are real and a proof of a conjecture of Dilks, Petersen, and Stembridge that all the roots of the affine Eulerian polynomial of type $B$ are real, as well.

Nous prouvons, de façon intrinsèque, une conjecture de Brenti affirmant que toutes les racines du polynôme eulérien de type $D$ sont réelles. Nous prouvons également une conjecture de Dilks, Petersen, et Stembridge que toutes les racines du polynôme eulérien affine de type $B$ sont réelles.
On Kerov polynomials for Jack characters (extended abstract)
Authors: Féray Valentin , Dołęga Maciej
Published: August 2021

We consider a deformation of Kerov character polynomials, linked to Jack symmetric functions. It has been introduced recently by M. Lassalle, who formulated several conjectures on these objects, suggesting some underlying combinatorics. We give a partial result in this direction, showing that some quantities are polynomials in the Jack parameter $\alpha$ with prescribed degree. Our result has several interesting consequences in various directions. Firstly, we give a new proof of the fact that the coefficients of Jack polynomials expanded in the monomial or power-sum basis depend polynomially in $\alpha$. Secondly, we describe asymptotically the shape of random Young diagrams under some deformation of Plancherel measure.
Balanced labellings of affine permutations
Authors: Yoo Hwanchul , Yun Taedong
Published: August 2021

We study the $\textit{diagrams}$ of affine permutations and their $\textit{balanced}$ labellings. As in the finite case, which was investigated by Fomin, Greene, Reiner, and Shimozono, the balanced labellings give a natural encoding of reduced decompositions of affine permutations. In fact, we show that the sum of weight monomials of the $\textit{column strict}$ balanced labellings is the affine Stanley symmetric function defined by Lam and we give a simple algorithm to recover reduced words from balanced labellings. Applying this theory, we give a necessary and sufficient condition for a diagram to be an affine permutation diagram. Finally, we conjecture that if two affine permutations are $\textit{diagram equivalent}$ then their affine Stanley symmetric functions coincide.
A bijection between permutations and a subclass of TSSCPPs
Authors: Striker Jessica
Published: August 2021

We define a subclass of totally symmetric self-complementary plane partitions (TSSCPPs) which we show is in direct bijection with permutation matrices. This bijection maps the inversion number of the permutation, the position of the 1 in the last column, and the position of the 1 in the last row to natural statistics on these TSSCPPs. We also discuss the possible extension of this approach to finding a bijection between alternating sign matrices and all TSSCPPs. Finally, we remark on a new poset structure on TSSCPPs arising from this perspective which is a distributive lattice when restricted to permutation TSSCPPs.
The combinatorics of CAT(0) cubical complexes
Authors: Ardila Federico , Baker Tia , Yatchak Rika
Published: August 2021

Given a reconfigurable system $X$, such as a robot moving on a grid or a set of particles traversing a graph without colliding, the possible positions of $X$ naturally form a cubical complex $\mathcal{S}(X)$. When $\mathcal{S}(X)$ is a CAT(0) space, we can explicitly construct the shortest path between any two points, for any of the four most natural metrics: distance, time, number of moves, and number of steps of simultaneous moves. CAT(0) cubical complexes are in correspondence with posets with inconsistent pairs (PIPs), so we can prove that a state complex $\mathcal{S}(X)$ is CAT(0) by identifying the corresponding PIP. We illustrate this very general strategy with one known and one new example: Abrams and Ghrist's ``positive robotic arm" on a square grid, and the robotic arm in a strip. We then use the PIP as a combinatorial ``remote control" to move these robots efficiently from one position to another.
The Robinson―Schensted Correspondence and $A_2$-webs
Authors: Housley Matthew , Russell Heather M. , Tymoczko Julianna
Published: August 2021

The $A_2$-spider category encodes the representation theory of the $sl_3$ quantum group. Kuperberg (1996) introduced a combinatorial version of this category, wherein morphisms are represented by planar graphs called $\textit{webs}$ and the subset of $\textit{reduced webs}$ forms bases for morphism spaces. A great deal of recent interest has focused on the combinatorics of invariant webs for tensors powers of $V^+$, the standard representation of the quantum group. In particular, the invariant webs for the 3$n$th tensor power of $V^+$ correspond bijectively to $[n,n,n]$ standard Young tableaux. Kuperberg originally defined this map in terms of a graphical algorithm, and subsequent papers of Khovanov–Kuperberg (1999) and Tymoczko (2012) introduce algorithms for computing the inverse. The main result of this paper is a redefinition of Kuperberg's map through the representation theory of the symmetric group. In the classical limit, the space of invariant webs carries a symmetric group action. We use this structure in conjunction with Vogan's generalized tau-invariant and Kazhdan–Lusztig theory to show that Kuperberg's map is a direct analogue of the Robinson–Schensted correspondence.
Periodic Patterns of Signed Shifts
Authors: Archer Kassie , Elizalde Sergi
Published: August 2021

The periodic patterns of a map are the permutations realized by the relative order of the points in its periodic orbits. We give a combinatorial description of the periodic patterns of an arbitrary signed shift, in terms of the structure of the descent set of a certain transformation of the pattern. Signed shifts are an important family of one-dimensional dynamical systems. For particular types of signed shifts, namely shift maps, reverse shift maps, and the tent map, we give exact enumeration formulas for their periodic patterns. As a byproduct of our work, we recover some results of Gessel and Reutenauer and obtain new results on the enumeration of pattern-avoiding cycles.
Divisors on graphs, Connected flags, and Syzygies
Authors: Mohammadi Fatemeh , Shokrieh Farbod
Published: August 2021

We study the binomial and monomial ideals arising from linear equivalence of divisors on graphs from the point of view of Gröbner theory. We give an explicit description of a minimal Gröbner basis for each higher syzygy module. In each case the given minimal Gröbner basis is also a minimal generating set. The Betti numbers of $I_G$ and its initial ideal (with respect to a natural term order) coincide and they correspond to the number of ``connected flags'' in $G$. Moreover, the Betti numbers are independent of the characteristic of the base field.
The height of the Lyndon tree
Authors: Mercier Lucas , Chassaing Philippe
Published: August 2021

We consider the set $\mathcal{L}_n<$ of n-letters long Lyndon words on the alphabet $\mathcal{A}=\{0,1\}$. For a random uniform element ${L_n}$ of the set $\mathcal{L}_n$, the binary tree $\mathfrak{L} (L_n)$ obtained by successive standard factorization of $L_n$ and of the factors produced by these factorization is the $\textit{Lyndon tree}$ of $L_n$. We prove that the height $H_n$ of $\mathfrak{L} (L_n)$ satisfies $\lim \limits_n \frac{H_n}{\mathsf{ln}n}=\Delta$, in which the constant $\Delta$ is solution of an equation involving large deviation rate functions related to the asymptotics of Eulerian numbers ($\Delta ≃5.092\dots $). The convergence is the convergence in probability of random variables.
Combinatorial Topology of Toric arrangements
Authors: d'Antonio Giacomo , Delucchi Emanuele
Published: August 2021

We prove that the complement of a complexified toric arrangement has the homotopy type of a minimal CW-complex, and thus its homology is torsion-free. To this end, we consider the toric Salvetti complex, a combinatorial model for the arrangement's complement. Using diagrams of acyclic categories we obtain a stratification of this combinatorial model that explicitly associates generators in homology to the "local no-broken-circuit sets'' defined in terms of the incidence relations of the arrangement. Then we apply a suitably generalized form of Discrete Morse Theory to describe a sequence of elementary collapses leading from the full model to a minimal complex.

On démontre que l’espace complémentaire d’un arrangement torique complexifié a le type d’homotopie d’un complexe CW minimal, donc que ses groupes d’homologie sont libres. On considère d’abord un modèle combinatoire du complémentaire de l’arrangement: le complexe de Salvetti torique. On obtient une stratification de ce complexe qui fait correspondre explicitement les générateurs d’homologie aux “circuits-non-rompus locaux” associés aux relations d’incidence de l’arrangement. On applique une forme généralisée de la théorie de Morse discrète pour obtenir une suite de collapsements élémentaires qui conduit à un complexe minimal.
The Rearrangement Conjecture
Authors: Pantone Jay , Vatter Vincent
Published: August 2021

The Rearrangement Conjecture states that if two words over $\mathbb{P}$ are Wilf-equivalent in the factor order on $\mathbb{P}^{\ast}$ then they are rearrangements of each other. We introduce the notion of strong Wilf-equivalence and prove that if two words over $\mathbb{P}$ are strongly Wilf-equivalent then they are rearrangements of each other. We further conjecture that Wilf-equivalence implies strong Wilf-equivalence.
Quasisymmetric (k,l)-hook Schur functions
Authors: Mason Sarah , Niese Elizabeth
Published: August 2021

We introduce a quasisymmetric generalization of Berele and Regev's hook Schur functions and prove that these new quasisymmetric hook Schur functions decompose the hook Schur functions in a natural way. In this paper we examine the combinatorics of the quasisymmetric hook Schur functions, providing analogues of the Robinson-Schensted-Knuth algorithm and a generalized Cauchy Identity.
Reflection factorizations of Singer cycles
Authors: Lewis J.B. , Reiner V. , Stanton D.
Published: August 2021

The number of shortest factorizations into reflections for a Singer cycle in $GL_n(\mathbb{F}_q)$ is shown to be $(q^n-1)^{n-1}$. Formulas counting factorizations of any length, and counting those with reflections of fixed conjugacy classes are also given.

Nous prouvons que le nombre de factorisations de longueur minimale d’un cycle de Singer dans $GL_n(\mathbb{F}_q)$ comme un produit de réflexions est $(q^n-1)^{n-1}$. Nous présentons aussi des formules donnant le nombre de factorisations de toutes les longueurs ainsi que des formules pour le nombre de factorisations comme produit de réflexions ayant des classes de conjugaison fixes.
Signed tree associahedra
Authors: Pilaud Vincent
Published: August 2021

An associahedron is a polytope whose vertices correspond to the triangulations of a convex polygon and whose edges correspond to flips between them. J.-L. Loday gave a particularly elegant realization of the associahedron, which was then generalized in two directions: on the one hand to obtain realizations of graph associahedra, and on the other hand to obtain multiple realizations of the associahedron parametrized by a sequence of signs. The goal of this paper is to unify and extend these two constructions to signed tree associahedra.

Un associaèdre est un polytope dont les sommets correspondent aux triangulations d’un polygone convexe et dont les arêtes correspondent aux flips entre ces triangulations. J.-L. Loday a donné une construction particulièrement élégante de l’associaèdre qui a été généralisée dans deux directions : d’une part pour obtenir des réalisations des associaèdres de graphes, et d’autre part pour obtenir de multiples réalisations de l’associaèdre paramétrées par une suite de signes. L’objectif de ce travail est d’unifier et d’étendre ces constructions aux associaèdres d’arbres signés.
The $m$-Cover Posets and the Strip-Decomposition of $m$-Dyck Paths
Authors: Kallipoliti Myrto , Mühle Henri
Published: August 2021

In the first part of this article we present a realization of the $m$-Tamari lattice $\mathcal{T}_n^{(m)}$ in terms of $m$-tuples of Dyck paths of height $n$, equipped with componentwise rotation order. For that, we define the $m$-cover poset $\mathcal{P}^{\langle m \rangle}$ of an arbitrary bounded poset $\mathcal{P}$, and show that the smallest lattice completion of the $m$-cover poset of the Tamari lattice $\mathcal{T}_n$ is isomorphic to the $m$-Tamari lattice $\mathcal{T}_n^{(m)}$. A crucial tool for the proof of this isomorphism is a decomposition of $m$-Dyck paths into $m$-tuples of classical Dyck paths, which we call the strip-decomposition. Subsequently, we characterize the cases where the $m$-cover poset of an arbitrary poset is a lattice. Finally, we show that the $m$-cover poset of the Cambrian lattice of the dihedral group is a trim lattice with cardinality equal to the generalized Fuss-Catalan number of the dihedral group.

Dans la première partie de cet article nous présentons une réalisation du treillis $m$ -Tamari $\mathcal{T}_n^{(m)}$ à l’aide de $m$-uplets de chemins de Dyck de hauteur $n$, équipés de l’ordre de rotation composante par composante. Pour cela, nous définissons le poset de $m$-couverture $\mathcal{P}^{\langle m \rangle}$ d’un poset borné quelconque $\mathcal{P}$, et montrons que la plus petite complétion en treillis du poset de $m$-couverture du treillis de Tamari $\mathcal{T}_n$ est isomorphe au treillis $m$-Tamari $\mathcal{T}_n^{(m)}$. Unoutil crucial pour la preuve de cet isomorphisme est une décomposition des chemins $m$-Dyck en $m$-uplets de chemins de Dyck usuels, que nous appelons la décomposition en bandes. Par la suite, nous caractérisons les cas où le poset de $m$-couverture d’un poset donné est un treillis. Enfin nous montrons que le poset de $m$-couverture du treillis Cambrien du groupe diédral est un treillis svelte de cardinalité le nombre généralisé de Fuss-Catalan du groupe diédral.
Deformations of Weyl's Denominator Formula
Authors: Hamel Angêle , King Ronald
Published: August 2021

We introduce a series of conjectured identities that deform Weyl's denominator formula and generalize Tokuyama's formula to other root systems. These conjectures generalize a number of well-known results due to Okada. We also prove a related result for $B'_n$ that generalizes a theorem of Simpson.

Nous proposons une série de conjectures qui sont des déformations de la formule dénominateur de Weyl et qui généralisent la formule de Tokuyama à d’autres systèmes de racines. Ces résultats sont des généralisations de théorèmes bien connus dus à Okada. Nous donnons aussi la preuve d’un résultat pour $B'_n$ qui est une généralisation d’un théorème de Simpson.
The freeness of ideal subarrangements of Weyl arrangements
Authors: Abe Takuro , Barakat Mohamed , Cuntz Michael , Hoge Torsten , Terao Hiroaki
Published: August 2021

A Weyl arrangement is the arrangement defined by the root system of a finite Weyl group. When a set of positive roots is an ideal in the root poset, we call the corresponding arrangement an ideal subarrangement. Our main theorem asserts that any ideal subarrangement is a free arrangement and that its exponents are given by the dual partition of the height distribution, which was conjectured by Sommers-Tymoczko. In particular, when an ideal subarrangement is equal to the entire Weyl arrangement, our main theorem yields the celebrated formula by Shapiro, Steinberg, Kostant, and Macdonald. The proof of the main theorem is classification-free. It heavily depends on the theory of free arrangements and thus greatly differs from the earlier proofs of the formula.

Un arrangement de Weyl est défini par l’arrangement d’hyperplans du système de racines d’un groupe de Weyl fini. Quand un ensemble de racines positives est un idéal dans le poset de racines, nous appelons l’arrangement correspondant un sous-arrangement idéal. Notre théorème principal affirme que tout sous-arrangement idéal est un arrangement libre et que ses exposants sont donnés par la partition duale de la distribution des hauteurs, ce qui avait été conjecturé par Sommers-Tymoczko. En particulier, quand le sous-arrangement idéal est égal à l’arrangement de Weyl, notre théorème principal donne la célèbre formule par Shapiro, Steinberg, Kostant et Macdonald. La démonstration du théorème principal n’utilise pas de classification. Elle dépend fortement de la théorie des arrangements libres et diffère ainsi grandement des démonstrations précédentes de la formule.
Noncrossing sets and a Graßmannian associahedron
Authors: Santos Francisco , Stump Christian , Welker Volkmar
Published: August 2021

We study a natural generalization of the noncrossing relation between pairs of elements in $[n]$ to $k$-tuples in $[n]$. We show that the flag simplicial complex on $\binom{[n]}{k}$ induced by this relation is a regular, unimodular and flag triangulation of the order polytope of the poset given by the product $[k] \times [n-k]$ of two chains, and it is the join of a simplex and a sphere (that is, it is a Gorenstein triangulation). This shows the existence of a flag simplicial polytope whose Stanley-Reisner ideal is an initial ideal of the Graßmann-Plücker ideal, while previous constructions of such a polytope did not guaranteed flagness. The simplicial complex and the polytope derived from it naturally reflect the relations between Graßmannians with different parameters, in particular the isomorphism $G_{k,n} \cong G_{n-k,n}$. This simplicial complex is closely related to the weak separability complex introduced by Zelevinsky and Leclerc.

Nous étudions une généralisation naturelle de la relation entre les paires d’éléments non-croisés de $[n]$ et les $k$-uplets de $[n]$. Nous montrons que le complexe simplicial de drapeau sur $\binom{[n]}{k}$ induit par cette relation est une triangulation régulière, unimodulaire et de drapeau du polytope d’ordre de l’ensemble partiellement ordonné obtenu par le produit $[k] \times [n-k]$ des deux chaînes, et c’est la jointure d’un simplexe et une sphère (c’est-à-dire qu’elle est une triangulation de Gorenstein). Cela montre l’existence d’un polytope simplicial de drapeau dont l’idéal de Stanley-Reisner est un idéal initial de l’idéal de Graßmann-Plücker, tandis que les constructions précédentes d’un tel polytope ne garantissaient pas la propriété de drapeau. Le complexe simplicial et le polytope qui en découle reflètent naturellement les relations entre les Grassmanniens avec différents paramètres, en particulier l’isomorphisme $G_{k,n} \cong G_{n-k,n}$. Ce complexe simplicial est étroitement lié au complexe de séparabilité faible étudié par Zelevinskyet Leclerc.
Sweep maps for lattice paths
Authors: Loehr Nicholas , Warrington Gregory
Published: August 2021

Sweep maps are a family of maps on words that, while simple to define, are not yet known to be injective in general. This family subsumes many of the "zeta maps" that have arisen in the study of q,t-Catalan numbers in the course of relating the three statistics of area, bounce and dinv. A sweep map can be defined for words over arbitrary alphabets with arbitrary weights. The latter property makes them particularly suitable for the study of rational Catalan combinatorics.
Schubert varieties, inversion arrangements, and Peterson translation
Authors: Slofstra William
Published: August 2021

We show that an element $\mathcal{w}$ of a finite Weyl group W is rationally smooth if and only if the hyperplane arrangement $\mathcal{I} (\mathcal{w})$ associated to the inversion set of \mathcal{w} is inductively free, and the product $(d_1+1) ...(d_l+1)$ of the coexponents $d_1,\ldots,d_l$ is equal to the size of the Bruhat interval [e,w]. We also use Peterson translation of coconvex sets to give a Shapiro-Steinberg-Kostant rule for the exponents of $\mathcal{w}$.
Weighted Tree-Numbers of Matroid Complexes
Authors: Kook Woong , Lee Kang-Ju
Published: August 2021

We give a new formula for the weighted high-dimensional tree-numbers of matroid complexes. This formula is derived from our result that the spectra of the weighted combinatorial Laplacians of matroid complexes consist of polynomials in the weights. In the formula, Crapo’s $\beta$-invariant appears as the key factor relating weighted combinatorial Laplacians and weighted tree-numbers for matroid complexes.

Nous présentons une nouvelle formule pour les nombres d’arbres pondérés de grande dimension des matroïdes complexes. Cette formule est dérivée du résultat que le spectre des Laplaciens combinatoires pondérés des matrides complexes sont des polynômes à plusieurs variables. Dans la formule, le $\beta$;-invariant de Crapo apparaît comme étant le facteur clé reliant les Laplaciens combinatoires pondérés et les nombres d’arbres pondérés des matroïdes complexes.
Cohomology classes of rank varieties and a counterexample to a conjecture of Liu
Authors: Pawlowski Brendan
Published: August 2021

To each finite subset of a discrete grid $\mathbb{N}×\mathbb{N}$ (a diagram), one can associate a subvariety of a complex Grassmannian (a diagram variety), and a representation of a symmetric group (a Specht module). Liu has conjectured that the cohomology class of a diagram variety is represented by the Frobenius characteristic of the corresponding Specht module. We give a counterexample to this conjecture.However, we show that for the diagram variety of a permutation diagram, Liu's conjectured cohomology class $\sigma$ is at least an upper bound on the actual class $\tau$, in the sense that $\sigma - \tau$ is a nonnegative linear combination of Schubert classes. To do this, we consider a degeneration of Coskun's rank varieties which contains the appropriate diagram variety as a component. Rank varieties are instances of Knutson-Lam-Speyer's positroid varieties, whose cohomology classes are represented by affine Stanley symmetric functions. We show that the cohomology class of a rank variety is in fact represented by an ordinary Stanley symmetric function.

A chaque sous-ensemble fini de $\mathbb{N}×\mathbb{N}$ (un diagramme), on peut associer une sous-variété d’une grassmannienne complexe et une représentation d’un groupe symétrique (un module de Specht). Liu a conjecturé que la classe de cohomologie de la variété d’un diagramme est représentée par la caractéristique de Frobenius du module de Specht correspondant. Nous donnons un contre-exemple à cette conjecture.Cependant, nous montrons que dans le cas de la variété du diagramme de permutation, la classe de cohomologie conjecturée par Liu est au moins un majorant de la classe juste $\tau$ , c’est-à-dire que $\sigma - \tau$ est une combinaison linéaire non-négative des classes de Schubert. Pour ce faire, nous considérons une dégénérescence des variétés de rang de Coskun qui contient la variété appropriée d’un diagramme comme une composante irréductible. Les variétés de rang sont des exemples de variétés de positroïde, dont les classes de cohomologie sont représentées par des fonctions symétriques de Stanley affines. En effet, nous montrons que la classe de cohomologie d’une variété de rang est représentée par une fonction symétrique de Stanley ordinaire.
Affine charge and the $k$-bounded Pieri rule
Authors: Morse Jennifer , Schilling Anne
Published: August 2021

We provide a new description of the Pieri rule of the homology of the affine Grassmannian and an affineanalogue of the charge statistics in terms of bounded partitions. This makes it possible to extend the formulation ofthe Kostka–Foulkes polynomials in terms of solvable lattice models by Nakayashiki and Yamada to the affine setting.

Nous proposons une nouvelle description de la règle de Pieri de l’homologie de la variété Grassmannienneaffine et un analogue affine de la statistique de charge en termes de partitions bornées . Il est ainsi possible d’étendreau cas affine la formulation due à Nakayashiki et Yamada des polynômes de Kostka–Foulkes en termes de modèlesde réseaux résolubles.
The Number of Sides of a Parallelogram
Authors: Falbel Elisha , Koseleff Pierre-Vincent
Published: August 2021

We define parallelograms of base a and b in a group. They appear as minimal relators in a presentation of a subgroup with generators a and b. In a Lie group they are realized as closed polygonal lines, with sides being orbits of left-invariant vector fields. We estimate the number of sides of parallelograms in a free nilpotent group and point out a relation to the rank of rational series.
$Y$ -meshes and generalized pentagram maps
Authors: Glick Max , Pylyavskyy Pavlo
Published: August 2021

We introduce a rich family of generalizations of the pentagram map sharing the property that each generates an infinite configuration of points and lines with four points on each line. These systems all have a description as $Y$ -mutations in a cluster algebra and hence establish new connections between cluster theory and projective geometry.

Nous introduisons une famille de généralisations de l’application pentagramme. Chacune produit une configuration infinie de points et de lignes avec quatre points sur chaque ligne. Ces systèmes ont une description des $Y$ -mutations dans une algèbre amassée, un nouveau lien entre la théorie d’algèbres amassées et la géométrie projective.
A lattice on decreasing trees : the metasylvester lattice
Authors: Pons Viviane
Published: August 2021

We introduce a new combinatorial structure: the metasylvester lattice on decreasing trees. It appears in the context of the $m$-Tamari lattices and other related $m$-generalizations. The metasylvester congruence has been recently introduced by Novelli and Thibon. We show that it defines a sublattice of the $m$-permutations where elements can be represented by decreasing labelled trees: the metasylvester lattice. We study the combinatorial properties of this new structure. In particular, we give different realizations of the lattice. The $m$-Tamari lattice is by definition a sublattice of our newly defined metasylvester lattice. It leads us to a new realization of the $m$-Tamari lattice, using certain chains of the classical Tamari lattice.

Nous définissons une nouvelle structure combinatoire : le treillis métasylvestre sur les arbres décroissants. Il apparaît dans le contexte des treillis $m$-Tamari et des autres $m$-généralisations. La congruence métasylvestre a été introduite récemment par Novelli et Thibon. Nous montrons qu’elle définit un sous-treillis du treillis sur les $m$-permutations où les éléments sont représentés par des arbres étiquetés décroissants : le treillis métasylvestre. Nous étudions les propriétés combinatoires de ce treillis ainsi que des classes métasylvestres. En particulier, nous en donnons plusieurs réalisations. Le treillis de $m$-Tamari est par définition un sous-treillis du treillis métasylvestre. Cela nous amène à une nouvelle réalisation du treillis de$m$-Tamari par des chaines du treillis de Tamari classiques.
A categorification of the chromatic symmetric polynomial
Authors: Sazdanović Radmila , Yip Martha
Published: August 2021

The Stanley chromatic polynomial of a graph $G$ is a symmetric function generalization of the chromatic polynomial, and has interesting combinatorial properties. We apply the ideas of Khovanov homology to construct a homology $H$*($G$) of graded $S_n$-modules, whose graded Frobenius series $Frob_G(q,t)$ reduces to the chromatic symmetric function at $q=t=1$. We also obtain analogues of several familiar properties of the chromatic symmetric polynomials in terms of homology.

Le polynôme chromatique symétrique d’un graphe $G$ est une généralisation par une fonction symétrique du polynôme chromatique, et possède des propriétés combinatoires intéressantes. Nous appliquons les techniques de l’homologie de Khovanov pour construire une homologie $H$*($G$) de modules gradués $S_n$, dont la série bigraduée de Frobeniusse $Frob_G(q,t)$ réduit au polynôme chromatique symétrique à $q=t=1$. Nous obtenons également des analogies pour plusieurs propriétés connues des polynômes chromatiques en termes d’homologie.
A characterization for all interval doubling schemes of the lattice of permutations
Authors: Caspard Nathalie
Published: August 2021

The lattice \textbfS_n of all permutations on a n-element set has been shown to be \emphbounded [CAS], which is a strong constructive property characterized by the fact that \textbfS_n admits what we call an \emph interval doubling scheme. In this paper we characterize all interval doubling schemes of the lattice \textbfS_n, a result that gives a nice precision on the bounded nature of the lattice of permutations. This theorem is a direct corollary of two strong properties that are also given with their proofs.
Election algorithms with random delays in trees
Authors: Marckert Jean-François , Saheb-Djahromi Nasser , Zemmari Akka
Published: August 2021

The election is a classical problem in distributed algorithmic. It aims to design and to analyze a distributed algorithm choosing a node in a graph, here, in a tree. In this paper, a class of randomized algorithms for the election is studied. The election amounts to removing leaves one by one until the tree is reduced to a unique node which is then elected. The algorithm assigns to each leaf a probability distribution (that may depends on the information transmitted by the eliminated nodes) used by the leaf to generate its remaining random lifetime. In the general case, the probability of each node to be elected is given. For two categories of algorithms, close formulas are provided.
Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution
Authors: Morales Alejandro , Vassilieva Ekaterina
Published: August 2021

We derive a new formula for the number of factorizations of a full cycle into an ordered product of two permutations of given cycle types. For the first time, a purely combinatorial argument involving a bijective description of bicolored maps of specified vertex degree distribution is used. All the previous results in the field rely either partially or totally on a character theoretic approach. The combinatorial proof relies on a new bijection extending the one in [G. Schaeffer and E. Vassilieva. $\textit{J. Comb. Theory Ser. A}$, 115(6):903―924, 2008] that focused only on the number of cycles. As a salient ingredient, we introduce the notion of thorn trees of given vertex degree distribution which are recursive planar objects allowing simple description of maps of arbitrary genus. \par

Nous démontrons une nouvelle formule exprimant le nombre de factorisations d'un long cycle en produit de deux permutations ayant un type cyclique donné. Pour la première fois, nous utilisons un argument purement combinatoire basé sur une description bijective des cartes bicolores dont la distribution des degrés des sommets est donnée. Tous les résultats précédents dans le domaine se basent soit partiellement soit totalement sur la théorie des caractères de groupe. La preuve combinatoire se fonde sur une nouvelle bijection généralisant celle introduite dans [G. Schaeffer and E. Vassilieva. $\textit{J. Comb. Theory Ser. A}$, 115(6):903―924, 2008] ne s'intéressant qu'au nombre de cycles. L'ingrédient le plus saillant est l'introduction de la notion d'arbre épineux de structure cyclique donnée, des objets récursifs et planaires permettant une description simple des cartes de genus arbitraire.