2-levelness of Marked Poset Polytopes

We call a polytope $Q\subseteq\mathbb{R}^{d}$ 2-level, if for every facet of $Q$ there exits a parallel hyperplane, such that all vertices of $Q$ are in the facet or in the parallel hyperplane. Alternatively, a polytope $Q$ is considered to be 2-level if and only if it possesses theta-rank 1 [gouveia2010theta], or it exhibits a slack matrix with entries restricted to $\{0,1\}$ [bohn2019enumeration]. These definitions, originating from the realms of semidefinite programming, statistics and polyhedral combinatorics respectively, underscore the inherent multidisciplinary nature of 2-level polytopes within mathematics. A 2-level polytope can be viewed as a generalization of well-known polytopes, including Birkhoff polytopes [ziegler2006], Hanner polytopes [hanner1956intersections], and Hansen polytopes [hansen1977certain]. The class of 2-level polytopes also encompasses spanning tree polytopes of series-parallel graphs [grande2017theta], stable matching polytopes [gusfield1989stable], certain min up/down polytopes [lee2004min], and stable set polytopes of perfect graphs [chvatal1975certain]. There is also a stronger connection between 2-level polytopes and compressed polytopes. The main difference between these classes, is that compressed polytopes are always integral 2-level polytopes, where each 2-level polytope is an affine image of a compressed polytope, where compressed polytopes are characterised as integral polytopes all of whose pulling triangulations are unimodular [compressed]. This broad spectrum of connections illustrates the pervasive presence of 2-level polytopes across diverse mathematical domains.
To any finite poset $(P,\prec)$ Stanley associated two polytopes, which are lattice polytopes with the same Ehrhart polynomial [stanley1986two]. These are the order polytope and the chain polytope. Moreover, these poset polytopes were already topic of a lot of research and it was proven, that order polytopes and chain polytopes are 2-level polytopes [ohsugi2001compressed]. Inspired by the representation theory of complex semi-simple Lie algebras, specifically within the context of PBW-degenerations, Ardila, Bliem, and Salazar [ardila2011gelfand] introduced the concept of marked order polytopes and marked chain polytopes, generalizing Stanley’s order and chain polytope. These polytopes are associated to marked posets. Given a finite poset $P$, we define a set of marked elements $P^{*}$, which includes the extremal elements of $P$. Then we can define a marking $\lambda:P^{*}\rightarrow\mathbb{Z}$, which gives all elements of $P^{*}$ an integral value preserving the ordering of $P$. These values introduces bounds for the elements of marked order polytopes and marked chain polytopes. Their investigation revealed that these polytopes are also indeed lattice polytopes, and for a given marked poset, they have identical Ehrhart polynomials.
Motivated by the recent work on linear degeneration of flag varieties [cerulli2017linear], Fang and Fourie introduced marked chain-order polytopes [fang2016marked]. These polytopes represent a class of polytopes, which combines features of marked order and marked chain polytopes. For each order ideal of the poset, one imposes chain conditions on the coordinates in the order ideal, and order conditions on the coordinates in its complement. Significantly, Fang and Fourie established that these marked chain-order polytopes form a family of lattice polytopes with Ehrhart equivalence. In addition, marked chain-order polytopes generalizes the classes of marked order and marked chain polytopes. Fang, Fourier and Pegel were also able to characterise reflexivity for this class of polytopes [fang2018minkowski].

In this paper, we mainly focus on characterising 2-levelness for marked order polytopes, marked chain polytopes and marked chain-order polytopes. The main result will be, that marked order and marked chain polytopes are 2-level, if and only if they are already an affine image of an order or a chain polytope. At first we have to make some general definitions and formulated some important theorems in Section 2. These definitions and theorems will be useful throughout the whole paper. In Theorem 3.3, Theorem 4.4 and Theorem 5.2 we will formulated a complete characterisation of 2-levelness for marked order, marked chain and marked chain-order polytopes respectively. These will use different techniques, depending, on what we know about these classes of polytopes. Yet, the characterisations will be very similar to each other.
Furthermore, we show a concrete formula for the Ehrhart polynomial for marked order polytopes in Theorem 6.4. Also, this will be a concrete formula for all marked chain-order polytopes. The complex nature of these polytopes will result into a very complex formula, but we will present an example of a marked poset, which will have a nice Ehrhart polynomial.

Acknowledgements. This paper was written during a student exchange supervised by Professor Akihiro Higashitani at Osaka University. I am grateful to Professor Akihiro Higashitani and my tutor, Max Kölbl, for their guidance and support during my research at Osaka University.

The set $\mathbb{R}$ (resp. $\mathbb{Z}$, ${\mathbb{N}}$) of real (resp. integral, natural) numbers has the usual total order. For us the set of natural numbers ${\mathbb{N}}$ will include the 0. The set $[m]$ denotes the set $\{1,2,\ldots,m\}$. For a polytope $Q\subseteq\mathbb{R}^{d}$, we denote the set of vertices as $V(Q)$. The set $\operatorname{aff}(F)$ for a set $F\subseteq\mathbb{R}^{d}$ is the affine hull of $F$. For a poset $(P,\prec)$ we will often just use the notation $P$. We still then use $\prec$ for describing the order of $P$. We denote the set of minimal and maximal elements of $P$ as $\min(P)$ and $\max(P)$.

Before we start proving something, we need to define the polytopes we are working with. At first, we define what a 2-level polytope is and which simple properties it has.

Proof.   This is trivial, since parallel objects stay parallel after affine transformations. $\Box$

Before defining the notations of marked posets and marked poset polytopes, we will remind us of the definitions of order polytopes and chain polytopes.

We will define next what a marked poset is. With this definition we can directly define marked order, marked chain and marked chain-order polytopes.

From here on we will always use $P^{*}$ for the set of marked elements for a poset $P$. We also assume $\min(P)\cup\max(P)\subseteq P^{*}$ for each marked poset.

Especially in Section 3, where we will be looking at marked order polytopes, we need to understand the faces of these polytopes. Thankfully Pegel already proved a lot of useful theorems [pegel2018face].

Before characterising the 2-level marked order polytopes, it is useful to make some observations.
Firstly, we only want to work with connected posets, therefore we prove that we can separate these components, while working with 2-levelness.

Proof.   Let $P_{1},\ldots,P_{k}$ be the connected, disjoint components of $(P,\lambda)$ with $\lambda_{i}=\lambda\mid_{P_{i}}$. Since each $P^{*}_{i}$ only contains one minimal and one maximal element, they are affine isomorphic to an order polytope, by changing the marking of these elements to $0$ and $1$. This change is an affine transformation without changing the structure of the polytope.
From Proposition 2.18 we know, that

$$\mathcal{O}(P_{1}\sqcup\cdots\sqcup P_{k},\lambda_{1}\sqcup\cdots\sqcup\lambda_{k})=\mathcal{O}(P_{1},\lambda_{1})\times\cdots\times\mathcal{O}(P_{k},\lambda_{k}).$$

Since the affine transformations only affect each marked order polytope separately, we can combine them to affinely transform $\mathcal{O}(P_{1}\sqcup\cdots\sqcup P_{k},\lambda_{1}\sqcup\cdots\sqcup\lambda_{k})$ such that all markings are only $0$ and $1$. We call this new marked order polytope $\mathcal{P}$ with poset $P^{\prime}$ and marking $\lambda^{\prime}$. Since all the components of $P^{\prime}$ are disjoint and have a maximal marking of $1$ and a minimal marking of $0$, we can connect them, by deleting the individual marked elements and connect all elements of $P^{\prime}$ to one maximal element $\hat{1}$ and one minimal element $\hat{0}$. This does not change the marked order polytope $\mathcal{P}$. From [ardila2011gelfand, Section 3.2] we know that $\mathcal{P}$ is now an order polytope and by construction affine isomorphic to $\mathcal{O}(P,\lambda)$. $\Box$

We use the theorems, which describe faces of marked order polytopes to define the exact facets of marked order polytopes.

Proof.   Let $(P,\lambda)$ be a marked poset which is regular and strict and $|P\backslash P^{*}|=d$. We know from Proposition 2.15 and Theorem 2.17, that facets of $\mathcal{O}(P,\lambda)$ are defined by partitions of $P$ with $d-1$ free blocks.
Since $|P\backslash P^{*}|=d$ there are only two options for how we can achieve $d-1$ free blocks. The first one is that $x_{p}=x_{q}\text{ for a a covering }p\prec q\text{ in }P$, because then $q$ and $p$ are in the same block and exactly two elements of $P\backslash P^{*}$ can only be in the same block, by being directly connect by a covering. The second option is that $x_{p}=\lambda(a)\text{ for some }p\in P\text{ and some }a\in P^{*}$ for obvious reasons. $\Box$

With these two lemmas we can now characterise marked order polytopes, which are 2-level polytopes.

Proof.   Let $(P,\lambda)$ be a strict and irredundant poset and $d=|P\backslash P^{*}|$.
Because of Lemma 3.1 we see (b) $\Rightarrow$(c). Since every compressed polytope is a 2-level polytope and order polytopes are compressed, (c) $\Rightarrow$(a) is trivial [ohsugi2001compressed].
Showing (a) $\Rightarrow$(b) is more complicated. Assume $\mathcal{O}(P,\lambda)$ is a 2-level polytope. From Lemma 3.2 we know, that there are only two kinds of facets. We want to get some informations about the vertices from $P$ by examining these two cases.
Case 1: Let $F$ be a facet defined by $x_{p}=\lambda(a)$ for some $p\in P$ and $a\in P^{*}$. W.l.o.g. $p$ covers $a$ in $P$.
Because $\mathcal{O}(P,\lambda)$ is a 2-level polytope, every vertex $v$ has to fulfill one of the following equations:

$$v_{p}=\lambda(a)\text{ or }v_{p}=c\text{ for }c\in\mathbb{R}.$$

By Proposition 2.15, the partition for the vertex has to have zero free blocks. Therefore $c=\lambda(b)$ for some $b\in P^{*}$. We can conclude, that $a$ is the highest lower bound for $p$ and $b$ is the lowest higher bound for $p$.
As a result, every time an element $p$ of $P\backslash P^{*}$ is less than an element $b$ of $P^{*}$ or is greater than an element $a$ of $P^{*}$, every vertex has $x_{p}=\lambda(a)$ or $x_{p}=\lambda(b)$.
Case 2: Let $F$ be a facet defined by $x_{p}=x_{q}$ for some $p,q\in P\backslash P^{*}$ and $p\prec q$.
We want to show, that $p$ and $q$ have the same value for their highest lower bound marking and lowest higher bound marking. Assume $a_{p}$ and $a_{q}$ are their respective lower bounds and $b_{p}$ and $b_{q}$ their respective higher bounds.
We want to see now, that $x_{p}$ and $x_{q}$ cannot have the same value $k\in\mathbb{R}$ in the whole facet. Assume they are equal to a value $k\in\mathbb{R}$ in the whole facet. Since there are vertices in the facet and all vertices have markings as coordinates, $k=\lambda(e)$ for some $e\in P^{*}$. Therefore the equation $x_{p}=x_{q}=\lambda(e)$ holds for the whole facet. Hence $p$, $q$ and $e$ are in the same block in the partition of the facet. This is a contradiction, since this partition has now at most $d-2$ free blocks and cannot describe a facet any more.
From this we can conclude, that $\lambda(a_{p})<\lambda(b_{p})$ and $\lambda(a_{q})<\lambda(b_{q})$. We also know $\lambda(a_{p})\leq\lambda(a_{q})<\lambda(b_{p})\leq\lambda(b_{q})$, since $x_{p}=x_{q}$ for some vertices.
Assume $\lambda(b_{p})<\lambda(b_{q})$. We get that there are non-crossing connections from $p$ and $q$ to $b_{p}$ and $b_{q}$ respectively. And $b_{p}$ has to be connected to a lower element then $q$ because of the ordering of $P$. In addition, we know from the 2-levelness of the polytope, all vertices have to fulfill either $x_{p}=x_{q}$ or $x_{p}=x_{q}+c$ for some $c\in\mathbb{R}$.
We can conclude from Theorem 2.17 that there exists the vertices $v$ and $w$ with $v_{p}=\lambda(b_{p})$ and $v_{q}=\lambda(b_{q})$, $w_{p}=\lambda(a_{p})$ and $w_{q}=\lambda(b_{q})$. From $x_{p}=x_{q}+c$ we have to conclude, that $\lambda(a_{p})=\lambda(b_{p})$ which is absurd. Therefore $\lambda(b_{p})=\lambda(b_{q})$ and we can combine $b_{p}$ and $b_{q}$ in the poset since $p\prec q$ (except when $b_{p}=b_{q}$). Analogous we can conclude $\lambda(a_{p})=\lambda(a_{q})$ and combine $a_{p}$ and $a_{q}$ in the poset (except when $a_{p}=a_{q}$).
As a result from Theorem 2.17, and the assumptions on $P$, we know, that every covering of $P$ gives us a facet. In conclusion with the two cases, we can see, that all elements of a component of the poset have exactly one maximal and one minimal element. $\Box$

We want to have a similar characterisation for marked chain polytopes. The difficulty in working with marked chain order polytopes lies in not knowing as much about the faces of marked chain polytopes. Therefore, we need some tricks.

Proof.   If $\mathcal{C}(P,\lambda)$ is only described by inequalities

$\displaystyle x_{i}\geq 0\text{ for }i\in P\backslash P^{*}\text{ and }\sum_{i\in I}x_{i}\leq 1\text{ for }I\subseteq P\backslash P^{*},$

we can construct a poset for the elements $P\backslash P^{*}$, where all maximal chains are the elements in the $I$ from the describing inequalities.
For this poset the chain polytope is obviously the polytope $\mathcal{C}(P,\lambda)$. $\Box$

To understand this lemma better, we will look at a small example, to understand the consequences better.

As we said before we do not know much about the faces of marked chain polytopes, but we can prove that there are always some special facets and that $0$ is always a vertex of a marked chain polytope. This will become very useful for the characterisation of marked chain polytopes, but also later for the proof of Theorem 5.2.

Proof.   Let $(P,\lambda)$ be a strict and irredundant poset and $\mathcal{C}(P,\lambda)$ the respective marked chain polytope. We know from the Definition 2.10, that $\mathcal{C}(P,\lambda)$ is described by inequalities of the form

$\displaystyle x_{p}\geq 0\text{ for }p\in P\backslash P^{*}\text{ and }\sum_{i\in I}x_{i}\leq c\text{ for }I\subseteq P\backslash P^{*}\leavevmode\nobreak\ c\in\mathbb{R}_{\geq 0}.$

Since the inequalities $x_{p}\geq 0$ are independent and no other lower bound can be formed from the inequalities $\sum_{i\in I}x_{i}\leq c$, the inequality $x_{p}\geq 0$ is a facet-describing inequality for each $p\in P\backslash P^{*}$.
The intersection of all these facets is the vertex $0$. $\Box$

We can now prove a similar characterisation for marked chain polytopes as the characterisation for marked order polytopes.

Proof.   Let $(P,\lambda)$ be a strict and irredundant poset and $d=|P\backslash P^{*}|$.
Because of Lemma 4.1 we see (b) $\Rightarrow$(c). Since every compressed polytope is a 2-level polytope and chain polytopes are compressed, (c) $\Rightarrow$(a) is trivial [ohsugi2001compressed].
Let $\mathcal{C}(P,\lambda)$ be a 2-level polytope. We want to show (a) $\Rightarrow$(b). Therefore we look at the different types of possible describing inequalities again.
From Lemma 4.3 we already know, that $x_{p}\geq 0$ is a facet for all $p\in P\backslash P^{*}$. Since $\mathcal{C}(P,\lambda)$ is a 2-level polytope, all vertices need to fulfill the equation $x_{p}=0$ or the equation $x_{p}=c_{p}$ for $c_{p}\in\mathbb{R}_{>0}$ for all $p\in P\backslash P^{*}$. By scaling every coordinate with $\tfrac{1}{c_{p}}$ respectively, we get a $(0,1)$-polytope $\mathcal{P}$.
Assume $\sum_{i\in I}x_{i}+x_{p}\leq c$ is a defining inequality of $\mathcal{P}$ with $I\cup\{p\}\subseteq P\backslash P^{*}$ a maximal chain and $c\geq 2$. We want to show that there exists a vertex $w$ with $w_{p}=1$ and $w_{i}=0$ for $\forall i\in P\backslash P^{*}$. Because we have a $(0,1)$-polytope, $w$ cannot be in the interior of any face of $\mathcal{P}$. Therefore $w$ is a vertex or $w\not\in\mathcal{P}$.
Assume that $w\not\in\mathcal{P}$. By Separation Theorem [ziegler2006, Prop 1.10], there exists a facet defining hyperplane which separates $w$ from the polytope. This is a contradiction, because there only exists defining inequalities like $x_{q}\geq 0$ for $q\in P\backslash P^{*}$ and $\sum_{i\in J}x_{i}\leq c$, where $c\in{\mathbb{N}}$ and $J$ a chain of $P$. These inequalities cannot separate $w$ from the polytope.
We now know, that $\mathcal{P}$ has the vertices $0$ and $w$. Because $\mathcal{P}$ is a 2-level polytope and the inequality $\sum_{i\in I}x_{i}+x_{p}\leq c$ is a defining inequality, all vertices have to fulfill one of the following equations:

	$\displaystyle(1)$	$\displaystyle\sum_{i\in I}x_{i}+x_{p}=c$	or
	$\displaystyle(2)$	$\displaystyle\sum_{i\in I}x_{i}+x_{p}=c-d\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ d\in{\mathbb{N}}.$

Since $0$ is a vertex of $\mathcal{P}$, and it does not fulfill the first equation it must fulfill the second equation. The same is true for the vertex $w$, since we assume $c\geq 2$. We can conclude

$\displaystyle\sum_{i\in I}0+0=0=c-d=\sum_{i\in I}0+1=1,$

which is absurd. Therefore $c$ needs to be equal to $1$.
In conclusion, all defining facets of $\mathcal{P}$ are of the form

	$\displaystyle x_{i}\geq 0\leavevmode\nobreak\ \leavevmode\nobreak\$	$\displaystyle\text{for }i\in P\backslash P^{*}$	and
	$\displaystyle\sum_{i\in I}x_{i}\leq 1\leavevmode\nobreak\ \leavevmode\nobreak\$	$\displaystyle\text{for }I\subseteq P\backslash P^{*}.$

Therefore the markings of each facet describing chain of $P$ only differ by 1, which concludes the proof. $\Box$

For marked chain-order polytopes we also do not know much about their faces, but we can characterise them using marked order and marked chain polytopes.

With this lemma we can characterise the 2-levelness of marked chain-order polytopes, by using a lot of the results for marked order and marked chain polytopes, we proved before.

Proof.   Let us first assume $\mathcal{O}(P\backslash C,\lambda)$ is a 2-level polytope and $\mathcal{O}_{C,O}(P,\lambda)$ is affinely isomorphic to a marked chain-order polytope, where the higher and lower bounds of chain elements only differ by 1. We want to show, that $\mathcal{O}_{C,O}(P,\lambda)$ is a 2-level polytope.
Since 2-levelness is preserved under affine transformations, we will use from now on the marked chain-order polytope, where the higher and lower bounds of chain elements only differ by 1 and we will call it $\mathcal{O}_{C,O}(P,\lambda)$ for simplicity.
We will now consider all different cases of facets of $\mathcal{O}_{C,O}(P,\lambda)$ and will show, that all vertices are in the facet or in a parallel hyperplane.
Case 1: Assume $x_{p}=\lambda(a)$ for $p\in O$ and $a\in P^{*}$ defines a facet.
Since $\mathcal{O}(P\backslash C,\lambda)$ is a 2-level polytope, all $x_{p}$ of vertices with $p\in O$ can only have the same upper and lower bound if they are connected in the Hasse-diagram. We call them $\lambda(a)$ and $\lambda(b)$. If these $p$ are only connected to other order elements, they are independent from all chain elements and 2-levelness follows for these elements from the 2-levelness of $\mathcal{O}(P\backslash C,\lambda)$.
If they have a connection to chain elements, $\lambda(a)$ and $\lambda(b)$ only differ by 1. Since $\mathcal{O}_{C,O}(P,\lambda)$ is a lattice polytope, $x_{p}$ has only two different possible values. This concludes 2-levelness for facets of the form $x_{p}=\lambda(a)$.
Case 2: Assume $\sum_{i\in I}x_{i}\leq 1$ is a facet for a chain $I\subseteq C$.
From this equation we get $0\leq x_{i}\leq 1$ for all $i\in I$. It follows directly from this, that all vertices lives in the facet $\sum_{i\in I}x_{i}=1$ or $\sum_{i\in I}x_{i}=0$. Therefore 2-levelness is true.
Case 3: Assume $\sum_{i\in I}x_{i}+x_{p}\leq\lambda(b)$ defines a facet for $I\subseteq C$, $p\in O$, $b\in P^{*}$ and $I$ is a maximal chain between $p$ and $b$.
With the given properties, we can follow that all $x_{i}$ for $i\in I$ and $x_{p}$ lie between some marked elements $a$ and $b$, such that $\lambda(a)=\lambda(b)-1$. It follows $0\leq x_{i}\leq 1$ for all $i\in I$ and $\lambda(b)-1\leq x_{p}\leq\lambda(b)$. In conclusion, all vertices fulfill either $\sum_{i\in I}x_{i}+x_{p}=\lambda(b)$ or $\sum_{i\in I}x_{i}+x_{p}=\lambda(b)-1$.
Case 4: Assume $\sum_{i\in I}x_{i}+\lambda(a)\leq x_{p}$ defines a facet for $I\subseteq C$, $p\in O$, $a\in P^{*}$ and $I$ is a maximal chain between $a$ and $p$.
This case is analogous to Case 3.
Case 5: Assume $\sum_{i\in I}x_{i}+x_{p}\leq x_{q}$ defines a facet for $I\subseteq C$, $p,q\in O$ and $I$ is a maximal chain between $p$ and $q$.
Because $\mathcal{O}(P\backslash C,\lambda)$ is a 2-level polytope, $x_{p}$ and $x_{q}$ lie between the same upper and lower bounds $\lambda(a)$ and $\lambda(b)$. Since the chain elements of the chain also lie between these two bounds, we know $\lambda(a)=\lambda(b)-1$. Therefore $x_{p}$ and $x_{q}$ can differ at most by at most $1$ and in addition $0\leq x_{i}\leq 1$ for all $i\in I$.
In conclusion all vertices fulfill either $\sum_{i\in I}x_{i}+x_{p}=x_{q}$ or $\sum_{i\in I}x_{i}+x_{p}+1=x_{q}$.
Case 6: Assume $x_{c}\geq 0$ for $c\in C$ is a facet.
The coordinate $x_{c}$ must be bounded by one of the inequalities from one of the cases before, because otherwise $\mathcal{O}_{C,O}(P,\lambda)$ would not be a polytope. In each of these cases $x_{c}$ lies between $0$ and $1$. It follows trivial, that all vertices fulfill either $x_{c}=0$ or $x_{c}=1$.
In conclusion, we can see for all facets all vertices lie in the facet or a parallel hyperplane. Therefore, $\mathcal{O}_{C,O}(P,\lambda)$ is a 2-level polytope. This concludes the first implication of the proof.

Assume that $\mathcal{O}_{C,O}(P,\lambda)$ is a full-dimensional 2-level polytope (coordinates which are fixed can be ignored).
We know from Lemma 4.3 that $0$ is a vertex of all marked chain polytopes. With Lemma 5.1 we can see, that for all $x\in\mathcal{O}(P\backslash C,\lambda)$ the point $(0,x)$ is a point of the marked chain-order polytope. Also for the same reason as in the proof of Lemma 4.3 we see, that $x_{c}\geq 0$ defines a facet of $\mathcal{O}_{C,O}(P,\lambda)$ for all $c\in C$. Combining these two properties we get

$\displaystyle\mathcal{O}_{C,O}(P,\lambda)\cap\bigcap_{c\in C}H_{x_{c}=0}=\{0\}\times\mathcal{O}(P\backslash C,\lambda)$

and $\mathcal{O}(P\backslash C,\lambda)$ is a face of $\mathcal{O}_{C,O}(P,\lambda)$. Since every face of a 2-level polytope is a 2-level polytope, $\mathcal{O}(P\backslash C,\lambda)$ needs to be a 2-level polytope.
Because $x_{c}\geq 0$ defines a facet for all $c\in C$, again for all $c\in C$ all vertices satisfies the equation $x_{c}=0$ or $x_{c}=d_{c}$ for some $d_{c}\in\mathbb{R}$. We can now scale all chain element coordinates by $\tfrac{1}{d_{c}}$. We will use the same name from here on for the resulting marked chain-order polytope.
Consider a facet $\sum_{i\in I}x_{i}+x_{p}\leq\lambda(b)$ for a chain $I\subseteq C$ with starts in $p\in O$ and ends in $b\in P^{*}$. Let $\lambda(a)$ be the lower bound for $x_{p}$ and the elements in the chain. Since $\mathcal{O}(P\backslash C,\lambda)$ is a face of $\mathcal{O}_{C,O}(P,\lambda)$, there exists a vertex with $x_{p}=\lambda(a)$ and $x_{i}=0$ for all $i\in I$. Therefore all vertices have to fulfill either

	$\displaystyle(1)$	$\displaystyle\sum_{i\in I}x_{i}+x_{p}=\lambda(b)$	$\displaystyle or$
	$\displaystyle(2)$	$\displaystyle\sum_{i\in I}x_{i}+x_{p}=\lambda(a).$

Also because $x_{p}\geq\lambda(a)$ and $x_{c}\leq 1$ for one $c\in I$, the set

$\displaystyle\mathcal{O}_{C,O}(P,\lambda)\cap H_{x_{p}=\lambda(a)}\cap H_{x_{c}=1}\bigcap_{i\in I\backslash\{c\}}H_{x_{i}=0}$

is a face of $\mathcal{O}_{C,O}(P,\lambda)$. If this face is not empty, there exists a vertex $w$ with $w_{p}=\lambda(a)$, $w_{c}=1$ and $w_{i}=0$ for $i\in I\backslash\{c\}$.
To show that this face is not empty, assume there exists no point $z\in\mathcal{O}(P\backslash C,\lambda)$ with $z_{p}=\lambda(a)$, such that $\exists c\in I$ with $v_{c}=1$ and $v_{i}=0$ for $i\in I\backslash\{c\}$ and $v\in\mathcal{C}(P,\lambda\sqcup z)$. That means, that for every $v_{c}$, there exists a chain with $c$ inside and the same upper and lower bound. Because of the full-dimensionality, this can only happen if at least one of these bounds is not $z_{p}=\lambda(a)$ and a bound introduced by a coordinate of $z$. But all coordinates of $z$ except $z_{p}$ can choose the two values $\lambda(a)$ and $\lambda(b)$. Therefore the assumption is not possible, because we can choose the coordinates of $z$, such that there is a chain with different upper and lower bounds.
We conclude, there exists a vertex $w$ with $w_{p}=\lambda(a)$, $w_{c}=1$ and $w_{i}=0$ for $i\in I\backslash\{c\}$. This vertex cannot lie in the hyperplane described by $\sum_{i\in I}x_{i}+x_{p}=\lambda(a)$. It holds

$\displaystyle\sum_{i\in I}w_{i}+w_{p}=1+\lambda(a)=\lambda(b).$

For facets of the form $\sum_{i\in I}x_{i}+\lambda(a)\leq x_{p}$ for a chain $I\subseteq C$ which starts in $a\in P^{*}$ and ends in $p\in O$, the proof that the upper bound and lower bound only differ by 1 is analogous.
The last facet we need to consider is a facet of the form $\sum_{i\in I}x_{i}+x_{p}\leq x_{q}$ for a chain $I\subseteq C$ with starts in $p\in O$ and ends in $q\in O$. The polytope $\mathcal{O}(P\backslash C,\lambda)$ is 2-level, therefore $x_{p}$ and $x_{q}$ have the same upper and lower bound. With this we can do a similar proof as before, to get that the bounds can only differ by 1. This concludes the proof. $\Box$

This theorem also includes Theorems 3.3 and Theorem 4.4, if we choose $C=\emptyset$ or $O=\emptyset$ respectively.

For an integral polytope $Q\subseteq\mathbb{R}^{d}$, whose vertices have integer coordinates. We denote the number of lattice points in $Q$ dilated by a factor $n\in\mathbb{Z}_{\geq 0}$ as

$$\text{Ehr}_{Q}(n):=|nQ\cap\mathbb{Z}^{d}|.$$

Ehrhart [ehrhart1962polyedres] discovered that $\text{Ehr}_{Q}(n)$ is a polynomial in $n$ of degree $\dim(Q)$. Therefore, we call $\text{Ehr}_{Q}(n)$ the Ehrhart polynomial of $Q$.

While working with marked order polytopes to prove the theorems of previous sections, we found a concrete formula for the Ehrhart polynomial of the marked order polytope. Since it is similar to the formula of order polytopes which was proven by Stanley [stanley1997enumerative, Thm 4.5.14], we will use some of his techniques and results.