Search

The Deodhar decomposition of the Grassmannian is a refinement of the Schubert, Richardson, and positroid stratifications of the Grassmannian. Go-diagrams are certain fillings of Ferrers diagrams with black stones, white stones, and pluses which index Deodhar components in the Grassmannian. We provide a series of corrective flips on diagrams which may be used to transform arbitrary fillings of Ferrers shapes with black stones, white stones, and pluses into a Go-diagram. This provides an extension of Lam and Williams' Le-moves for transforming reduced diagrams into Le-diagrams to the context of non-reduced diagrams. Next, we address the question of describing when the closure of one Deodhar component is contained in the closure of another. We show that if one Go-diagram D is obtained from another D ′ by replacing certain stones with pluses, then applying corrective flips, that there is a containment of closures of the associated Deodhar components, D ′ ¯ ⊂ D ¯ . Finally, we address the question of verifying whether an arbitrary filling of a Ferrers shape with black stones, white stones, and pluses is a Go-diagram. We show that no reasonable description of the class of Go-diagrams in terms of forbidden subdiagrams can exist by providing an injection from the set of valid Go-diagrams to the set of minimal forbidden subdiagrams for the class of Go-diagrams. In lieu of such a description, we offer an inductive characterization of the class of Go-diagrams. [ABSTRACT FROM AUTHOR]

Planar bicolored (plabic) graphs are combinatorial objects introduced by Postnikov to give parameterizations of the positroid cells of the totally nonnegative Grassmannian Gr ≥ 0 (n , k) . Any two plabic graphs for the same positroid cell can be related by a sequence of certain moves. The flip graph has plabic graphs as vertices and has edges connecting the plabic graphs which are related by a single move. A recent result of Galashin shows that plabic graphs can be seen as cross-sections of zonotopal tilings for the cyclic zonotope Z(n, 3). Taking this perspective, we show that the fundamental group of the flip graph is generated by cycles of length 4, 5, and 10, and use this result to prove a related conjecture of Dylan Thurston about triple crossing diagrams. We also apply our result to make progress on an instance of the generalized Baues problem. [ABSTRACT FROM AUTHOR]

We prove that the class of Brauer graph algebras coincides with the class of indecomposable idempotent algebras of biserial weighted surface algebras. These algebras are associated with triangulated surfaces with arbitrarily oriented triangles, investigated recently in Erdmann and Skowroński (J Algebra 505:490–558, 2018, Algebras of generalized dihedral type, Preprint. arXiv:1706.00688, 2017). Moreover, we prove that Brauer graph algebras are idempotent algebras of periodic weighted surface algebras, investigated in Erdmann and Skowroński (Algebras of generalized quaternion type, Preprint. arXiv:1710.09640, 2017). [ABSTRACT FROM AUTHOR]

The matching polynomial of a graph has coefficients that give the number of matchings in the graph. In this paper, we determine all connected graphs on eight vertices whose matching polynomials have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We show that there are exactly two matching integral graphs on eight vertices. [ABSTRACT FROM AUTHOR]

Let Γ be a finite graph and let A (Γ) be its adjacency matrix. Then Γ is singular if A (Γ) is singular. The singularity of graphs is of certain interest in graph theory and algebraic combinatorics. Here we investigate this problem for Cayley graphs Cay (G , H) when G is a finite group and when the connecting set H is a union of conjugacy classes of G. In this situation, the singularity problem reduces to finding an irreducible character χ of G for which ∑ h ∈ H χ (h) = 0. At this stage, we focus on the case when H is a single conjugacy class h G of G; in this case, the above equality is equivalent to χ (h) = 0 . Much is known in this situation, with essential information coming from the block theory of representations of finite groups. An element h ∈ G is called vanishing if χ (h) = 0 for some irreducible character χ of G. We study vanishing elements mainly in finite simple groups and in alternating groups in particular. We suggest some approaches for constructing singular Cayley graphs. [ABSTRACT FROM AUTHOR]

The goal of this paper is to introduce and study noncommutative Catalan numbers C n which belong to the free Laurent polynomial algebra L n in n generators. Our noncommutative numbers admit interesting (commutative and noncommutative) specializations, one of them related to Garsia–Haiman (q, t)-versions, another—to solving noncommutative quadratic equations. We also establish total positivity of the corresponding (noncommutative) Hankel matrices H n and introduce accompanying noncommutative binomial coefficients. [ABSTRACT FROM AUTHOR]

In the Pythagorean tuning system, the fifth is used to generate a scale of 12 notes per octave. In this paper, we use the octave to generate a scale of 19 notes per tritave; one can play this scale on a traditional piano. In this system, the octave becomes a proper interval and the 2:3:4 chord a proper chord. We study harmonic properties obtained from the 2:3:4 chord, in particular composition elements using dominants, inversions, major and minor chords, and diminished chords. The Tonnetz (array notation) turns out to be an effective tool to visualize the harmonic development in a composition based on these elements. 2:3:4 harmony may sound pure, yet sparse, as we illustrate in a short piece. [ABSTRACT FROM AUTHOR]

We show that if a semisimple synchronizing automaton with n states has a minimal reachable non-unary subset of cardinality r ≥ 2 , then there is a reset word of length at most (n - 1) D (2 , r , n) , where D(2, r, n) is the 2-packing number for families of r-subsets of [1, n]. [ABSTRACT FROM AUTHOR]

Let G be a graph which belongs to either of the following classes: (i) bipartite graphs, (ii) unmixed graphs, or (iii) claw–free graphs. Assume that J(G) is the cover ideal G and J (G) (k) is its k-th symbolic power. We prove that k deg (J (G)) ≤ reg (J (G) (k)) ≤ (k - 1) deg (J (G)) + | V (G) | - 1. We also determine families of graphs for which the above inequalities are equality. [ABSTRACT FROM AUTHOR]

The aim of this paper is to give analogs of the cluster expansion formula of Musiker and Schiffler for cluster algebras of type A with coefficients arising from boundary arcs of the corresponding triangulated polygon. Indeed, we give three cluster expansion formulas by perfect matchings of angles in triangulated polygon, by discrete subsets of arrows of the corresponding ice quiver and by minimal cuts of the corresponding quiver with potential. [ABSTRACT FROM AUTHOR]

We prove various results on monotone Boolean functions. In particular, we prove a conjecture proposed recently, stating that there are no monotone bent Boolean functions. Further, we give an upper bound on the nonlinearity of monotone functions in odd dimension, we describe the Walsh–Hadamard spectrum and investigate some other cryptographic properties of monotone Boolean functions.

Recently, there have been found relations between the algebraic co-rank and the zero forcing number along with the minimum rank. We continue on this direction by giving a characterization of the graphs with real algebraic co-rank at most 2. This implies that for any graph with minimum rank at most 3, its minimum rank is bounded from above by its real algebraic co-rank. This sheds some light on the conjecture that the real minimum rank is bounded from above by the real algebraic co-rank. [ABSTRACT FROM AUTHOR]

We prove a conjecture on the nonlinearity of monotone Boolean functions in even dimension, proposed in the recent paper “Cryptographic properties of monotone Boolean functions”, by Carlet et al. (J. Math. Cryptol. 10(1), 1-14, 2016). We also prove an upper bound on such nonlinearity, which is asymptotically much stronger than the conjectured upper bound and than the upper bound proved for odd dimension in this same paper. Contrary to these two previous bounds, which were not tight enough for allowing to clarify if monotone functions can have good nonlinearity, this new bound shows that the nonlinearity of monotone functions is always very bad, which represents a fatal cryptographic weakness of monotone Boolean functions; they are too closely approximated by affine functions for being usable as nonlinear components in cryptographic applications. We deduce a necessary criterion to be satisfied by a Boolean (resp. vectorial) function for being nonlinear. [ABSTRACT FROM AUTHOR]

The aim of this work is to prove a conjecture related to the Combinatorial Invariance Conjecture of Kazhdan–Lusztig polynomials, in the parabolic setting, for lower intervals in every arbitrary Coxeter group. This result improves and generalizes, among other results, the main results of Brenti et al. (2006) [6] , Marietti (2016) [21] . [ABSTRACT FROM AUTHOR]

We repurpose the main theorem of Thomas and Williams (J Algebr Comb 39(2):225-246, 2014) to prove that modular sweep maps are bijective. We construct the inverse of the modular sweep map by passing through an intermediary set of equitable partitions; motivated by an analogy to stable marriages, we prove that the set of equitable partitions for a fixed word forms a distributive lattice when ordered component wise. We conclude that the general sweep maps defined in Armstrong et al. (Adv Math 284:159-185, 2015) are bijective. As a special case of particular interest, this gives the first proof that the zeta map on rational Dyck paths is a bijection. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices, let S=K[x1,⋯,xn] be the polynomial ring in n variables over a field K and let I(G) denote the edge ideal of G. For every collection H of connected graphs with K2∈H, we introduce the notions of ind-matchH(G) and min-matchH(G). It will be proved that the inequalities ind-match{K2,C5}(G)≤reg(S/I(G))≤min-match{K2,C5}(G) are true. Moreover, we show that if G is a Cohen-Macaulay graph with girth at least five, then reg(S/I(G))=ind-match{K2,C5}(G). Furthermore, we prove that if G is a paw-free and doubly Cohen-Macaulay graph, then reg(S/I(G))=ind-match{K2,C5}(G) if and only if every connected component of G is either a complete graph or a 5-cycle graph. Among other results, we show that for every doubly Cohen-Macaulay simplicial complex, the equality reg(K[Δ])=dim(K[Δ]) holds. [ABSTRACT FROM AUTHOR]

Based on Crapo's theory of one point extensions of combinatorial geometries, we find various classes of geometric lattices that behave very well from the point of view of stability theory. One of them, ( K 3 , ≼ ) , is ω -stable, it has a monster model and an independence calculus that satisfies all the usual properties of non-forking. On the other hand, these classes are rather unusual, e.g. in ( K 3 , ≼ ) the Smoothness Axiom fails, and so ( K 3 , ≼ ) is not an AEC. [ABSTRACT FROM AUTHOR]

We present a stand-alone simple proof of a probabilistic interpretation of the Gaussian binomial coefficients by conditioning a random walk to hit a given lattice point at a given time. [ABSTRACT FROM AUTHOR]

We construct the definition of allowable graphs of the nonlinear Schrödinger equation of arbitrary degree and use it to verify the separation and irreducibility (over the ring of integers) of the characteristic polynomials of all the possible graphs giving 3-dimensional blocks of the normal form of the nonlinear Schrödinger equation. The method is purely algebraic and the obtained results will be useful in further studies of the nonlinear Schrödinger equation. [ABSTRACT FROM AUTHOR]

We give a complete combinatorial characterization of homogeneous quadratic relations of “universal character” valid for minors of quantum matrices (more precisely, for minors in the quantized coordinate ring O q ( M m , n ( K ) ) of m × n matrices over a field K , where q ∈ K ⁎ ). This is obtained as a consequence of a study of quantized minors of matrices generated by paths in certain planar graphs, called SE-graphs , generalizing the ones associated with Cauchon diagrams. Our efficient method of verifying universal quadratic identities for minors of quantum matrices is illustrated with many appealing examples. [ABSTRACT FROM AUTHOR]

For k , s ≥ 2 , the s -stable Kneser graphs are the graphs with vertex set the k -subsets S of { 1 , … , n } such that the circular distance between any two elements in S is at least s and two vertices are adjacent if and only if the corresponding k -subsets are disjoint. Braun showed that for n ≥ 2 k + 1 the automorphism group of the 2-stable Kneser graphs (Schrijver graphs) is isomorphic to the dihedral group of order 2 n . In this paper we generalize this result by proving that for s ≥ 2 and n ≥ s k + 1 the automorphism group of the s -stable Kneser graphs also is isomorphic to the dihedral group of order 2 n . [ABSTRACT FROM AUTHOR]

Let $$\gcd (a,b)=1$$ . J. Olsson and D. Stanton proved that the maximum number of boxes in a simultaneous ( a, b)-core is and that this maximum is achieved by a unique core. P. Johnson combined Ehrhart theory with the polynomial method to prove D. Armstrong's conjecture that the expected number of boxes in a simultaneous ( a, b)-core is We extend Johnson's method to compute the variance to be and also prove polynomiality of all moments. By extending the definitions of 'simultaneous cores' and 'number of boxes' to affine Weyl groups, we give uniform generalizations of all three formulae above to simply laced affine types. We further explain the appearance of the number 24 using the 'strange formula' of H. Freudenthal and H. de Vries. [ABSTRACT FROM AUTHOR]

We present a definition of mutations of species with potential that can be applied to the species realizations of any skew-symmetrizable matrix B over cyclic Galois extensions E / F whose base field F has a primitive [ E : F]th root of unity. After providing an example of a globally unfoldable skew-symmetrizable matrix whose species realizations do not admit non-degenerate potentials, we present a construction that associates a species with potential to each tagged triangulation of a surface with marked points and orbifold points of order 2. Then we prove that for any two tagged triangulations related by a flip, the associated species with potential are related by the corresponding mutation (up to a possible change of sign at a cycle), thus showing that these species with potential are non-degenerate. In the absence of orbifold points, the constructions and results specialize to previous work by Labardini-Fragoso (Proc Lond Math Soc 98(3):797-839, 2009. ; Sel Math New Ser 22(1):145-189, 2016. doi:. ). The species constructed here for each triangulation $$\tau $$ is a species realization of one of the several matrices that Felikson-Shapiro-Tumarkin have associated to $$\tau $$ in (Adv Math 231(5):2953-3002, 2012. ), namely, the one that in their setting arises from choosing the number $$\frac{1}{2}$$ for every orbifold point. [ABSTRACT FROM AUTHOR]

Introduced by Kawanaka in order to find the unipotent representations of finite groups of Lie type, generalized Gelfand-Graev characters have remained somewhat mysterious. Even in the case of the finite general linear groups, the combinatorics of their decompositions has not been worked out. This paper re-interprets Kawanaka's definition in type [ABSTRACT FROM AUTHOR]

We establish a powerful construction of D-optimal Euclidean designs, or D-optimal rotatable designs, on the unit hyperball by using the corner vectors associated with the symmetry groups of (semi-)regular polytopes. This is a full generalization of the classical construction choosing points in the form ( a,..., a,0,...,0) or in their orbits under the symmetry group of a regular hyperoctahedron (Gaffke and Heiligers 1995b), (Hirao et al. 2014), as well as Scheffé's { n, 2}-lattice design on the simplex. We prove a Gaffke-Heiligers type theorem for D - and A -invariant D-optimal Euclidean designs which is a 'reduction theorem' on the computational cost of searching observation points, and thereby construct many families of D-optimal Euclidean designs. For each group A , D , B , H , H , F , E , E , E , we determine the maximum degree of a D-optimal Euclidean design constructed by our method and in particular discover examples of degrees 5 and 6 for E and H , respectively. We also classify such maximum-degree designs for the groups H , H and F acting on the 3- and 4-dimensional Euclidean spaces. [ABSTRACT FROM AUTHOR]

Parabolic R -polynomials were introduced by Deodhar as parabolic analogues of ordinary R -polynomials defined by Kazhdan and Lusztig. In this paper, we are concerned with the computation of parabolic R -polynomials for the symmetric group. Let S n be the symmetric group on { 1 , 2 , … , n } , and let S = { s i | 1 ≤ i ≤ n − 1 } be the generating set of S n , where for 1 ≤ i ≤ n − 1 , s i is the adjacent transposition. For a subset J ⊆ S , let ( S n ) J be the parabolic subgroup generated by J , and let ( S n ) J be the set of minimal coset representatives for S n / ( S n ) J . For u ≤ v ∈ ( S n ) J in the Bruhat order and x ∈ { q , − 1 } , let R u , v J , x ( q ) denote the parabolic R -polynomial indexed by u and v . Brenti found a formula for R u , v J , x ( q ) when J = S ∖ { s i } , and obtained an expression for R u , v J , x ( q ) when J = S ∖ { s i − 1 , s i } . In this paper, we provide a formula for R u , v J , x ( q ) , where J = S ∖ { s i − 2 , s i − 1 , s i } and i appears after i − 1 in v . It should be noted that the condition that i appears after i − 1 in v is equivalent to that v is a permutation in ( S n ) S ∖ { s i − 2 , s i } . We also pose a conjecture for R u , v J , x ( q ) , where J = S ∖ { s k , s k + 1 , … , s i } with 1 ≤ k ≤ i ≤ n − 1 and v is a permutation in ( S n ) S ∖ { s k , s i } . [ABSTRACT FROM AUTHOR]

The article focus on solving quarter-plane lattice walks with interactions via the kernel method. Topics include number of n-step paths that start at point which visit vertices on the horizontal boundary; and how interactions will affect the solubility of quarter-plane lattice walk models and the properties of the generating functions Q(x, y, t).

In this paper we prove that the parabolic Kazhdan–Lusztig polynomials and the parabolic R -polynomials of the universal Coxeter group can be computed in a combinatorial way, by using special matchings. [ABSTRACT FROM AUTHOR]

Let $${\mathbb{K}}$$ be a field and $${S=\mathbb{K}[x_1,\dots,x_n]}$$ be the polynomial ring in n variables over $${\mathbb{K}}$$ . Let G be a graph with n vertices. Assume that $${I=I(G)}$$ is the edge ideal of G and $${J=J(G)}$$ is its cover ideal. We prove that $${{\rm sdepth}(J)\geq n-\nu_{o}(G)}$$ and $${{\rm sdepth}(S/J)\geq n-\nu_{o}(G)-1}$$ , where $${\nu_{o}(G)}$$ is the ordered matching number of G. We also prove the inequalities $${{\rm sdepth}(J^k)\geq {\rm depth}(J^k)}$$ and $${{\rm sdepth}(S/J^k)\geq {\rm depth}(S/J^k)}$$ , for every integer $${k\gg 0}$$ , when G is a bipartite graph. Moreover, we provide an elementary proof for the known inequality reg $${(S/I)\leq \nu_{o}(G)}$$ . [ABSTRACT FROM AUTHOR]

We give a counting formula for the set of rectangular increasing tableaux in terms of generalized Narayana numbers. We define small m-Schröder paths and give a bijection between the set of increasing rectangular tableaux and small m-Schröder paths, generalizing a result of Pechenik [4]. Using K-jeu de taquin promotion, we give a cyclic sieving phenomenon for the set of increasing hook tableaux. [ABSTRACT FROM AUTHOR]

The diamond product is the poset operation that when applied to the face lattices of two polytopes results in the face lattice of the Cartesian product of the polytopes. Application of the diamond product to two Eulerian posets is a bilinear operation on the cd-indices of the two posets, yielding a product on cd-polynomials. A lattice path interpretation is provided for this product of two cd-monomials. [ABSTRACT FROM AUTHOR]

We introduce a general construction that takes as input a so-called stiff PRO and that outputs a Hopf algebra. Stiff PROs are particular PROs that can be described by generators and relations with precise conditions. Our construction generalizes the classical construction from operads to Hopf algebras of van der Laan. We study some of its properties and review some examples of application. We get in particular Hopf algebras on heaps of pieces and retrieve some deformed versions of the noncommutative Faà di Bruno algebra introduced by Foissy. [ABSTRACT FROM AUTHOR]

We study a subset of a parabolic quotient in a simply laced Weyl group W-stable under an automorphism $$\sigma $$ -which we call the balanced parabolic quotient. This subset describes the interaction between the branching rule for a Levi subalgebra, Demazure modules, and $$\sigma $$ -invariant weight spaces in $$\sigma $$ -stable simple modules for the corresponding Lie algebra. The Hasse diagram of the balanced parabolic quotient in types A and D under the Bruhat order is a directed forest with a remarkable self-similarity property, and its order is related to the Fibonacci sequence. We characterize an element of a balanced quotient on the level of the root system of W and find that the subalgebras of the Borel associated with these elements decompose into the direct sum of two subalgebras: one contained in the Borel for a Levi subalgebra and another consisting of $$\sigma $$ -invariants. [ABSTRACT FROM AUTHOR]

The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity. We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree. [ABSTRACT FROM AUTHOR]

A set of vectors of equal norm in $$\mathbb {C}^d$$ represents equiangular lines if the magnitudes of the Hermitian inner product of every pair of distinct vectors in the set are equal. The maximum size of such a set is $$d^2$$ , and it is conjectured that sets of this maximum size exist in $$\mathbb {C}^d$$ for every $$d \ge 2$$ . We take a combinatorial approach to this conjecture, using mutually unbiased bases (MUBs) in the following three constructions of equiangular lines: For each construction, we give the dimensions $$d$$ for which we currently know that the construction produces a maximum-sized set of equiangular lines. [ABSTRACT FROM AUTHOR]

Diassociative algebras form a category of algebras recently introduced by Loday. A diassociative algebra is a vector space endowed with two associative binary operations satisfying some very natural relations. Any diassociative algebra is an algebra over the diassociative operad, and, among its most notable properties, this operad is the Koszul dual of the dendriform operad. We introduce here, by adopting the point of view and the tools offered by the theory of operads, a generalization on a nonnegative integer parameter γ of diassociative algebras, called γ -pluriassociative algebras, so that 1-pluriassociative algebras are diassociative algebras. Pluriassociative algebras are vector spaces endowed with 2 γ associative binary operations satisfying some relations. We provide a complete study of the γ -pluriassociative operads, the underlying operads of the category of γ -pluriassociative algebras. We exhibit a realization of these operads, establish several presentations by generators and relations, compute their Hilbert series, show that they are Koszul, and construct the free objects in the corresponding categories. We also study several notions of units in γ -pluriassociative algebras and propose a general way to construct such algebras. This paper ends with the introduction of an analogous generalization of the triassociative operad of Loday and Ronco. [ABSTRACT FROM AUTHOR]

We generalize the construction of multi-tildes in the aim to provide double multi-tilde operators for regular languages. We show that the underlying algebraic structure involves the action of some operads. An operad is an algebraic structure that mimics the composition of the functions. The involved operads are described in terms of combinatorial objects. These operads are obtained from more primitive objects, namely precompositions, whose algebraic counter-parts are investigated. One of these operads acts faithfully on languages in the sense that two different operators act in two different ways. [ABSTRACT FROM AUTHOR]

We prove that the quivers with potentials associated with triangulations of surfaces with marked points, and possibly empty boundary, are non-degenerate, provided the underlying surface with marked points is not a closed sphere with exactly five punctures. This is done by explicitly defining the QPs that correspond to tagged triangulations and proving that whenever two tagged triangulations are related to a flip, their associated QPs are related to the corresponding QP-mutation. As a by-product, for (arbitrarily punctured) surfaces with non-empty boundary, we obtain a proof of the non-degeneracy of the associated QPs which is independent from the one given by the author in the first paper of the series. The main tool used to prove the aforementioned compatibility between flips and QP-mutations is what we have called Popping Theorem, which, roughly speaking, says that an apparent lack of symmetry in the potentials arising from ideal triangulations with self-folded triangles can be fixed by a suitable right-equivalence. [ABSTRACT FROM AUTHOR]

The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. A minimizer graph is such that minimizes the spectral radius among all connected graphs on n vertices with diameter d . The minimizer graphs are known for d ∈ { 1 , 2 } ∪ [ n / 2 , 2 n / 3 − 1 ] ∪ { n − k | k = 1 , 2 , … , 8 } . In this paper, we determine all minimizer graphs for d = 2 ( n − 1 ) / 3 . [ABSTRACT FROM AUTHOR]

Associated with each irreducible crystallographic root system $$\varPhi $$ , there is a certain cell complex structure on the torus obtained as the quotient of the ambient space by the coroot lattice of $$\varPhi $$ . This is the Steinberg torus. A main goal of this paper is to exhibit a module structure on (the set of faces of) this complex over the (set of faces of the) Coxeter complex of $$\varPhi $$ . The latter is a monoid under the Tits product of faces. The module structure is obtained from geometric considerations involving affine hyperplane arrangements. As a consequence, a module structure is obtained on the space spanned by affine descent classes of a Weyl group, over the space spanned by ordinary descent classes. The latter constitute a subalgebra of the group algebra, the classical descent algebra of Solomon. We provide combinatorial models for the module of faces when $$\varPhi $$ is of type A or C. [ABSTRACT FROM AUTHOR]