Search

The chromatic number related to a colouring of facets of certain classes of generalised associahedra is studied. The exact values are obtained for permutohedra, associahedra and simple permutoassociahedra, while lower and upper bounds are established for cyclohedra and stellohedra. The asymptotic values of the chromatic numbers for associahedra, cyclohedra and simple permutoassociahedra are given. [ABSTRACT FROM AUTHOR]

We show that the order complex of the poset of nonempty intervals, ordered by inclusion, is a Tchebyshev triangulation of the order complex of the original poset. Besides studying the properties of this transformation, we show that the dual of the type B permutohedron is combinatorially equivalent to the suspension of the order complex of the poset of nonempty intervals of a Boolean algebra (with the minimum and maximum elements removed). [ABSTRACT FROM AUTHOR]

The aim of this work is to study the problem of prior elicitation for the consensus ranking in the Mallows model with Spearman's distance, a popular distance-based model for rankings or permutation data. Previous Bayesian inference for such a model has been limited to the use of the uniform prior over the space of permutations. We present a novel strategy to elicit informative prior beliefs on the location parameter of the model, discussing the interpretation of hyper-parameters and the implication of prior choices for the posterior analysis. [ABSTRACT FROM AUTHOR]

Motivated by the work of Panina and her coauthors on cyclopermutohedron we study a poset whose elements correspond to equivalence classes of partitions of the set { 1 , ⋯ , n + 1 } up to cyclic permutations and orientation reversion. This poset is the face poset of a regular CW complex which we call bi-cyclopermutohedron and denote it by QP n + 1 . The complex QP n + 1 contains subcomplexes homeomorphic to moduli space of certain planar polygons with n + 1 sides up to isometries. In this article we find an optimal discrete Morse function on QP n + 1 and use it to compute its homology with Z as well as Z 2 coefficients. [ABSTRACT FROM AUTHOR]

We define and study a new family of polytopes which are formed as convex hulls of partial alternating sign matrices. We determine the inequality descriptions, number of facets, and face lattices of these polytopes. We also study partial permutohedra that we show arise naturally as projections of these polytopes. We enumerate facets and also characterize the face lattices of partial permutohedra in terms of chains in the Boolean lattice. Finally, we have a result and a conjecture on the volume of partial permutohedra when one parameter is fixed to be two. [ABSTRACT FROM AUTHOR]

We introduce a metric on the set of permutations of given order, which is a weighted generalization of Kendall's τ rank distance and study its properties. Using the edge graph of a permutohedron, we give a criterion which guarantees that a permutation lies metrically between another two fixed permutations. In addition, the conditions under which four points from the resulting metric space form a pseudolinear quadruple were found. [ABSTRACT FROM AUTHOR]

We present a hardware-based implementation of linear program (LP) decoding for binary linear codes. LP decoding frames error–correction as an optimization problem. In contrast, variants of belief propagation (BP) decoding frame error–correction as a problem of graphical inference. LP decoding has several advantages over BP-based methods, including convergence guarantees and better error-rate performance in high-reliability channels. The latter makes LP decoding attractive for optical transport and storage applications. However, LP decoding, when implemented with general solvers, does not scale to large blocklengths and is not suitable for a parallelized implementation in hardware. It has been recently shown that the alternating direction method of multipliers (ADMM) can be applied to decompose the LP decoding problem. The result is a message-passing algorithm with a structure very similar to BP. We present modifications to this algorithm, resulting in a more intuitive and hardware-compatible form. This is particularly true for projection onto the parity polytope: the major computational primitive for ADMM-LP decoding. Furthermore, we present results for a fixed-point Verilog implementation of ADMM-LP decoding. This implementation targets a field-programmable gate array (FPGA) platform to evaluate error-rate performance and estimate resource usage. We show that frame error rate performance well within 0.5 dB of double-precision implementations is possible with 10-bit messages. Finally, we outline research opportunities that should be explored en route to an application-specific integrated circuit (ASIC) implementation that is capable of Gigabit-per-second throughput. [ABSTRACT FROM AUTHOR]

A polytope plays a central role in different areas of mathematics. It is used quite heavily in applied fields of mathematics, such as medical imaging and robotics, geometric modeling. A polytope has many users in modern science such as computer graphics, optimization, and search engine. It is intended for a broad audience of mathematically inclined. Therefore in this paper, we shall take a polytope with one kind of application, which is known as a Stasheff polytope. it has been applied in: moduli spaces, Erhart polynomial, physics- chemistry, and Hopf algebras. In this paper,a finite graph G with tubingis taken, the nodes of the graph are reducetopoints in R^n and the convex hull for them are simplex, permutahedron and associahedron (Stasheff polytope ) are studied. Also, a fan graph to the painted tree is also taken and reduces its nodes to points inR^n. The converse of this result is also given with different examples to consult our results.

It is well known that the weak Bruhat order on the symmetric group on a finite number n of letters is a lattice, denoted by P.n/ and often called the permutohedron on n letters, of which the Tamari lattice A.n/ is a lattice retract. The equational theory (or word problem) of a class of lattices is the set of all lattice identities satisfied by all members of that class. Our main results imply, as particular cases, the following. Theorem I. The equational theories of all P.n/ and of all A.n/ are both decidable. Theorem I. There exists a lattice identity that holds in all P.n/, but fails in a certain 3;338-element lattice. Theorem III. The equational theory of all extended permutohedra, on arbitrary (possibly infinite) posets, is trivial. The proofs of Theorems I and II involve reductions of algebraic statements to certain tiling properties of finite chains. [ABSTRACT FROM AUTHOR]

A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations can be represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. There is an analogous polytope for conditional independence relations coming from a regular Gaussian model, and it can be defined using multiinformation or relative entropy. For directed acyclic graphical models and also for mixed graphical models containing undirected, directed, and bidirected edges, we give a construction of this polytope, up to equivalence of normal fans, as a Minkowski sum of matroid polytopes. Finally, we apply this geometric insight to construct a new ordering-based search algorithm for causal inference via directed acyclic graphical models. [ABSTRACT FROM AUTHOR]

We describe a way of producing an -dimensional manifold starting with an Alexander self-dual simplicial complex on vertices (or, in another terminology, by a simple game with constant sum with players). The construction presents explicitly, by describing its regular cellulation. [ABSTRACT FROM AUTHOR]

To any graph G, one can associate a toric variety $$X(\mathcal {P}G)$$ , obtained as a blowup of projective space along coordinate subspaces corresponding to connected subgraphs of G. The polytopes of these toric varieties are the graph associahedra, a class of polytopes that includes the permutohedron, associahedron, and stellahedron. We show that the space $$X(\mathcal {P}{G})$$ is isomorphic to a Hassett compactification of $$M_{0,n}$$ precisely when G is an iterated cone over a discrete set. This may be viewed as a generalization of the well-known fact that the Losev-Manin moduli space is isomorphic to the toric variety associated with the permutohedron. [ABSTRACT FROM AUTHOR]

An operad (this paper deals with non-symmetric operads) may be conceived as a partial algebra with a family of insertion operations, which correspond to substitution of an operation within an operation. These insertion operations are Gerstenhaber's circle-i products, and they satisfy two kinds of associativity, one of them involving commutativity. A Cat-operad is an operad enriched over the category Cat of small categories, as a 2-category with small hom-categories is a category enriched over Cat. This means that the operadic operations of the same arity in a Cat-operad do not make just a set, but they are the objects of a small category. The notion of weak Cat-operad is to the notion of Cat-operad what the notion of bicategory is to the notion of 2-category. This means that the equations of operads like associativity of insertions are replaced by isomorphisms in a category. The goal of this paper is to formulate conditions concerning these isomorphisms that ensure coherence, in the sense that all diagrams of canonical arrows commute. This is the sense in which the notions of monoidal category and bicategory are coherent. (The coherence of monoidal categories, which is due to Mac Lane, is the best known coherence result.) The coherence proof in the paper is much simplified by indexing the insertion operations in a context-independent way, and not in the usual manner. This proof, which is in the style of term rewriting, involves an argument with normal forms that generalizes what is established with the completeness proof for the standard presentation of symmetric groups. This generalization may be of an independent interest, and related to other matters than those studied in this paper. Some of the coherence conditions for weak Cat-operads lead to the hemiassociahedron, which is a polyhedron related to, but different from, the three-dimensional associahedron and permutohedron. [ABSTRACT FROM AUTHOR]

For a closure space (P, φ) with φ(ø) = ø, the closures of open subsets of P, called the regular closed subsets, form an ortholattice (P, φ), extending the poset (P, φ) of all clopen subsets. If (P, φ) is a finite convex geometry, then (P, φ) is pseudocomplemented. The Dedekind-MacNeille completion of the poset of regions of any central hyperplane arrangement can be obtained in this way, hence it is pseudocomplemented. The lattice (P, φ) carries a particularly interesting structure for special types of convex geometries, that we call closure spaces of semilattice type. For finite such closure spaces, • (P, φ) satisfies an infinite collection of stronger and stronger quasi-identities, weaker than both meet- and join-semidistributivity. Nevertheless it may fail semidistributivity. • If (P, φ) is semidistributive, then it is a bounded homomorphic image of a free lattice. • (P, φ) is a lattice if and only if every regular closed set is clopen. The extended permutohedron (G) on a graph G and the extended permutohedron S on a join-semilattice S, are both defined as lattices of regular closed sets of suitable closure spaces. While the lattice of all regular closed sets is, in the semilattice context, always the Dedekind-MacNeille completion of the poset of clopen sets, this does not always hold in the graph context, although it always does so for finite block graphs and for cycles. Furthermore, both (G) and S are bounded homomorphic images of free lattices. [ABSTRACT FROM AUTHOR]

The phylogenetic tree space, introduced by Billera, Holmes, and Vogtmann, is a cone over a simplicial complex. In this short article, we construct this complex from local gluings of classical polytopes, the associahedron and the permutohedron. Its homotopy is also reinterpreted and calculated based on polytope data. [ABSTRACT FROM AUTHOR]

A family of polytopes introduced by E.M. Feichtner, A. Postnikov, and B. Sturmfels, which were named nestohedra, consists in each dimension of an interval of polytopes starting with a simplex and ending with a permutohedron. This paper investigates a problem of changing and extending the boundaries of these intervals. An iterative application of Feichtner-Kozlov procedure of forming complexes of nested sets is a solution of this problem. By using a simple algebraic presentation of members of nested sets it is possible to avoid the problem of increasing the complexity of the structure of nested curly braces in elements of the produced simplicial complexes. [ABSTRACT FROM AUTHOR]

We introduce a "lifting'' construction for generalized permutohedra, which turns an $n$-dimensional generalized permutahedron into an $(n+1)$-dimensional one. We prove that this construction gives rise to Stasheff's multiplihedron from homotopy theory, and to the more general "nestomultiplihedra,'' answering two questions of Devadoss and Forcey. We construct a subdivision of any lifted generalized permutahedron whose pieces are indexed by compositions. The volume of each piece is given by a polynomial whose combinatorial properties we investigate. We show how this "composition polynomial'' arises naturally in the polynomial interpolation of an exponential function. We prove that its coefficients are positive integers, and conjecture that they are unimodal.

When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode error-correcting codes at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper, we draw on decomposition methods from optimization theory, specifically the alternating direction method of multipliers (ADMM), to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a “two-slice” characterization of the parity polytope, the polytope formed by taking the convex hull of all codewords of the single parity check code. This new characterization simplifies the representation of points in the polytope. Using this simplification, we develop an efficient algorithm for Euclidean norm projection onto the parity polytope. This projection is required by the ADMM decoder and its solution allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We present numerical results for LDPC codes of lengths more than 1000. The waterfall region of LP decoding is seen to initiate at a slightly higher SNR than for sum-product BP, however an error floor is not observed for LP decoding, which is not the case for BP. Our implementation of LP decoding using the ADMM executes as fast as our baseline sum-product BP decoder, is fully parallelizable, and can be seen to implement a type of message-passing with a particularly simple schedule. [ABSTRACT FROM PUBLISHER]

Abstract: Grätzer asked in 1971 for a characterization of sublattices of Tamari lattices. A natural candidate was coined by McKenzie in 1972 with the notion of a bounded homomorphic image of a free lattice—in short, bounded lattice. Urquhart proved in 1978 that every Tamari lattice is bounded (thus so are its sublattices). Geyer conjectured in 1994 that every finite bounded lattice embeds into some Tamari lattice. We disprove Geyerʼs conjecture, by introducing an infinite collection of lattice-theoretical identities that hold in every Tamari lattice, but not in every finite bounded lattice. Among those finite counterexamples, there are the permutohedron on four letters , and in fact two of its subdirectly irreducible retracts, which are Cambrian lattices of type A. For natural numbers m and n, we denote by the (bounded) lattice obtained by doubling a join of m atoms in an -atom Boolean lattice. We prove that embeds into a Tamari lattice iff , and that embeds into a permutohedron iff . In particular, cannot be embedded into any permutohedron. Nevertheless we prove that is a homomorphic image of a sublattice of the permutohedron on 12 letters. [Copyright &y& Elsevier]

For a Coxeter system ( W, S), the subgroup W generated by a subset J⊆ S is called a parabolic subgroup of W. The Coxeterhedron PW associated to ( W, S) is the finite poset of all cosets { wW} of all parabolic subgroups of W, ordered by inclusion. This poset can be realized by the face lattice of a simple polytope, constructed as the convex hull of the orbit of a generic point in ℝ under an action of the reflection group W. In this paper, for the groups W= A, B and D in a case-by-case manner, we present an elementary proof of the cyclic sieving phenomenon for faces of various dimensions of PW under the action of a cyclic group generated by a Coxeter element. This result provides a geometric, enumerative and combinatorial approach to re-prove a theorem in Reiner et al. (J. Comb. Theory, Ser. A 108:17-50, ). The original proof is proved by an algebraic method that involves representation theory and Springer's theorem on regular elements. [ABSTRACT FROM AUTHOR]

Abstract: We unravel the algebraic structure which controls the various ways of computing the word and its siblings. We show that it gives rise to a new type of operads, that we call permutads. A permutad is an algebra over the monad made of surjective maps between finite sets. It turns out that this notion is equivalent to the notion of “shuffle algebra” introduced previously by the second author. It is also very close to the notion of “shuffle operad” introduced by V. Dotsenko and A. Khoroshkin. It can be seen as a noncommutative version of the notion of nonsymmetric operads. We show that the role of the associahedron in the theory of operads is played by the permutohedron in the theory of permutads. [Copyright &y& Elsevier]

The set of permutations of 〈 n〉={1,..., n} in one-line notation is Π( n). The shorthand encoding of a⋯ a∈ Π( n) is a⋯ a. A shorthand universal cycle for permutations (SP-cycle) is a circular string of length n! whose substrings of length n−1 are the shorthand encodings of Π( n). When an SP-cycle is decoded, the order of Π( n) is a Gray code in which successive permutations differ by the prefix-rotation σ=(1 2 ⋯ i) for i∈{ n−1, n}. Thus, SP-cycles can be represented by n! bits. We investigate SP-cycles with maximum and minimum 'weight' (number of σs in the Gray code). An SP-cycle n a n b⋯ n z is 'periodic' if its 'sub-permutations' a, b,..., z equal Π( n−1). We prove that periodic min-weight SP-cycles correspond to spanning trees of the ( n−1)-permutohedron. We provide two constructions: B( n) and C( n). In B( n) the spanning trees use 'half-hunts' from bell-ringing, and in C( n) the sub-permutations use cool-lex order by Williams (SODA, 987-996, ). Algorithmic results are: (1) memoryless decoding of B( n) and C( n), (2) O(( n−1)!)-time generation of B( n) and C( n) using sub-permutations, (3) loopless generation of B( n)'s binary representation n bits at a time, and (4) O( n+ ν( n))-time ranking of B( n)'s permutations where ν( n) is the cost of computing a permutation's inversion vector. Results (1)-(4) improve on those for the previous SP-cycle construction D( n) by Ruskey and Williams (ACM Trans. Algorithms 6(3):Art. 45, ), which we characterize here using 'recycling'. [ABSTRACT FROM AUTHOR]

Abstract: We investigate a family of polytopes introduced by E.M. Feichtner, A. Postnikov and B. Sturmfels, which were named nestohedra. The vertices of these polytopes may intuitively be understood as constructions of hypergraphs. Limit cases in this family of polytopes are, on the one end, simplices, and, on the other end, permutohedra. In between, as notable members one finds associahedra and cyclohedra. The polytopes in this family are investigated here both as abstract polytopes and as realized in Euclidean spaces of all finite dimensions. The later realizations are inspired by J.D. Stasheff ʼs and S. Shniderʼs realizations of associahedra. In these realizations, passing from simplices to permutohedra, via associahedra, cyclohedra and other interesting polytopes, involves truncating vertices, edges and other faces. The results presented here reformulate, systematize and extend previously obtained results, and in particular those concerning polytopes based on constructions of graphs, which were introduced by M. Carr and S.L. Devadoss. [Copyright &y& Elsevier]

Abstract: To a link , we associate a spectral sequence whose page is the reduced Khovanov homology of L and which converges to a version of the monopole Floer homology of the branched double cover. The pages for depend only on the mutation equivalence class of L. We define a mod 2 grading on the spectral sequence which interpolates between the δ-grading on Khovanov homology and the mod 2 grading on Floer homology. We also derive a new formula for link signature that is well adapted to Khovanov homology. More generally, we construct new bigraded invariants of a framed link in a 3-manifold as the pages of a spectral sequence modeled on the surgery exact triangle. The differentials count monopoles over families of metrics parameterized by permutohedra. We utilize a connection between the topology of link surgeries and the combinatorics of graph-associahedra. This also yields simple realizations of permutohedra and associahedra, as refinements of hypercubes. [ABSTRACT FROM AUTHOR]

For L a finite lattice, let $${\mathbb {C}(L) \subseteq L^2}$$ denote the set of pairs γ = ( γ, γ) such that $${\gamma_0 \prec \gamma_1}$$ and order it as follows γ ≤ δ iff γ ≤ δ, $${\gamma_{1} \nleq \delta_0,}$$ and γ ≤ δ. Let $${\mathbb {C}(L, \gamma)}$$ denote the connected component of γ in this poset. Our main result states that, for any $${\gamma, \mathbb {C}(L, \gamma)}$$ is a semidistributive lattice if L is semidistributive, and that $${\mathbb {C}(L, \gamma)}$$ is a bounded lattice if L is bounded. Let $${\mathcal{S}_{n}}$$ be the Permutohedron on n letters and let $${\mathcal{T}_{n}}$$ be the Associahedron on n + 1 letters. Explicit computations show that $${\mathbb {C}(\mathcal{S}_{n}, \alpha) = \mathcal{S}_{n-1}}$$ and $${\mathbb {C}(\mathcal {T}_n, \alpha) = \mathcal {T}_{n-1}}$$ , up to isomorphism, whenever α1 is an atom of $${\mathcal{S}_{n}}$$ or $${\mathcal{T}_{n}}$$ . These results are consequences of new characterizations of finite join-semidistributive and of finite lower bounded lattices: (i) a finite lattice is join-semidistributive if and only if the projection sending $${\gamma \in \mathbb {C}(L)}$$ to $${\gamma_0 \in L}$$ creates pullbacks, (ii) a finite join-semidistributive lattice is lower bounded if and only if it has a strict facet labelling. Strict facet labellings, as defined here, are a generalization of the tools used by Caspard et al. to prove that lattices of finite Coxeter groups are bounded. [ABSTRACT FROM AUTHOR]

Convex rank tests are partitions of the symmetric group which have desirable geometric properties. The statistical tests defined by such partitions involve counting all permutations in the equivalence classes. Each class consists of the linear extensions of a partially ordered set specified by data. Our methods refine existing rank tests of nonparametric statistics, such as the sign test and the runs test, and are useful for exploratory analysis of ordinal data. We establish a bijection between convex rank tests and probabilistic conditional independence structures known as semigraphoids. The subclass of submodular rank tests is derived from faces of the cone of submodular functions or from Minkowski summands of the permutohedron. We enumerate all small instances of such rank tests. Of particular interest are graphical tests, which correspond to both graphical models and to graph associahedra. [ABSTRACT FROM AUTHOR]

Abstract: This work is first concerned with some properties of the Young–Fibonacci insertion algorithm and its relation with Fomin''s growth diagrams. It also investigates a relation between the combinatorics of Young–Fibonacci tableaux and the study of Okada''s algebras associated to the Young–Fibonacci lattice. The original algorithm was introduced by Roby and we redefine it in such a way that both the insertion and recording tableaux of any permutation are conveniently interpreted as saturated chains in the Young–Fibonacci lattice. Using our conventions, we give a simpler proof of a property of Killpatrick''s evacuation algorithm for Fibonacci tableaux. It also appears that this evacuation is no longer needed in making Roby''s and Fomin''s constructions coincide. We provide the set of Young–Fibonacci tableaux of size n with a structure of graded poset called tableauhedron, induced by the weak order of the symmetric group, and realized by transitive closure of elementary transformations on tableaux. We show that this poset gives a combinatorial interpretation of the coefficients of the transition matrix from the analogue of complete symmetric functions to analogue of the Schur functions in Okada''s algebra associated to the Young–Fibonacci lattice. We prove a similar result relating usual Kostka numbers with four partial orders on Young tableaux, studied by Melnikov and Taskin. [Copyright &y& Elsevier]