Hirsch polytopes with exponentially long combinatorial segments

Abstract

In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340–1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound $O(n2^d)$ for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound $n-d+1$ if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent but more local, by introducing the notions of monotonicity and conservativeness of dual paths in pure simplicial complexes. We use these definitions to investigate further properties of combinatorial segments. Besides recovering the two stated bounds, we show a refined bound for banner complexes, and study the behavior of the maximal length of combinatorial segments with respect to two usual operations, namely join and one-point suspension. Finally, we show the limitations of combinatorial segments by constructing pure normal simplicial complexes in which all combinatorial segments between two particular facets achieve the length $\Omega (n2^{d})$. This includes vertex-decomposable—therefore Hirsch—polytopes.

1 Introduction

One of the main open questions in polyhedral combinatorics is the so-called polynomial Hirsch Conjecture:

Is there an upper bound for the (combinatorial) diameter of the graph of every d-polyhedron with n facets that is polynomial in n and d?

Remember that it was conjectured by Hirsch in 1957 that $n-d$ is a valid upper bound. We say that a polytope or polyhedron is Hirsch if it satisfies this bound. Although the Hirsch Conjecture was disproved by Klee and Walkup [13] in the general case and by Santos [18] in the bounded case, the known counterexamples exceed the bound only by a small fraction (25 % in the unbounded case, 5 % in the bounded case, see [16, 18]). In contrast, the best upper bounds known are not polynomial. If we denote by H(d, n) the maximum diameter of d-dimensional polytopes with n facets, these bounds are:

$$\begin{aligned} H(d,n) \le \frac{2}{3}2^{d-3} n, \quad H(d,n) \le (n-d)^{\log _2 d }. \end{aligned}$$

(1)

The first bound is linear in fixed dimension. Except for a constant factor, which was an improvement by Barnette [3], this bound was first proved by Larman [14]. The second, quasi-polynomial bound, was first proved by Kalai and Kleitman [11], although the version we state is an improvement by Todd [20].

An approach to the question that has been attempted since long, starting with the introduction of abstract polytopes by Adler and Dantzig [2], is to generalize it to the setting of simplicial complexes. Here and in the rest of the paper, a pure simplicial complex C of dimension $d-1$ is a subset of $\left( {\begin{array}{c}[n]\\ d\end{array}}\right)$, where $\left( {\begin{array}{c}[n]\\ d\end{array}}\right)$ denotes the set of d-subsets of the set $[n]:=\{1,2,\dots , n\}$. The elements of [n] are called vertices and those of C are called facets. Two facets are adjacent if they differ in a single vertex. This defines a facet-adjacency graph (or dual graph) of C. The (dual) diameter of C is the diameter of this graph. A simplicial d-sphere is a simplicial complex whose underlying topological space is homeomorphic to a sphere of dimension d. See more details and basic concepts about simplicial complexes in Sect. 2.1.

As a motivating example, if P is a simple d-polytope with n facets labeled 1 to n and for each vertex v of P we call $F_v=\{i\in [n]: \text { the } i \hbox {-}\text {th facet contains} \,v\}$, then the collection $C:=\{F_v : v \text { a vertex of }P\}$ is a simplicial $(d-1)$-sphere and its facet-adjacency graph equals the graph of P. Observe that vertices and facets of C correspond, respectively, to facets and vertices of P. In fact, C is nothing but the face complex of the simplicial polytope dual to P.

Since it is known that H(d, n) is attained at a simple polytope, H(d, n) is bounded by the maximum diameter of dual graphs of all simplicial $(d-1)$-spheres with n vertices. It is hoped that generalizing the Hirsch question to arbitrary pure simplicial complexes may help in finding the right proof strategy. However, if one generalizes too much then exponential diameters arise:

Theorem A

(Criado and Santos [4, 19]) The maximum diameter of pure simplicial $(d-1)$-complexes with n vertices grows as ${\Theta (n^{d-1})}$, for every fixed d.

Hence, some condition is needed if one wants to have (hopes for) a polynomial upper bound. The standard consensus is to look only at normal complexes. That is, complexes in which between every two facets F, $F'$ there is a dual path (a path in the dual graph) consisting only of facets that contain $F\cap F'$. The adjective “normal” for these complexes is quite established if they are pseudomanifolds, in which case the condition admits a homological characterization (see e.g. [7, Sect. 4]). Without the pseudomanifold condition, the name has been used in [1, 19]. In the context of diameter bounds, pure simplicial complexes with this property have been called locally connected [2] and ultraconnected [10]. In fact, the abstract polytopes of Adler and Dantzig [2] are nothing but normal pseudomanifolds without boundary. The property arises also in the context of unfoldings of simplicial complexes [9, 15] under the name locally strongly connected.

Evidence that normality is the right condition to consider is that the two bounds for H(d, n) stated in Eq. (1) are still valid, with minor adjustments, for the diameters of all normal complexes. This was already known to Kalai and Kleitman [11], and it was recently highlighted by the work of Eisenbrand et al. [6], who considered an even more abstract setting and proved the two bounds in this setting. Their work, in fact, suggests the following conjecture, much stronger than the polynomial Hirsch Conjecture:

Conjecture

(Hähnle [8, Conjecture 7.0.5]) The diameter of every normal $(d-1)$-complex with n vertices is at most $(n-1)d$.

Normality also plays a role in Adiprasito and Benedetti’s proof of the (original) Hirsch bound for flag polytopes [1]. Indeed they prove the Hirsch bound for the diameter of every flag normal simplicial complex. In this paper we revisit one of the two proofs of this result given in [1] and explore what the proof implies for normal complexes that are not flag.

More precisely, Adiprasito and Benedetti introduce paths of certain types in dual graphs of pure complexes, that they call combinatorial segments. They then prove that:

• Between every pair of facets in a normal (not necessarily flag) complex there is always a combinatorial segment (see Corollary 2.9).

• Combinatorial segments in flag normal complexes are nonrevisiting, hence they satisfy the Hirsch bound (see Sect. 3.1).

Hereafter, we recast these proofs and the concept of combinatorial segment. In Sect. 2 we introduce the notion of monotone conservative paths by extracting the key properties of Adiprasito and Benedetti’s combinatorial segments. Although the two concepts are equivalent (see Theorem 2.12) our formulation is local: a dual path $F_0,\dots ,F_N$ in a simplicial complex C is monotone and conservative if each step from a facet $F_{i-1}$ to the next facet $F_i$ satisfies certain conditions. In contrast, the original definition of combinatorial segment goes by imposing global conditions on the path via a double recursion: on the vertex-distance between $F_0$ and $F_N$ and on the dimension of C. Here, we call vertex-distance between two subsets of vertices of C the distance between them in the 1-skeleton (the “usual” graph, whose vertices and edges are the 0-faces and 1-faces) of C. We achieve this local, yet equivalent, definition by considering the vertex set of each facet along the path to be ordered, so that the ordering encodes the recursions. The property of being monotone somehow translates the local optimality of a step while conservativeness allows us to keep some control on our paths.

In Sect. 3 we rephrase the proof of the Hirsch bound for flag normal complexes in the language of monotone conservative paths. We also include a proof of the Larman bound for normal complexes in this language, and we generalize the bound to the so-called banner complexes:

Theorem B

(Adiprasito and Benedetti [1], see Theorem 3.5 and Corollary 3.2) The length of any monotone conservative path in a $(d-1)$-dimensional pure normal complex C on n vertices ($d\ge 2$) is at most $n2^{d-2}$. Moreover, if C is a pseudomanifold, the same statement holds with the bound $n2^{d-3}$; and if C is flag, the same statement holds with the Hirsch bound $n-d$.

Theorem C

(Novik 2013, unpublished, see Theorem 3.9) Let $k\ge 2$. If C is a k-banner pure normal complex on n vertices, then between any two distinct facets of C there is a monotone conservative path of length bounded by $n2^{k-2}$.

The property of being k-banner is a generalization of flagness, which is itself equivalent to 2-banner (see precise definitions in Sect. 3.3). Theorem C interpolates (modulo a factor of 2 and an additive term of d, respectively) between two of the bounds of Theorem B: Since every $(d-1)$-complex is $(d+1)$-banner, we retrieve the bound $2^{d-1}n$ for arbitrary normal complexes. On the other extreme, substituting k by 2 into the theorem gives a bound of n for flag normal complexes.

In Sect. 4 we study how combinatorial segments behave with respect to classic operations on simplicial complexes, and we show their limitations by constructing exponentially long combinatorial segments in some normal complexes. We do this in two versions; first in a topological ball, and then in the boundary complex of a vertex-decomposable simplicial polytope:

Theorem D

(See Theorem 4.8) For every $d\ge 2$ and every $N\ge 4$ there is a simplicial d-polytope with $N+\Theta (d^2)$ vertices with vertex-decomposable boundary complex and two facets in it such that every monotone conservative path between them has length at least $2^{d-3} N$.

Vertex-decomposability is interesting in this context since vertex-decomposable simplicial polytopes are known to satisfy the Hirsch bound [17, Corollary 2.11]. Observe that the paths mentioned in this theorem are within a factor of $1+\varepsilon$ from the upper bound of Theorem B, with $\varepsilon$ going to zero as N goes to infinity.

2 Combinatorial segments and monotone conservative paths

2.1 Preliminaries on simplicial complexes

A simplicial complex, or simply a complex, on a vertex set V is a collection C of subsets of V such that $f\subset g\in C$ implies $f\in C$. The elements of C are called faces. The dimension of a face f is $|f|-1$. If all its facets (that is, inclusion maximal faces) have d elements, C is said to be pure of dimension $d-1$, and sometimes called a $(d-1)$-complex. When describing a complex C we usually only list its maximal faces. For example, for $f\subset V$ and $v\in V$ we denote $\{f\}$ and $\{v\}$ the complexes $\{f': f'\subset f\}$ and $\{\{v\},\emptyset \}$, respectively. Observe that from this perspective a pure simplicial $(d-1)$-complex is nothing but an arbitrary subset of $\left( {\begin{array}{c}V\\ d\end{array}}\right)$. A minimal nonface of a complex is a nonempty set of its vertices which is not a face but such that all its proper subset are faces. A complex C is called flag if all its minimal nonfaces are 1-dimensional, that is edges. Equivalently, a complex is flag if it is the clique complex of its 1-skeleton.

The star and link of a face f in C are the following subcomplexes of C, where $\sqcup$ denotes the disjoint union:

$$\begin{aligned} \mathrm{st}_C(f)&:=\{f' \in C : f\cup f' \in C \}, \\ {{\mathrm{lk}}}_C(f)&:=\{f' \in C : f \sqcup f' \in C\} = \{f' \in V{\setminus } f : f \cup f' \in C\}. \end{aligned}$$

The facet-adjacency graph or dual graph of C has the facets of C as nodes with two facets F and $F'$ being adjacent in the graph if they differ by a single vertex. A pure simplicial complex C is called normal if between every two facets F, $F'$ there is a dual path (a path in the dual graph) consisting only of facets that contain $F\cap F'$. That is, if the star of every face has a connected dual graph. Equivalently, if the link of every face of codimension at least two is connected [9, Lemma 3.1.2]. A pure simplicial complex C is called a pseudomanifold if every codimension-one simplex lies in either 1 or 2 facets. The codimension-one simplices lying in only one facet form the boundary of C.

Finally, to any complex C one can associate a topological space, unique up to homeomorphism, as follows: for each face F of dimension k of C consider a geometric k-simplex $S_F$ (the convex hull of $k+1$ affinely independent points in some $\mathbb {R}^N$), and label the vertices of $S_F$ by those of F. Then, glue faces of the collection of disjoint simplices $\{S_F : F\in C\}$ as indicated by their vertex labels. The topological space so obtained is called the topological realization of C. We say that the complex C is a simplicial d-ball (resp. simplicial d-sphere) or simply a d-ball (resp. d-sphere) if its topological realization is homeomorphic to a ball (resp. sphere) of dimension d.

Although our main interest is in (the diameter of) the dual graph of C, we use also the distance in the “usual graph” (or 1-skeleton) of C, whose vertices and edges are the 0-faces and 1-faces of C. We refer to it as the vertex-distance between two vertices u and v of C and denote it ${{\mathrm{vdist}}}_C(u,v)$. For two sets of vertices S and $S'$ we denote

$$\begin{aligned} {{\mathrm{vdist}}}_C(S,S'):= \min _{u\in S, v\in S'} {{\mathrm{vdist}}}_C(u,v), \end{aligned}$$

with the standard convention that if one or both of S and $S'$ are empty then the minimum is $+\infty$. If $\dim (C)=0$, we also take the convention that for nonempty sets S and $S',{{\mathrm{vdist}}}_C(S,S')=0$ if $S\cap S'\ne \emptyset$, and ${{\mathrm{vdist}}}_C(S,S')=1$ otherwise.

2.2 Monotone conservative paths

The following recursive definition is crucial in order to define monotonicity and conservativeness of paths.

Definition 2.1

Let $F=(v_1,\dots ,v_d)$ be a facet of a pure $(d-1)$-dimensional simplicial complex C with its vertices given in a specific order. We call this an ordered facet. Let S be a subset of vertices of C, referred to as the target set. The vector of distances $\Lambda =(\lambda _1,\dots ,\lambda _d)$ of F with respect to S is defined as follows:

• $\lambda _1:= {{\mathrm{vdist}}}(v_1, S)$.

• $(\lambda _2,\dots ,\lambda _d)$ is the vector of distances of $F{\smallsetminus }v_1$ with respect to $S'$ in ${{\mathrm{lk}}}_C(v_1)$, where $S'$ is the following subset of the vertex set of ${{\mathrm{lk}}}_C(v_1)$:

  $$\begin{aligned} S':= {\left\{ \begin{array}{ll} \{v \in V_1 : {{\mathrm{vdist}}}_C(v,S) = {{\mathrm{vdist}}}_C(v_1, S)-1\} &{} \quad \text {if } v_1\not \in S,\\ S\cap {{\mathrm{lk}}}_C(v_1) &{}\quad \text {if } v_1\in S. \end{array}\right. } \end{aligned}$$

We say the ordering is admissible with respect to S if $\lambda _1={{\mathrm{vdist}}}_C(v_1,S)={{\mathrm{vdist}}}_C(F,S)$ and $F{\smallsetminus }v_1$ (with the induced ordering) is admissible with respect to $S'$ in ${{\mathrm{lk}}}_C(v_1)$.

Example 2.2

Consider the pure flag 2-dimensional complex given in Fig. 1, with target set $S=\{s_1,s_2\}$. The ordered facet $F_1=(a_1,a_2,a_3)$ is not admissible, whereas the ordered facet $F_2=(b_1,b_2,b_3)$ and $F_3=(c_1,c_2,c_3)$ are admissible with respect to S. The facet $F_1$ could be admissible with respect to S if endowed with other orderings, as $(a_2,a_3,a_1)$ for instance. The vectors of distances of the facets $F_1,F_2$ and $F_3$ are (5, 0, 0), (2, 1, 1) and $(0,0,\infty )$ respectively. In particular, it is possible to have infinite values in a vector of distances.

Fig. 1

Examples of admissible and nonadmissible ordered facets in a 2-dimensional complex

We are primarily interested in the case where S is a facet, but recursiveness of the definition forces us to consider more general target sets. Observe that the definition may even make the new target set $S'$ obtained from S be empty, in which case all entries in the vector of distances will be infinite from that point on. The following statement shows that this never happens in a normal complex, if the initial target set is a facet.

Lemma 2.3

Let C be a normal $(d-1)$-complex, S be a nonempty set of vertices of C, and $F=(v_1, \dots , v_d)$ be an ordered facet of C. If F is admissible with respect to S and one of the following conditions is true

• $F\cap S=\emptyset$,

• S is a face of C not strictly contained in F,

then the vector of distances $\Lambda =(\lambda _1,\dots ,\lambda _d)$ from F to S has no infinite entry.

Proof

We use induction on the dimension $d-1$ of C. For $d=1$, since $\dim C=0$, in both cases the vector of distances has a single entry which is either zero or one. Indeed the set F is a singleton, and S is a nonempty set. For $d>1$, the entry $\lambda _1$ of the vector of distances is finite since S is nonempty and C is normal thus has connected 1-skeleton. Notice that the simplicial complex C being pure and normal ensures that ${{\mathrm{lk}}}_C(v_1)$ is also pure, normal and of dimension one less. Further, as the ordering on F is admissible with respect to S, so is the ordering on $F{\smallsetminus }v_1$ with respect to $S'$. Suppose first that $F\cap S=\emptyset$. Because the ordering on F is admissible with respect to S, the vertex $v_1$ is at smallest (and nonzero) vertex-distance of S in the facet F. Therefore the facet $F{\smallsetminus }v_1$ and the set $S'$ in Definition 2.1 are disjoint. Suppose now that S is a face of C such that $v_1\in S$. In this case $S'=S\cap {{\mathrm{lk}}}_C(v_1)$ is a face of ${{\mathrm{lk}}}_C(v_1)$ which is not strictly contained in $F{\smallsetminus }v_1$. In both cases, the induction hypothesis ensures that the vector $(\lambda _2,\dots ,\lambda _d)$ has no infinite entry. $\square$

The previous proof also shows that if F is admissible with respect to S and the vector of distances contains some zero, then all zeroes are at the beginning of the vector. That is to say: no entry of the vector of distances can be zero if a previous entry is nonzero.

We now introduce the main definitions used in this article.

Definition 2.4

Let C be a pure and normal complex, S be a nonempty target set of vertices of C, and $\Gamma =[F_0,\dots ,F_N]$ be a path of ordered facets in the dual graph of C.

• (1) We say that $\Gamma$ is (combinatorially) monotone towards S if the sequence $(\Lambda _0,\dots ,\Lambda _N)$ of vectors of distances from its facets to S is lexicographically decreasing. That is, $\Lambda _i$ is lexicographically smaller than $\Lambda _{i-1}$ for every $i=1,\dots ,N$.

• (2) For each $i=1,\dots ,N$ we call index of the step from $F_{i-1}$ to $F_i$ in $\Gamma$ the minimum k for which $v_k\ne v'_k$, where $F_{i-1}=(v_1,\dots ,v_d)$ and $F_{i}=(v'_1,\dots ,v'_d)$. When there is no ambiguity on the path $\Gamma$ that we are considering we call it the index of $F_i$. We say that the step from $F_{i-1}$ to $F_i$, is conservative towards S if the following two things happen:

  • $F_{i-1}{\smallsetminus }F_i$ is the last vertex in the ordering of $F_{i-1}$. That is, $F_i$ keeps the initial vertices of $F_{i-1}$ as much as possible.

  • $F_i$ is admissible with respect to S and it has the maximum index among all possible choices of admissible reorderings of $F_i$. That is, $F_i$ tries to keep the order established in $F_{i-1}$ as much as admissible.

  We say that $\Gamma$ itself is conservative towards S if $F_0$ is admissible and all the steps of $\Gamma$ are conservative towards S.

Example 2.5

Consider the pure flag 2-dimensional complex given in Fig. 2, with target set $S=\{a_8\}$. The vector of distances of the ordered facet $F=(a_1,a_2,a_3)$ is (2, 2, 1) and is admissible with respect to S. All vectors of distances of the ordered facet $G_1=(a_5,a_1,a_3)$, $G_2=(a_1,a_5,a_3)$, $H_1=(a_4,a_1,a_2)$ and $H_2=(a_1,a_4,a_2)$ are (2, 1, 1) and are admissible with respect to S. The step $[F,G_1]$ is monotone, but does not satisfy either conditions of conservativeness: $a_2$ is not the last vertex of F and $G_1$ does not have maximum index. The step $[F,H_1]$ is monotone but not conservative: $a_3$ is the last vertex of F, but $H_1$ is not of maximum index. The step $[F,G_2]$ is monotone but not conservative: $G_2$ has maximum index, but $a_2$ is not the last vertex of F. The step $[F,H_2]$ is monotone and conservative: $a_3$ is the last vertex of F and $H_2$ has maximum index. Note that these four steps form initial segments of shortest paths in the dual graph from F to S, but only one of them is monotone and conservative.

To obtain a nonmonotone but conservative step, consider the complex $\big \{\{1,2\},\{1,3\},\{1,4\}\big \}$ with $F=(1,2)$, $G=(1,3)$, and $S=\{4\}$. The path [F, G] is not monotone but is conservative.

Fig. 2

A 2-dimensional flag simplicial complex having monotone and nonconservative paths

Remark 2.6

In a conservative step $[F_{i-1},F_i]$ towards a target set S, the index somehow denotes the “depth” at which the step occurs in the recursive definition.

It is clear from this definition that for a path $\Gamma$ of ordered facets in the dual graph and a target set S,

• if $\Gamma$ is monotone (resp. conservative) towards S, then any subpath of $\Gamma$ is also monotone (resp. conservative) towards S,

• if $\Gamma _1$ and $\Gamma _2$ are monotone (resp. conservative) towards S and the last ordered facet in $\Gamma _1$ equals the first one in $\Gamma _2$, then the concatenation of $\Gamma _1$ and $\Gamma _2$ is monotone (resp. conservative) towards S.

Define the anchor of an ordered facet to be its first vertex. The anchors along a monotone path towards S form a vertex-path in the 1-skeleton of C along which the distance to S decreases. In particular, they form a shortest path between the first and last anchor. Notice that in a monotone and conservative path $\Gamma$ from F towards S, the simplices with the same anchor $x_0$ form a subpath $\Gamma _0$ of $\Gamma$. Moreover, removing $x_0$ from every facet in the path $\Gamma _0$ produces a monotone conservative path $\Gamma '_0$ in ${{\mathrm{lk}}}_C(x_0)$ towards the set $\{x\in V : {{\mathrm{vdist}}}_C(x,x_0)=1,{{\mathrm{vdist}}}_C(x,S) = {{\mathrm{vdist}}}_C(x_0,S)-1\}$ which is the set $S'$ of Definition 2.1.

We now show the existence of monotone conservative paths in any pure normal complex, and bound their lengths. The following theorem deals with the existence part, up to the (immediate) existence of admissible orderings.

Theorem 2.7

Let C be a pure and normal complex, S be a nonempty target set, and $F_0$ be an ordered facet of C. If $F_0\cap S=\emptyset$ and $F_0$ is admissible with respect to S, then there exists an ordered facet $F_1$ adjacent to $F_0$ such that the step $[F_0,F_1]$ is monotone and conservative.

Proof

Lemma 2.3 ensures that all entries in the vector of distances of $F_0$ are finite, so that we do not need to define any comparison convention on potential infinite values.

The proof works by induction on the dimension $d-1$ of C, the case $d=1$ being clear.

Let us also deal with the case $d=2$ separately. In this case, C is a graph and $F_0$ is an ordered edge (u, v). The vector of distances is (a, 1), where $a\ge 1$ is the distance from u to S in the graph. Simply take $F_1=(w,u)$, where w is any neighbor of u at distance $a-1$ from S.

For arbitrary d, let $F_0=\{v_1,\dots , v_d\}$ (in this order) and let $F'_0=\{v_2,\dots , v_{d}\}=F_0{\smallsetminus }v_1$. Observe that (as in the proof of Lemma 2.3) the condition $F_0\cap S=\emptyset$ is inherited into $F'_0 \cap S' = \emptyset$, where

$$\begin{aligned} S'=\{v \in {\text {vertices}}({{\mathrm{lk}}}_C(v_1)) : {{\mathrm{vdist}}}_C(v,S) = {{\mathrm{vdist}}}_C(v_1, S)-1\} \end{aligned}$$

is as in the definition of admissibility. In particular the inductive hypothesis implies that there is an ordered facet $F'_1$ containing $F'_0{\smallsetminus }\{v_d\}$ such that (for a suitable ordering for $F'_1$) the step $[F'_0,F'_1]$ is monotone and conservative from $F_0$ towards $S'$ in ${{\mathrm{lk}}}_{v_1}(C)$. Let $F_1=\{v_1\}\cup F'_1$ considered, for now, with $v_1$ as the first vertex, followed by the rest in the order of $F'_1$. Then:

• The vector of distances of $F_1$ with respect to S has the same first entry as that of $F_0$, and the remaining entries are lexicographically smaller than those of $F_0$ by inductive hypothesis. Thus, $[F_0,F_1]$ is monotone.

• Again by inductive hypothesis, $F_{0}{\smallsetminus }F_1$ is the last vertex in the ordering of $F_0$.

If ${{\mathrm{vdist}}}(F_1,S) = {{\mathrm{vdist}}}(v_1,S)$, the ordering of $F_1$ is admissible and, by inductive hypothesis, it has the maximum index among admissible orderings; hence $[F_0,F_1]$ is admissible and conservative. If ${{\mathrm{vdist}}}(F_1,S) < {{\mathrm{vdist}}}(v_1,S)$, the first vertex of any admissible ordering of $F_1$ cannot be $v_1$, therefore the index of this step has to be 0. Then choosing any reordering for $F_1$ that is admissible makes the step $[F_0,F_1]$ conservative. It is also still monotone since the first entry of the vector of distances of $F_1$ is then smaller than the first entry of the vector of distances of $F_0$. $\square$

Observe that the reordering of $F_1$ in the last part of the previous proof produces a change of anchor, from $v_1$ to $v'_1$. In fact, every change of anchor is produced by such a reordering. When an anchor is changed in the step from $F_0$ to $F_1$ (say from an anchor x to an anchor y), the vertex x is still in the new facet $F_1$ because the vertex in $F_0{\smallsetminus }F_1$ must be the last vertex in the order of $F_0$. So, the change of anchor is not due to the disappearance of x from the facet, but rather to the fact that x is no longer a closest vertex to S in $F_1$ and a reordering is needed.

Corollary 2.8

Let C, S and $F_0$ be as in Theorem 2.7. There exists a monotone conservative path towards S starting at $F_0$ and ending in a facet that meets S.

Proof

If $F_0$ meets S then $F_0$ alone is the desired path. If $F_0\cap S=\emptyset$ then we apply Theorem 2.7, which gives us an $F_1$ to start the path. $\square$

Corollary 2.9

Let C, S and $F_0$ be as in Theorem 2.7. If S is the vertex set of a facet, then there is a monotone conservative path towards S starting at $F_0$ and with S as its last facet.

Proof

By the previous corollary, there is no loss of generality in assuming $F_0\cap S\ne \emptyset$. That is, $v_1\in S$. Now, $S':=S{\smallsetminus }\{v_1\}$ is a facet in ${{\mathrm{lk}}}_{C}(v_1)$. By induction on the dimension, there is a monotone path in ${{\mathrm{lk}}}_{C}(v_1)$ from $F'_0:=F_0{\smallsetminus }\{v_1\}$ which is conservative towards $S':=S{\smallsetminus }\{v_1\}$ and ending in $S'$. Adding $v_1$ as the first vertex in all facets of that path gives the desired path from $F_0$ to S. $\square$

Theorem 2.7 also has the following consequence:

Proposition 2.10

In a pseudomanifold (with or without boundary), a conservative path is automatically monotone.

Proof

Let $[F_0,F_1]$ be a conservative step in a pseudomanifold. If $F_0\cap S\ne \emptyset$, then we induct on the dimension, by taking the link of the first vertex $v_1$ of $F_0$, which is still a pseudomanifold. So we can assume that $F_0\cap S = \emptyset$.

By Corollary 2.9, from $F_0$ there is a monotone and conservative step to a certain facet $F'_1$. Now, since the definition of conservativeness determines which vertex of $F_0$ is to be removed, the complex being a pseudomanifold implies that $F_1=F'_1$ up to reordering. Being conservative implies that the first vertex in which the orderings of $F_1$ and $F'_1$ differ is also the first vertex in which they differ from $F_0$, and that the corresponding entry in the vector of distances of $F_1$ and $F'_1$ is smaller than the same entry in the vector of distances of $F_0$. Hence, the step $[F_0,F_1]$ is monotone. $\square$

2.3 Combinatorial segments as monotone conservative paths

We now relate these concepts with the notion of combinatorial segment by Adiprasito and Benedetti [1]. The following definition is taken from [19].

Definition 2.11

A dual path $\Gamma =[F_0,\dots ,F_N]$ with $x_0\in F_0$ in a simplicial $(d-1)$-complex C is a combinatorial segment from a facet F to a set S anchored at the vertex $x_0$ if it satisfies the following recursive definition:

• (1) if $F_0\cap S\ne \emptyset$, then $N=0$,

• (2) if $d=1$ and $F_0\cap S=\emptyset$, then $N=1$ and $\Gamma =(\{x_0\},\{v\})$ with $v\in S$,

• (3) if $d>1$ and $F_0\cap S=\emptyset$, then:

  • (a) the facet $F_N$ is the unique facet of $\Gamma$ intersecting S,

  • (b) the vertex $x_0$ realizes the vertex distance between $F_0$ and S, that is${{\mathrm{vdist}}}_C(x_0,S)={{\mathrm{vdist}}}_C(F_0,S)$. Let $\ell ={{\mathrm{vdist}}}_C(F_0,S)$, let $k=\min \{i\in [N]|{{\mathrm{vdist}}}_C(F_i,S)<\ell \}$ and let y be the unique vertex in $F_k$ such that ${{\mathrm{vdist}}}_C(\{y\},S)=\ell -1$. Then $x_0\in F_0\cap \dots \cap F_k$ and the link $\Gamma '_1$ of $x_0$ in the path $\Gamma _1=(F_0,F_1,\dots ,F_k)$ is a combinatorial segment in ${{\mathrm{lk}}}_C(x_0)$ from the facet $F_0{\smallsetminus }x_0$ to the set of neighbors of $x_0$ being at vertex-distance $\ell -1$ from S in C (that is the set $S'$ of Definition 2.1 of admissibility),

  • (c) the path $\Gamma _2=[F_k,\dots ,F_N]$ is a combinatorial segment from $F_k$ to S anchored at y.

In [19], the anchor of the path $\Gamma$ is the vertex $x_0$. In our definition $x_0$ is only the “first anchor” of the path, after which come all the anchors in the path $\Gamma _2$. Anchors, in the sense of [19], are called pearls in [1].

Observe that the facets of a combinatorial segment come with an implicit ordering of their vertices. For the facets in $\Gamma _1$, except the last one $F_k$, $x_0$ is the first vertex in the ordering and the rest of the ordering is obtained by induction on the dimension. For facets in $\Gamma _2$, the ordering is obtained by induction on N (or, alternatively, on the vertex-distance from $F_0$ to S). These orderings make combinatorial segments and monotone conservative paths essentially equivalent:

Theorem 2.12

Let C be a pure simplicial complex, S be a nonempty set of vertices of C, $\Gamma =[F_0,\dots ,F_N]$ be a dual path in C in which $F_N$ is the only facet intersecting S. The path $\Gamma$ is a combinatorial segment from $F_0$ to S if and only if it is monotone and conservative towards S.

Proof

We make the proof follow the inductive definition of combinatorial segment. Observe that it has a double induction, first on the dimension and then on N (or, alternatively, on ${{\mathrm{vdist}}}(F_0,S)$).

In case (1) of the definition, the result trivially holds. In case (2) observe that for $d=1$ the “vector of distances” between a vertex F and a set S is just a number, zero if $F\in S$ and one if not. Since monotonicity implies these numbers to be decreasing, a monotone path must have $N=1$ and be of the form $[\{x_0\},\{v\}]$ with $v\in S$.

So suppose that $F_0\cap S=\emptyset$ and that $d>1$. Assume for now that $\Gamma$ is a combinatorial segment from $F_0$ to S. Then we already know that the path $\Gamma _2$ of the definition is also a combinatorial segment from $F_k$ to S, implying by induction that any step of this path is both monotone and conservative towards S. By the induction hypothesis, since the path $\Gamma '_1$ of the definition is a combinatorial segment, it is monotone and conservative towards the set $S'$ of Definition 2.1. The vectors of distances in the path $\Gamma _1$ are all, except for the one in the last facet $F_k$, obtained from those in the path $\Gamma '_1$ by adding the distance of the anchor $x_0$ as first coordinate, so that $\Gamma _1$ is still monotone. Moreover, the dual graph of ${{\mathrm{lk}}}_C(x_0)$ is the same as that of $\mathrm{st}_C(x_0)$, so that conservativeness is also preserved from $\Gamma _1$ to $\Gamma '_1$ and conversely, except perhaps for the last step. Monotonicity in the step $[F_{k-1},F_k]$ is clear, since ${{\mathrm{vdist}}}(y,S) < {{\mathrm{vdist}}}(x_0,S)$. Let us check the conditions for conservativeness:

• The vertex in $F_{k-1}{\smallsetminus }F_k$ is the last vertex of $F_{k-1}$ because it is the last vertex in $F'_{k-1}:=F_{k-1}{\smallsetminus }\{x_0\}$ (induction on the dimension).

• The ordering in $F_k$ is admissible and has maximum index among admissible ones because $\Gamma _2$ is monotone and conservative, by induction on N.

Since $\Gamma _2$ is also monotone and conservative, the path $\Gamma$ is monotone and conservative.

Conversely, assume now that $\Gamma$ is monotone and conservative towards S. Let $x_0$ be the first anchor of $\Gamma$ and $[F_0,\dots ,F_{k-1}]$ be the part of $\Gamma$ anchored at $x_0$ and let $\Gamma _1=[F_0,\dots ,F_{k}]$. Observe that, by conservativeness, $F_k$ still contains $x_0$. Moreover, the link $\Gamma '_1$ of $x_0$ in $\Gamma _1$ is monotone and conservative towards $S'$ except for the last step. In this last step, the order on $F_k$ in $\Gamma$ cannot be restricted to an ordering of $F'_k:=F_k{\smallsetminus }\{x_0\}$ in ${{\mathrm{lk}}}_{C}(x_0)$, since $x_0$ is not the first vertex in $F_k$. Nevertheless the same arguments as above still apply and any admissible ordering on $F_k$ with respect to $S'$ with maximum index guarantees monotonicity and conservativeness for the step $[F_{k-1},F_k]$. So $\Gamma '_1$ is a combinatorial segment to $S'$ by the induction hypothesis. Moreover, the path $\Gamma _2=[F_k,\dots ,F_N]$ is a subpath of $\Gamma$ and so is monotone and conservative towards S, and so is a combinatorial segment from $F_k$ to S by induction on N. Thus $\Gamma$ is a combinatorial segment from $F_0$ to S in C. $\square$

Adiprasito and Benedetti also define a combinatorial segment “between two facets” as follows: Let $F,F'$ be two facets of C and let $\Gamma$ be a combinatorial segment from the facet F to the set of vertices $F'$. Then, only the last facet $F''$ in $\Gamma$ intersects $F'$, and $F''$ and $F'$ intersect in a single vertex x. Since $F''{\smallsetminus }x$ and $F'{\smallsetminus }x$ are both facets in ${{\mathrm{lk}}}_C(x)$ we can recursively define a combinatorial segment from the facet F to the facet $F'$ to be $\Gamma$ followed by $x*\Gamma '$, where $\Gamma '$ is a combinatorial segment in ${{\mathrm{lk}}}_C(x)$ from the facet $F''{\smallsetminus }x$ to the facet $F'{\smallsetminus }x$.

The following result follows easily:

Corollary 2.13

Let $F,F'$ be facets in a normal complex C. A combinatorial segment from F to $F'$ is a monotone and conservative path that starts in F towards the target set $F'$ and finishes in $F'$.

Proof

By Theorem 2.12, the combinatorial segment starting at F and ending at the first facet intersecting $F'$ at the vertex x is monotone and conservative towards the vertex set of $F'$. By induction on the dimension, we join x to the monotone and conservative path in the link of x and concatenate it to the previous path. The result is clearly monotone and conservative. $\square$

3 Upper bounds for the length of monotone conservative paths

The motivation for the definition of combinatorial segment was the proof of the Hirsch upper bound for flag normal complexes, and it gave as a byproduct the linear bound in fixed dimension. In this section we rework these two bounds in the language of monotone conservative paths. We also include a bound for banner complexes that interpolates between the two.

3.1 Hirsch bound for flag normal complexes

A path $\Gamma = [F_0,\dots , F_N]$ in a complex C is said to be nonrevisiting if for every vertex v, the facets of $\Gamma$ containing v form a subpath of $\Gamma$. That is to say, if $v\in F_i\cap F_j$ then $v\in F_k$ for every $k\in [i,j]$. It is easy to show (see below) that the length of nonrevisiting paths in a pure complex cannot exceed the Hirsch bound $n-d$.

Lemma 3.1

([1, Section 3], see also [19, Corollary 4.19]) Let C be a flag normal complex, x and y be two consecutive anchors, with x coming first, along a monotone conservative path $\Gamma =[F_0,\dots ,F_N]$. If z is a neighbor of y that belongs to a facet $F_i$ anchored at x, then z belongs to all facets between $F_i$ and the first one anchored at y.

Proof

The proof goes by induction on the dimension of C and is obvious in dimension 1. Now in higher dimension, we can assume without loss of generality that x and y are the only two anchors in the path, that $i=0$, that y first appears in $F_N$, and that $x\ne z$. Consider the monotone and conservative path $\Gamma '$ obtained from $\Gamma$ in ${{\mathrm{lk}}}_{C}(x)$. Since y is an anchor of $\Gamma$, it is in the target set of $\Gamma '$ and $\Gamma '$ finishes at a facet containing y. Since $\{x,y\},\{x,z\}$ and $\{y,z\}$ are edges of C, which is flag, the set $\{x,y,z\}$ is a face of C so that $\{y,z\}$ is in ${{\mathrm{lk}}}_{C}(x)$. The vertex z is in the first facet of $\Gamma '$ and at distance 1 of the target set. So either it is the anchor of $\Gamma '$ and we are done, or the first anchor of $\Gamma '$ then has to be at distance 1 of y to give an admissible order. Call this anchor $x'$. Then, $\Gamma '$ satisfies all the conditions in the statement, with respect to the vertices $x'$, y and z. Since flagness is preserved under taking links, we can apply the induction hypothesis in ${{\mathrm{lk}}}_{C}(x)$. Thus, z is in all facets of the path $\Gamma '$, and so of the path $\Gamma$. $\square$

Corollary 3.2

([1, Section 3], see also [19, Corollary 4.20]) Every monotone and conservative path in a flag normal complex is a nonrevisiting path. In particular, its length is bounded by the Hirsch bound.

Proof

Let $\Gamma =[F_0,\dots ,F_N]$ be a monotone conservative path towards a target set S in a flag normal complex C. The proof is by a double induction on the dimension of C and the length N of the path $\Gamma$. For dimension $d=1$ or for $N=1$, the result is clear.

Now, assume $d>1$ and $N>1$. Let x be the first anchor of $\Gamma$ and y be the second anchor, if any. We call $\Gamma '$ the path $[F_0{\smallsetminus }\{x\},\dots ,F_k{\smallsetminus }\{x\}]$ where $[F_0,\dots ,F_{k-1}]$ is the part of $\Gamma$ anchored at x. By induction on the dimension, the monotone and conservative path $\Gamma '$ in ${{\mathrm{lk}}}_{C}(x)$ is nonrevisiting. By induction on N, the tail $\Gamma _2:=[F_k,\dots ,F_N]$ of $\Gamma$ once x is not an anchor is nonrevisiting. So it only remains to show that, if there is a vertex z used in $\Gamma '$ and $\Gamma _2$, then it has to be contained in the last facet of $\Gamma '$, where a change of anchor occurs. Since z is a vertex in ${{\mathrm{lk}}}_C(x)$, it is also a neighbor of x in C. Moreover x and y are consecutive anchors of $\Gamma$ and so are neighbors in C. Set $\ell ={{\mathrm{vdist}}}_C(y,S)$ and suppose, for the sake of contradiction, that z is not a neighbor of y. Since y is the anchor of $\Gamma$ following x, we have ${{\mathrm{vdist}}}_C(x,S)=\ell +1$, and so ${{\mathrm{vdist}}}_C(z,S)\ge \ell +1$ because of admissibility. Since z appears in a facet of $\Gamma _2$, the anchor of this facet has to be at vertex-distance at most $\ell -1$ from S. Indeed it cannot be y and the sequence of anchors forms a shortest vertex path to S. Since z is a neighbor of this anchor in C, we have ${{\mathrm{vdist}}}_C(z,S)\le \ell$; a contradiction. Hence y and z are neighbors in C; and Lemma 3.1 applies to C and x, y and z. Thus z belongs to the last facet of $\Gamma '$; which concludes the proof. $\square$

Remark 3.3

Both the monotonicity and conservativeness assumptions are necessary in Corollary 3.2. On the one hand, consider the nonmonotone but conservative path obtained in Example 2.5 in the complex $C=\left\{ \{1,2\},\{1,3\},\{1,4\}\right\}$. The complex C is normal and flag. Let $F=(1,2)$, $G=(1,3)$, and $S=\{4\}$, the path [F, G, F] is nonmonotone, conservative and revisiting. On the other hand, consider the complex presented in Fig. 3 and the shown monotone but not conservative path which is revisiting. Again, the complex is flag and normal.

Fig. 3

A flag normal complex with a monotone nonconservative path which is revisiting. The step $[F_0,F_1]$ is not conservative

Even in flag normal complexes, monotone conservative paths do not yield, or even approximate, shortest paths:

Lemma 3.4

There are flag 2-balls (and flag 3-polytopes) with the following behaviors:

• (a) the difference in length in monotone conservative paths between two given facets can be arbitrarily large.

• (b) no monotone conservative path is a shortest path between two given facets.

Proof

In Fig. 4, we see two examples of flag 2-balls with the needed properties. In the one on the left, the first anchor can be $f_1$ or $f_2$. If we choose $f_1$, the path to the facet S is going to be short. Otherwise, choosing $f_2$ may lead to an arbitrary large path depending on the number of vertices involved in the “comb” region. In the complex on the right, the first anchor has to be $f_2$ and the path can be very long for the same reason. The shortest path from F to S can thus be arbitrarily shorter than any monotone conservative path.

It is not difficult to make these examples as flag 3-polytopes by adding a vertex v joined to the boundary and making edge-subdivisions of the edge $\{v,f_3\}$ sufficiently many times. Adding v and the edges to the boundary gives a flag 2-sphere since there are no empty triangles, that is a minimal nonface of dimension 2. Finally flagness and polytopality are preserved by edge-subdivisions. $\square$

Fig. 4

The flag 2-ball on the left has two monotone conservative paths from F to S whose difference in length is large. The flag 2-ball on the right has a monotone conservative path from F to S much longer than the shortest path

3.2 A linear bound in fixed dimension

We show here that monotone conservative paths lead to the classical bound of Larman [14], Barnette [3], and Eisenbrand et al. [6].

Theorem 3.5

([3, 6, 14]) The length of a monotone conservative path in a $(d-1)$-dimensional pure complex C on n vertices ($d\ge 2$) is at most $n2^{d-2}$. In particular if C is normal, the same inequality holds for its diameter. Moreover, if C is a pseudomanifold without boundary, the same statement holds with the bound $n2^{d-3}$.

The statement is meant with respect to any target set. In particular we never make the target set explicit in the proof for brevity reasons. As mentioned in the introduction the bound $n2^{d-2}$ is, modulo a (small) constant, one of the best that are proved for the diameter of normal simplicial complexes, or even for the more restricted case of polytopal simplicial complexes.

Proof

The proof is by induction on d. In the case $d=1$, either $n=1$, and then $N=0 \le n 2^{d-2} =1/2$, or $n\ge 2$, and then $N\le 1= 2\cdot \frac{1}{2}\le n 2^{d-2}$.

For $d\ge 2$ let $x_1,\dots ,x_k$ be the sequence of anchors along $\Gamma$. Let $\Gamma _i=[F^i_0,\dots ,F^i_{N_i}]$ be the subpath of $\Gamma$ anchored at $x_i$, including the facet at which the change of anchor takes places (that is, $F^{i-1}_{N_{i}}=F^i_0$ is the first facet anchored at $x_i$, obtained in a step that was still anchored at $x_{i-1}$).

The path $\Gamma _i$ is monotone and conservative in the star of $x_i$. Deleting $x_i$ from it gives a monotone conservative path in ${{\mathrm{lk}}}_C(x_i)$ which, by inductive hypothesis, has length at most

$$\begin{aligned} n_i 2^{d-3}, \end{aligned}$$

where $n_i$ is the number of vertices other than $x_i$ used in $\Gamma _i$. Now, since the distances ${{\mathrm{vdist}}}(x_i,S)$ are decreasing, no vertex of C can be in more than two links of the form ${{\mathrm{lk}}}_{C}(x_i)$. This shows that $\sum _{i=1}^kn_i\le 2n$. Using this fact and the induction hypothesis, we have

$$\begin{aligned} N \quad =\quad \sum _{i=1}^k N_i \le \sum _{i = 1}^k n_i2^{d-3} \quad \le \quad 2^{d-2}n. \end{aligned}$$

For pseudomanifolds the proof follows the same ideas, but the induction starts with $d=2$. A 1-dimensional pseudomanifold without boundary is a cycle on n vertices, and the length of monotone conservative paths in it is indeed bounded by n / 2.

Now the normality hypothesis ensures the existence of monotone conservative paths between any two facets, which concludes the proof for the bound on the diameter in this case. $\square$

3.3 Refined bound for banner complexes

We now look at monotone conservative paths in banner complexes. We begin by recalling the definition by Klee and Novik [12]. Then, we prove upper bounds for the length of monotone conservative paths for these complexes, and therefore on their diameter.

Definition 3.6

Let C be a pure simplicial complex of dimension $(d-1)$. A critical clique is a set T of vertices of C forming a clique in the 1-skeleton of C and such that there exists a vertex $v\in T$ such that $T{\smallsetminus }\{v\}$ is a face of C. For $k\in \{2, \dots ,d-1\}$, the complex C is said to be k-banner if every critical clique of size at least $(k+1)$ is a face of C.

Notice that any $(d-1)$-dimensional complex has no face with $(d+1)$ vertices, and thus cannot contain a critical clique of size $(d+2)$. So any $(d-1)$-dimensional complex is $(d+1)$-banner. Other properties on banner complexes are to be found in the article [12]. Among them is the fact that any k-banner complex is also $(k+1)$-banner, and that flag and 2-banner complexes coincide. Thus, banner complexes form a nested sequence of families of complexes starting with flag complexes for $k=2$ to finish with all complexes for $k=d+1$. Let us also mention that the original definition allows for $k=1$, but since 1-banner and 2-banner complexes are exactly the same, we prefer not to consider 1-banner complexes.

Remark 3.7

Every minimal nonface of size at least 3 in a complex is also a critical clique. In particular, if C is k-banner then every minimal nonface of it has size at most k. In other words, the Stanley–Reisner ring of a k-banner complex is generated in degree at most k. The converse may not hold.

We also recall the following result on links in banner complexes.

Lemma 3.8

([12, Lemma 3.4]) Let $k\ge 2$, C be a pure simplicial complex and x be a vertex of C. If C is k-banner, then the link ${{\mathrm{lk}}}_C(x)$ of x in C is $(k-1)$-banner.

Proof

Any critical clique in ${{\mathrm{lk}}}_C(x)$ is, after adding x, a critical clique of C of size one more. $\square$

This lemma allows us to provide an upper bound for the length of monotone conservative paths in banner complexes, combining the proofs of Theorem 3.5 and Corollary 3.2, which are special cases of the following:

Theorem 3.9

Let $d\ge 2$, $k\ge 2$, and C be a normal k-banner $(d-1)$-complex on n vertices. If $\Gamma =[F_0,\dots ,F_{\ell }]$ is a monotone conservative path in C towards a set S, then the length of $\Gamma$ satisfies $\ell \le n2^{k-2}$.

Proof

We show the result by induction on the dimension $d-1$. For $d=2$, monotone conservative paths are the shortest paths in C so that $\ell \le n$. The inequality thus holds in this case. Suppose now that $d>2$. If $k=2$, then we know that C is flag, implying the Hirsch bound [1], and the inequality holds.

So suppose now that $k\ge 3$ and consider the dual paths $\Gamma _1,\dots ,\Gamma _r$ obtained from splitting $\Gamma$ according to its sequence of anchors, that is $\Gamma _i$ is the greatest subpath of $\Gamma$ in which the anchor of any facet is the $i{\mathrm{th}}$ anchor $x_i$ of the sequence of anchors of $\Gamma$, for $i\in [r]$. In particular all $\Gamma _i$’s are monotone conservative paths from their starting facet towards the set S. We fix $i\in [r]$ and consider the link $\Gamma '_i$ of $x_i$ in $\Gamma _i$. It is a monotone conservative path towards the set $S'$ of Definition 2.1. Moreover it is a monotone conservative path in the link ${{\mathrm{lk}}}_C(x_i)$ of $x_i$ in C.

Since C is k-banner, Lemma 3.8 ensures that this link is $(k-1)$-banner. Since $k\ge 3$, we can thus apply the induction hypothesis to $\Gamma '_i$. Let $n_i$ be the number of vertices of C that appear in at least one facet of $\Gamma '_i$, the induction hypothesis says that $\Gamma '_i$, and thus $\Gamma _i$, has length at most $n_i2^{k-3}$. So we have

$$\begin{aligned} \ell \le \sum _{i=1}^{r} n_i2^{k-3} = 2^{k-3}\sum _{i=1}^{r} n_i. \end{aligned}$$

Now recall that each facet of the path $\Gamma _i$ contains $x_i$ and vertices that are either at distance ${{\mathrm{vdist}}}(x_i,S)$ or ${{\mathrm{vdist}}}(x_i,S)~+~1$ of the set S. Since ${{\mathrm{vdist}}}(x_i,S) = {{\mathrm{vdist}}}(x_{i + 1}, S) + 1$, a vertex of C cannot appear in more than two consecutive $\Gamma _i$’s. So the sum of the $n_i$’s is smaller than 2n, which concludes the proof. $\square$

Observe that Theorem 3.9 somehow interpolates between Theorem 3.5 and Corollary 3.2:

• Since every $(d-1)$-complex is $(d+1)$-banner, substituting k by $d+1$, we recover (except for a factor of two) the bounds in Theorem 3.5.

• Since flag complexes are (the same as) 2-banner complexes, substituting k by 2, we recover (almost) the Hirsch bound of Corollary 3.2.

4 Monotone conservative paths can be exponentially long

In this final section we construct long monotone conservative paths, hence providing lower bounds somehow responding to the upper bounds of Sect. 3. Our constructions use the operations of join and one-point suspension of simplicial complexes, so in the first part of the section we review these operations and study how monotone conservative paths behave under them. We then present two constructions of normal complexes that contain exponentially long monotone conservative paths. The first one is a ball and the second one is a simplicial polytope.

Both constructions have the comfortable property of being vertex-decomposable. Recall that a pure $(d-1)$-complex C is vertex-decomposable [5, 17] if it is either a simplex or if there exists a vertex $x\in C$ such that ${{\mathrm{lk}}}_{C}(x)$ and ${{\mathrm{del}}}_C(x)$ are both vertex-decomposable and ${{\mathrm{del}}}_C(x)$ is still pure of dimension $d-1$. Our interest in vertex-decomposability comes from the following:

Lemma 4.1

([17, Corollary 2.11]) Vertex-decomposable complexes satisfy the Hirsch bound. That is, if C is a vertex-decomposable $(d-1)$-complex, then the diameter of the dual graph of C is at most $n-d$.

4.1 Monotone conservative paths in joins and one-point suspensions

The join of two simplicial complexes $C_1$ and $C_2$ on disjoint vertex sets $V_1$ and $V_2$ is the simplicial complex

$$\begin{aligned} C_1*C_2:=\{f_1\sqcup f_2 : f_1\in C_1,f_2\in C_2\}. \end{aligned}$$

Observe that the dual graph of $C_1*C_2$ is the Cartesian product of the dual graphs of $C_1$ and $C_2$.

The suspension of a simplicial complex C is the join of C with a simplicial complex consisting of two singletons.

The deletion (sometimes called the antistar or face-deletion) of a face f from C is

$$\begin{aligned} {{\mathrm{del}}}_C(f) :=\{f'\in C : f\not \subseteq f'\}, \\ \end{aligned}$$

Given a vertex v of a simplicial complex C, the one-point suspension of C with respect to v is the simplicial complex

$$\begin{aligned} {{\mathrm{ops}}}_C(v):=({{\mathrm{lk}}}_C(v) * \left\{ \{v_1,v_2\}\right\} )\ \cup \ ({{\mathrm{del}}}_C(v) * \left\{ \{v_1\},\{v_2\}\right\} ), \end{aligned}$$

where $v_1$ and $v_2$ are new elements, called suspension vertices, that were not vertices of C. Equivalently, ${{\mathrm{ops}}}_C(v)$ is obtained by contracting the edge $vv_2$ in the suspension $C * \{v_1,v_2\}$ of C. See Fig. 5 (left and middle) for an illustration of the one-point suspension of a 1-dimensional complex. Observe that

$$\begin{aligned} {{\mathrm{lk}}}_{{{\mathrm{ops}}}_{C}(v)}(v_1) \cong {{\mathrm{lk}}}_{{{\mathrm{ops}}}_{C}(v)}(v_2) \cong C\quad \text { and } \quad {{\mathrm{lk}}}_{{{\mathrm{ops}}}_{C}(v)}(v_1v_2) = {{\mathrm{lk}}}_C(v). \end{aligned}$$

One-point suspensions are called wedges in [17], where it is proved that joins and one-point suspensions preserve vertex-decomposability:

Lemma 4.2

([17, Proposition 2.5 and Theorem 2.7]) Let C be a d-complex, x a vertex of C and f a face of C.

• The complex C is vertex-decomposable if and only if ${{\mathrm{ops}}}_C(x)$ is vertex-decomposable.

• If C is vertex-decomposable, then ${{\mathrm{stell}}}_C(f)$ is a vertex-decomposable d-complex.

Let $\omega (C)$ denote the maximum length of monotone conservative paths in a pure complex C.

Proposition 4.3

The function $\omega$ has the following properties.

• (i) $\omega (C_1*C_2)=\omega (C_1)+\omega (C_2)$

• (ii) $\omega ({{\mathrm{ops}}}_C(v))\in \{\omega (C),\omega (C)+1\}$

Proof

• (i) It is clear that every dual path $\Gamma$ in $C_1*C_2$ restricts as a path $\Gamma _1$ in $C_1$ and a path $\Gamma _2$ in $C_2$ so that ${{\mathrm{length}}}(\Gamma _1)+{{\mathrm{length}}}(\Gamma _2)={{\mathrm{length}}}(\Gamma )$. To prove $\omega (C_1*C_2)\le \omega (C_1)+\omega (C_2)$ we only need to check that if $\Gamma$ is monotone and conservative, then $\Gamma _1$ and $\Gamma _2$ are also monotone and conservative.

  Let $\Gamma$ be a monotone and conservative path from the facet $F=F_1 *F_2$ to the facet $G=G_1 *G_2$, where $F_1,G_1$ (resp. $F_2,G_2$) are facets of $C_1$ (resp. $C_2$). Observe that flipping a vertex in $C_1$ does not influence the vertex-distances from vertices of a facet in $C_1$ to the facet $G_2$. Therefore the restriction of $\Gamma$ to $C_1$ always flips according to vertex-distances within $C_1$. Further, the flip does not depend on the position of the anchor, i.e., it occurs either in $C_1$ or in ${{\mathrm{lk}}}_{C_1}(v)$, which respects the definition of vector of distances in $C_1$. Therefore, the restriction of $\Gamma$ to $C_1$ (and symmetrically to $C_2$) forms a monotone and conservative path.

  Conversely, taking monotone and conservative paths in $C_1$ and $C_2$ determines a monotone and conservative path in $C_1*C_2$ by shuffling the consecutive subsegments depending on the minimal vertex-distances of the anchors. Therefore $\omega (C_1)+\omega (C_2)\le \omega (C_1*C_2)$, which concludes the proof of (i).

• (ii) Since C is isomorphic to the link of $v_1$ in ${{\mathrm{ops}}}_C(v)$, we have $\omega ({{\mathrm{ops}}}_C(v)) \ge \omega (C)$. So, we only need to check that $\omega ({{\mathrm{ops}}}_C(v)) \le \omega (C) +1$. Let $\Gamma$ be a longest monotone conservative path in the one-point suspension ${{\mathrm{ops}}}_C(v)$ and let $\Gamma '$ be the path restricted to C in the following sense: facets of ${{\mathrm{ops}}}_C(v)$ of the type $F*v_1$ or $F*v_2$ are sent to F, facets $F*\{v_1,v_2\}$ are sent to $F*v$. If one of $v_1$ or $v_2$ (say $v_1$) belongs to all the facets in $\Gamma$, then $\Gamma '$ is a monotone and conservative path in ${{\mathrm{lk}}}_{{{\mathrm{ops}}}_{C}(v)}(v_1)$, which is isomorphic to C. If none of $v_1$ or $v_2$ belongs to all the facets in $\Gamma$, then assume that the starting facet contains $v_1$ but not $v_2$ and the final facet contains $v_2$ but not $v_1$. The path $\Gamma '$ does the same flips as $\Gamma$ except for the flips that change $v_1$ to $v_2$, or vice-versa. We need to show that there is only one of those. Since the stars of $v_1$ and $v_2$ contain all vertices, a step [F, G] flipping $v_1$ to $v_2$ (or vice-versa) occurs with a vector of distances $(1,\dots ,1)$ for F. Therefore, G has to contain a vertex in the original target set S. Since $v_2$ is the only vertex not in F, we have $v_2\in S$. Then, by the recursive definition of monotone conservative paths, the remaining part of the monotone conservative path in ${{\mathrm{ops}}}_C(v)$ is formed in ${{\mathrm{lk}}}_{{{\mathrm{ops}}}_C(v)}(v_2)$ which is isomorphic to C and $v_2$ is contained in the rest of the monotone conservative path. It remains to show that $\Gamma '$ is monotone and conservative. The path $\Gamma '$ consists of two parts, the one containing $v_1$ and the one containing $v_2$. By the argument above they are both monotone and conservative with respect to a same target set so concatenating them gives a monotone and conservative path up to the repetition of a unique facet of C.

$\square$

4.2 A simplicial ball with exponential monotone conservative paths

We now present the construction of our first family of normal complexes containing exponentially long monotone conservative paths.

Lemma 4.4

Let $\mathcal {B}$ be a $(d-1)$-dimensional simplicial ball with n vertices. Suppose there are facets $F_1$ and $F_2$ and vertices $x_1$ and $x_2$ satisfying the following properties:

• (1) $F_i$ is the only facet containing $x_i$, for $i=1,2$.

• (2) Every monotone conservative path from $F_1$ to $F_2$ or from $F_2$ to $F_1$ has length at least L.

Then, for every $k\ge 2d$ there is a d-dimensional simplicial ball $\mathcal {B}'$ with $n+k+1$ vertices having facets $F'_1$ and $F'_2$ and vertices $x'_1$ and $x'_2$ satisfying:

• (1) $F'_i$ is the only facet containing $x'_i$, for $i=1,2$.

• (2) Every monotone conservative path from $F'_1$ to $F'_2$ or from $F'_2$ to $F'_1$ has length at least $2L+k$.

Observe that the statement does not specify the target sets for the monotone conservative paths. The expression “for every monotone conservative path” is then meant whatever the target set S may be, as long as that target set S allows for the existence of the claimed monotone conservative paths. In the case of Lemma 4.4 this is equivalent to $x_2\in S \subset F_2$. We refer the reader to Fig. 5 to visualize more easily the construction presented in the following proof.

Fig. 5

A 2-dimensional illustration of the example constructed in Lemma 4.4

Proof

The condition on the vertex $x_i$ implies that the facet $F_i$ has a codimension-one face $G_i$ contained in the boundary of $\mathcal {B}$. Consider the one-point suspension ${{\mathrm{ops}}}_\mathcal {B}(x_1)$ of $\mathcal {B}$ on the vertex $x_1$, and call $u_1$ and $u_2$ the suspension vertices. Observe that $F_2 \cup u_i$ is a facet containing the codimension-one face $G_2\cup u_i$, for $i=1,2$.

Let $C_\ell$ be the following d-complex on $\ell +d$ vertices $\{u,v_1,v_2,\dots , v_{\ell +d-1}\}$ and $\ell$ facets:

$$\begin{aligned} C_\ell := \{ \{u, v_i,\dots , v_{i+d-1}\} : i=1,\dots \ell \}. \end{aligned}$$

Observe that for $\ell \ge d$ the codimension-one boundary face $G:=\{u,v_1,\dots , v_{d-1}\}$ and the facet $F:=\{u,v_\ell ,\dots , v_{\ell +d-1}\}$ only have u in common.

Let now $k_1,k_2\in \mathbb {N}$ be such that $k_1+k_2=k$ and $k_i\ge d$, $i=1,2$. Our complex $\mathcal {B}'$ consists of the one-point suspension ${{\mathrm{ops}}}_\mathcal {B}(x_1)$ of $\mathcal {B}$ with a copy of $C_{k_1}$ glued by identifying $G_2\cup u_1$ with $G\cup u$ and a copy of $C_{k_2}$ glued by identifying $G_2\cup u_2$ with $G\cup u$. The facets $F'_1$ and $F'_2$ are the F’s in $C_{k_1}$ and $C_{k_2}$, and the vertices $x'_i$ are the last vertices $v_{k_1+d-1}$ and $v_{k_2+d-1}$ in them. Let us see that the stated properties are satisfied. We concentrate on paths from $F'_1$ to $F'_2$ but all the assertions are valid for the reverse paths, by symmetry.

• The number of vertices in $\mathcal {B}'$ equals the $n+1$ in ${{\mathrm{ops}}}_\mathcal {B}(x_1)$ plus the $k+2d$ vertices in $C_{k_1}$ plus $C_{k_2}$, minus the 2d vertices along which we glue.

• The facets $F'_i$ and vertices $x'_i$ clearly satisfy property 1 in the statement.

• Since $\mathcal {B}'$ is a ball, it is normal and, by Lemma 2.9, there is at least one monotone conservative path from $F'_1$ to $F'_2$.

• Every facet path (monotone and conservative or not) from $F'_1$ to $F'_2$ starts by going through the $k_1$ facets of $C_{k_1}$ and finishes by going through the $k_2$ facets $C_{k_2}$. Apart of these k steps, the path consists of a path between $F_2 \cup u_1$ and $F_2 \cup u_2$ inside ${{\mathrm{ops}}}_\mathcal {B}(x_1)$.

• The unique closest vertices between $F'_1$ and $F'_2$ are $u_1$ and $u_2$, which form an edge. In particular, every monotone conservative path from $F'_1$ to $F'_2$ (or vice versa) has two anchors, $u_1$ and $u_2$.

• The part of the path anchored at $u_1$ goes from $F_2 \cup u_1$ to ${{\mathrm{ops}}}_{F_1}(x_1)=F_1{\smallsetminus }\{x_1\}\cup \{u_1,u_2\}$. Its link at $u_1$ is hence a monotone conservative path from $F_2$ to $F_1$ in $\mathcal {B}$, so it has length at least L.

• The part of the path anchored at $u_2$ goes from ${{\mathrm{ops}}}_{F_1}(x_1)=F_1{\smallsetminus }\{x_1\}\cup \{u_1,u_2\}$ to $F_2 \cup u_2$. Its link at $u_2$ is hence a monotone conservative path from $F_1$ to $F_2$ in $\mathcal {B}$, so it has length at least L.$\square$

Theorem 4.5

For every $d\ge 2$ and every $N\ge 4$ there is a $(d-1)$-ball $\mathcal {B}_d$ with $N+d^2$ vertices and two facets $F_1$ and $F_2$ in it such that every monotone conservative path between them has length at least $2^{d-2} (N+3)$.

Proof

Let $\mathcal {B}_2$ be a path with $N+4$ vertices and iterate the process of Lemma 4.4 with $k=2d$. $\square$

Remark 4.6

It is easy to check that the construction of Lemma 4.4 preserves shellability and vertex-decomposability. Moreover, if every monotone conservative path in $\mathcal {B}$ is a Hamiltonian path in the dual graph, then the same happens in $\mathcal {B}'$. In particular, in the statement of Theorem 4.5 we can add that $\mathcal {B}_d$ is vertex-decomposable and that every monotone conservative path from $F_1$ to $F_2$ is Hamiltonian.

4.3 A Hirsch polytope with exponential monotone conservative paths

We now show a second construction which achieves essentially the same length of monotone and conservative paths but in a simplicial complex that is a polytopal sphere. The construction is similar in spirit to the previous one, based on the use of one-point suspensions, but a bit more complicated since in a sphere we cannot have vertices contained in a unique facet, that were instrumental in the previous construction.

In the inductive step, instead of gluing stacks to the one-point suspension of the previously constructed sphere, we do stellar subdivisions at edges. Recall that the stellar subdivision of a face f in a complex C is the simplicial complex denoted by ${{\mathrm{stell}}}_C(f)$ and given by

$$\begin{aligned} {{\mathrm{stell}}}_C(f):= & {} {{\mathrm{del}}}_{C \cup ( \mathrm{st}_C(f)*\{a\})}(f)\\= & {} \{f'\in C : f\not \subseteq f'\} \cup \left\{ f'\cup \{a\} : f\not \subseteq f'\in \mathrm{st}_C(f) \right\} , \end{aligned}$$

where a is a new vertex that is not a vertex of C. Notice that in the particular case where $f=\{v_1,\dots ,v_d\}$ is a facet of C, then ${{\mathrm{stell}}}_C(f)$ is obtained replacing in C the facet f by the $d+1$ facets $\{f{\setminus } \{v\} \cup \{a\}: v\in f\}$ (see Fig. 6).

Fig. 6

The stellar subdivision of a simplex F

The following properties of stellar subdivisions will be used in the construction. Let ab be an edge in a simplicial complex C, and let $C'$ be the complex obtained by a stellar subdivision of the edge ab. Let c be the new vertex.

• Let v be a vertex of C other than a and b and assume that abv is not a triangle. Then, ${{\mathrm{lk}}}_{C'}(v)={{\mathrm{lk}}}_{C}(v)$.

• ${{\mathrm{lk}}}_{C'}(a)$ is obtained from ${{\mathrm{lk}}}_{C}(a)$ replacing c for b. Similarly, ${{\mathrm{lk}}}_{C'}(b)$ is obtained from ${{\mathrm{lk}}}_{C}(b)$ replacing c for a.

• The degree of c in the 1-skeleton of $C'$ is 2 plus the number of triangles containing ab in C, and is bounded above by $\min \{\deg _C(a), \deg _C(b)\}$.

In particular, the proof makes use of the following idea. Let a be a vertex in a simplicial complex C and let $C'$ be obtained from C by stellar subdivision of all the edges ab containing a (in any order). Then, for every vertex $v\ne a$ of C we have that

$$\begin{aligned} {{\mathrm{vdist}}}_{C'}(a,v) = {{\mathrm{vdist}}}_{C}(a,v) + 1. \end{aligned}$$

We are now ready to state and prove the lemma that gives the induction step:

Lemma 4.7

Let C be a $(d-1)$-complex on N vertices. If C has two facets $F_1$ and $F_2$ and vertices $x_i\in F_i$ ($i=1,2$) such that:

• (1) Every monotone conservative path from $F_i$ towards $\{x_j\}$ (and ending in a facet containing $x_j$) ends precisely in $F_j$ and has length at least L, for $(i,j)\in \{(1,2),(2,1)\}$.

• (2) Every monotone conservative path from $F_i$ towards $F_j$ (and ending in $F_j$) has length at least L, for $(i,j)\in \{(1,2),(2,1)\}$.

• (3) ${{\mathrm{vdist}}}_C(x_1,x_2)\ge 3$.

• (4) The degrees of $x_1$ and $x_2$ in (the 1-skeleton of) C are $2d-2$.

Then, there exists a d-complex $C'$ on $N':= N+ 4d+1$ vertices having the same properties (1) to (4) with $L':=2L$ and $d':=d+1$, and with respect to facets $F'_i$ and vertices $x'_i\in F'_i$ ($i=1,2$).

We refer the reader to Fig. 7 to visualize on a 2-dimensional example the construction presented in the following proof.

Proof

Consider first the complex ${{\mathrm{ops}}}_C(x_1)$ and let u and v be the suspension vertices. In it do the following stellar subdivisions:

• Let $\{y_1,\dots ,y_{2d-2}\}$ be the neighbor vertices of $x_2$ in C. For each of them, subdivide the edges $uy_i$ and $vy_i$. Call $u_i$ and $v_i$ the new vertices introduced.

• Then subdivide the edges $ux_2$ and $vx_2$. Call $u'$ and $v'$ the new vertices.

• Finally subdivide the edges $uu'$ and $vv'$ and call the new vertices $x'_1$ and $x'_2$.

Let $C'$ be the final complex so obtained. Observe that the number of vertices has increased by one via the one-point suspension, then by $4d-4$ (vertices $u_i$ and $v_i$, $i=1,\dots , 2d-2$), then, finally by another four ($u'$, $v'$, $x'_1$ and $x'_2$). In particular, the new complex indeed has $N':=N+4d+1$ vertices.

Observe that the links of u and v do not change by the subdivisions, except some of the new vertices introduced play the role of vertices of C. For example, in ${{\mathrm{lk}}}_{C'}(u)$ the role of $x_1$ and $x_2$ is played by $x'_1$ and v, respectively, and the role of each neighbor y of $x_1$ is played by the new vertex produced by subdividing uy. Here we are using the assumption ${{\mathrm{vdist}}}(x_1,x_2)\ge 3$. If this didn’t hold, some of the $y_i$’s would form a triangle with u and v, in which case the subdivision of $uy_i$ would change the link at v, and vice-versa.

We let $F'_1$ consist of u together with the vertices of ${{\mathrm{lk}}}_{C'}(u)$ corresponding to $F_2$ and let $F'_2$ consist of v together with the vertices of ${{\mathrm{lk}}}_{C'}(v)$ corresponding to $F_2$. Put differently:

$$\begin{aligned} F'_1:=\{u,x'_1\}\cup \{y'_i: y_i \in F_2\}, \quad F'_2:=\{v,x'_2\}\cup \{y'_i: y_i \in F_2\}. \end{aligned}$$

Let us show some properties of this construction, among which are the claimed properties (1) to (4).

• Let us look at the degree of $x'_1$ (and $x_2$ symmetrically). Observe that the number $2d-2$ of neighbors of $x_2$ in C equals the number of triangles containing $ux_2$ in ${{\mathrm{ops}}}_C(x_1)$. This number does not change by the subdivision of the edges $uy_i$, and it becomes the number of triangles containing $uu'$ when we subdivide $ux_2$. So, when we create the vertex $x'_1$ by subdividing $uu'$, the degree of the new vertex $x'_1$ equals 2 plus that number, which shows property (4).

• The path $(x'_1,u,v,x'_2)$ is the unique shortest path from $x'_1$ to $x'_2$. Indeed, observe that any other path from $x'_1$ to $x'_2$ (or from a vertex on the “u side” to a vertex on the “v side” of the construction, for that matter) needs to pass through a vertex of C. The claim then follows by noticing that no vertex of C is a neighbor of neither $x'_1$ nor $x'_2$, so all other paths between them have length at least four. This implies part (3), but it also shows that:

  • (u, v) is the unique shortest vertex-path between $F'_1$ and $F'_2$.

  • $(u,v,x'_2)$ is the unique shortest vertex-path between $F'_1$ and $x'_2$.

  • $(x'_1,u,v)$ is the unique shortest vertex-path between $x'_1$ and $F'_2$.

• Then every monotone conservative path from $F'_1$ to $x'_2$ has $(u,v,x'_2)$ as its sequence of anchors. While we are in the first anchor u the path is a monotone conservative path along ${{\mathrm{lk}}}_{C'}(u)$ towards the vertex set $S':=\{v\}$, which is the same as a monotone conservative path from $F_2$ to $x_1$ in C. By hypothesis (1), this path has length at least L and finishes in the facet ${{\mathrm{ops}}}_C(F_1)$. The part anchored at v is, by the same arguments, a monotone conservative path from ${{\mathrm{ops}}}_C(F_1)$ to $x'_2$, which finishes in $F'_2$ and has length also at least L by the same hypothesis. This proves (1) for $C'$.

• Similarly, every monotone conservative path from $F'_1$ towards $F'_2$ has (u, v) as its first two anchors. While we are anchored at u the path is a monotone conservative path along ${{\mathrm{lk}}}_{C'}(u)$ towards the vertex set $S':=\{v\}$, which is the same as a monotone conservative path from $F_2$ to $x_1$ in C. By hypothesis (1), this path has length at least L and finishes in the facet ${{\mathrm{ops}}}_C(F_1)$. The rest of the path (the part anchored at v, and what comes later, since v belongs to our target set S) is a monotone conservative path from ${{\mathrm{ops}}}_C(F_1)$ to $F'_2$ and has length also at least L by hypothesis (2). This proves (2) for $C'$. $\square$

Theorem 4.8

For every $d\ge 2$ and every $N\ge 4$, there is a vertex-decomposable polytopal $(d-1)$-sphere $\mathcal {S}_d$ with $N+\Theta (d^2)$ vertices and two facets $F_1$ and $F_2$ in it such that every monotone conservative path between them has length at least $2^{d-3} N$.

See Fig. 7 for a 2-sphere example.

Proof

Let $\mathcal {S}_2$ be a cycle with N vertices and iterate on it the process of Lemma 4.7. Observe that the construction in the lemma preserves polytopality and vertex-decomposability, since both one-point suspension and stellar subdivision preserve them. For vertex-decomposability this follows from Lemma 4.2. For polytopality, it suffices to add a vertex outside the polytope close enough to the barycenter of the face which is stellar-subdivided to realize the stellar subdivision. $\square$

Fig. 7

A 2-sphere illustration of the example constructed in Theorem 4.8

Remark 4.9

• Observe that, for fixed d, the bounds of Theorems 4.5 and 4.8 are both within a $1+\varepsilon$ ratio of the upper bounds of Theorem 3.5, with $\varepsilon$ going to zero as N goes to infinity.

• The fact that the polytopes constructed in Theorem 4.8 are vertex-decomposable implies that they satisfy the Hirsch bound [17], and it also dramatically illustrates the need of flagness for the proof of Adiprasito and Benedetti [1] to work.