This paper initiates the explicit study of face numbers of matroid polytopes and their computation. We prove that, for the large class of split matroid polytopes, their face numbers depend solely on the number of cyclic flats of each rank and size, together with information on the modular pairs of cyclic flats. We provide a formula which allows us to calculate $f$-vectors without the need of taking convex hulls or computing face lattices. We discuss the particular cases of sparse paving matroids and rank two matroids, which are of independent interest due to their appearances in other combinatorial and geometric settings.

We propose and unify classes of different models for information propagation over graphs. In a first class, propagation is modelled as a wave, which emanates from a set of known nodes at an initial time, to all other unknown nodes at later times with an ordering determined by the arrival time of the information wave front. A second class of models is based on the notion of a travel time along paths between nodes. The time of information propagation from an initial known set of nodes to a node is defined as the minimum of a generalised travel time over subsets of all admissible paths. A final class is given by imposing a local equation of an eikonal form at each unknown node, with boundary conditions at the known nodes. The solution value of the local equation at a node is coupled to those of neighbouring nodes with lower values. We provide precise formulations of the model classes and prove equivalences between them. Finally, we apply the front propagation models on graphs to semi-supervised learning via label propagation and information propagation on trust networks.

Remixed Eulerian numbers are a polynomial q-deformation of Postnikov’s mixed Eulerian numbers. They arose naturally in previous work by the authors concerning the permutahedral variety and subsume well-known families of polynomials such as q-binomial coefficients and Garsia–Remmel’s q-hit numbers. We study their combinatorics in more depth. As polynomials in q, they are shown to be symmetric and unimodal. By interpreting them as computing success probabilities in a simple probabilistic process we arrive at a combinatorial interpretation involving weighted trees. By decomposing the permutahedron into certain combinatorial cubes, we obtain a second combinatorial interpretation. At $q=1$, the former recovers Postnikov’s interpretation whereas the latter recovers Liu’s interpretation, both of which were obtained via methods different from ours.

We investigate a recently devised polyhedral semantics for intermediate logics, in which formulas are interpreted in n-dimensional polyhedra. An intermediate logic is polyhedrally complete if it is complete with respect to some class of polyhedra. The first main result of this paper is a necessary and sufficient condition for the polyhedral completeness of a logic. This condition, which we call the Nerve Criterion, is expressed in terms of Alexandrov’s notion of the nerve of a poset. It affords a purely combinatorial characterisation of polyhedrally complete logics. Using the Nerve Criterion we show, easily, that there are continuum many intermediate logics that are not polyhedrally complete but which have the finite model property. We also provide, at considerable combinatorial labour, a countably infinite class of logics axiomatised by the Jankov–Fine formulas of ‘starlike trees’ all of which are polyhedrally complete. The polyhedral completeness theorem for these ‘starlike logics’ is the second main result of this paper.

We study $n$-vertex $d$-dimensional polytopes with at most one nonsimplex facet with, say, $d+s$ vertices, called almost simplicial polytopes. We provide tight lower and upper bound theorems for these polytopes as functions of $d,n$, and $s$, thus generalizing the classical Lower Bound Theorem by Barnette and the Upper Bound Theorem by McMullen, which treat the case where $s=0$. We characterize the minimizers and provide examples of maximizers for any $d$. Our construction of maximizers is a generalization of cyclic polytopes, based on a suitable variation of the moment curve, and is of independent interest.

We study a combinatorial problem that recently arose in the context of shape optimization: among all triangles with vertices $(0,0)$, $(x,0)$, and $(0,y)$ and fixed area, which one encloses the most lattice points from $\mathbb{Z}_{{>}0}^{2}$? Moreover, does its shape necessarily converge to the isosceles triangle $(x=y)$ as the area becomes large? Laugesen and Liu suggested that, in contrast to similar problems, there might not be a limiting shape. We prove that the limiting set is indeed non-trivial and contains infinitely many elements. We also show that there exist “bad” areas where no triangle is particularly good at capturing lattice points and show that there exists an infinite set of slopes $y/x$ such that any associated triangle captures more lattice points than any other fixed triangle for infinitely many (and arbitrarily large) areas; this set of slopes is a fractal subset of $[1/3,3]$ and has Minkowski dimension of at most $3/4$.

CoxIter is a computer program designed to compute invariants of hyperbolic Coxeter groups. Given such a group, the program determines whether it is cocompact or of finite covolume, whether it is arithmetic in the non-cocompact case, and whether it provides the Euler characteristic and the combinatorial structure of the associated fundamental polyhedron. The aim of this paper is to present the theoretical background for the program. The source code is available online as supplementary material with the published article and on the author’s website (http://coxiter.rgug.ch).

Supplementary materials are available with this article.

The multiplicity conjecture of Herzog, Huneke, and Srinivasan is verified for the face rings of the following classes of simplicial complexes: matroid complexes, complexes of dimension one and two, and Gorenstein complexes of dimension at most four. The lower bound part of this conjecture is also established for the face rings of all doubly Cohen–Macaulay complexes whose 1-skeleton's connectivity does not exceed the codimension plus one as well as for all $\text{(}d-1)$-dimensional $d$-Cohen–Macaulay complexes. The main ingredient of the proofs is a new interpretation of the minimal shifts in the resolution of the face ring $\mathbf{k}[\Delta ]$ via the Cohen–Macaulay connectivity of the skeletons of $\Delta $.

The face ring of a homology manifold (without boundary) modulo a generic system of parameters is studied. Its socle is computed and it is verified that a particular quotient of this ring is Gorenstein. This fact is used to prove that the algebraic g-conjecture for spheres implies all enumerative consequences of its far-reaching generalization (due to Kalai) to manifolds. A special case of Kalai’s conjecture is established for homology manifolds that have a codimension-two face whose link contains many vertices.

Cubical sets and their homology have been used in dynamical systems as well as in digital imaging. We take a fresh look at this topic, following Zariski ideas from algebraic geometry. The cubical topology is defined to be a topology in ${{\mathbb{R}}^{d}}$ in which a set is closed if and only if it is cubical. This concept is a convenient frame for describing a variety of important features of cubical sets. Separation axioms which, in general, are not satisfied here, characterize exactly those pairs of points which we want to distinguish. The noetherian property guarantees the correctness of the algorithms. Moreover, maps between cubical sets which are continuous and closed with respect to the cubical topology are precisely those for whom the homology map can be defined and computed without grid subdivisions. A combinatorial version of the Vietoris–Begle theorem is derived. This theorem plays the central role in an algorithm computing homology of maps which are continuous with respect to the Euclidean topology.