In a highly influential paper, Bidigare, Hanlon and Rockmore showed that a number of popular Markov chains are random walks on the faces of a hyperplane arrangement. Their analysis of these Markov chains took advantage of the monoid structure on the set of faces. This theory was later extended by Brown to a larger class of monoids called left regular bands. In both cases, the representation theory of these monoids played a prominent role. In particular, it was used to compute the spectrum of the...

A simple idea used in many combinatorial algorithms is the idea of pivoting. Originally, it comes from the method proposed by Gauss in the 19th century for solving systems of linear equations. This method had been extended in 1947 by Dantzig for the famous simplex algorithm used for solving linear programs. From since, a pivoting algorithm is a method exploring subsets of a ground set and going from one subset σ to a new one σ′ by deleting an element inside σ and adding an element outside σ: σ′ = σv}  ∪  {u},...

Let ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ be the following algorithmic problem: Given a finite simplicial complex $K$ of dimension at most $k$, does there exist a (piecewise linear) embedding of $K$ into ${ℝ}^d$? Known results easily imply polynomiality of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2}$ ($k=1,2$; the case $k=1,d=2$ is graph planarity) and of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2k}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{d\to d}$ and ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{(d-1)\to d}$ are undecidable for each ${}_d\ge 5$. Our main result is NP-hardness of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{2\to 4}$ and, more generally, of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ for all $k$, $d$ with...

LVM and LVMB manifolds are a large family of non kähler manifolds. For instance, Hopf manifolds and Calabi-Eckmann manifolds can be seen as LVMB manifolds. The LVM manifolds have a natural action of a real torus and the quotient of this action is a polytope. This quotient allows us to relate closely LVM manifolds to the moment-angle manifolds studied by Buchstaber and Panov. Our aim is to generalize the polytope associated to a LVM manifold to the LVMB case and study the properties of this generalization....

We prove that the complement of a toric arrangement has the homotopy type of a minimal CW-complex. As a corollary we deduce that the integer cohomology of these spaces is torsionfree. We apply discrete Morse theory to the toric Salvetti complex, providing a sequence of cellular collapses that leads to a minimal complex.

For a simplicial complex $\Delta$ we study the behavior of its $f$- and $h$-triangle under the action of barycentric subdivision. In particular we describe the $f$- and $h$-triangle of its barycentric subdivision $\mathrm{sd}\left(\Delta \right)$. The same has been done for $f$- and $h$-vector of $\mathrm{sd}\left(\Delta \right)$ by F. Brenti, V. Welker (2008). As a consequence we show that if the entries of the $h$-triangle of $\Delta$ are nonnegative, then the entries of the $h$-triangle of $\mathrm{sd}\left(\Delta \right)$ are also nonnegative. We conclude with a few properties of the $h$-triangle of $\mathrm{sd}\left(\Delta \right)$.

Harary [10, p. 7] claims that Veblen [20, p. 2] first suggested to formalize simple graphs using simplicial complexes. We have developed basic terminology for simple graphs as at most 1-dimensional complexes. We formalize this new setting and then reprove Mycielski’s [12] construction resulting in a triangle-free graph with arbitrarily large chromatic number. A different formalization of similar material is in [15].