Geometric Realizations of Dichotomous Ordinal Graphs

In this paper, we initiate the study of the pandichotomic dimension of graphs, with a focus on the bipartite case. In Section 3, we characterize the complete bipartite graphs that are pandichotomous in ${ℝ}^2$. Specifically, we show that $K_{m,n}$ is pandichotomous in ${ℝ}^2$ if and only if either (1) $m\le 3$ or (2) $m=4$ and $n\le 6$.

A dichotomous ordinal graph has two natural induced subgraphs: The short subgraph, induced by the short edges, and the long subgraph, induced by the long edges. In Section 4, we show that if either of these subgraphs is sufficiently constrained, then a realization in ${ℝ}^2$ always exists. Specifically, this is the case if (1) the graph is bipartite and the short subgraph is outerplanar (Theorem 8); (2) the short subgraph forms a subgraph of a rectangular grid (Theorem 9); or (3) the long subgraph forms a caterpillar (Theorem 10). In (1) and (2), we can also ensure that the short subgraph is realized without edge crossings. However, there are bipartite dichotomous ordinal graphs that do not admit a geometric realization in ${ℝ}^2$, even though the short subgraph is planar (see, e.g., Lemma 6).

In Section 5, we study the pandichotomic Euclidean dimension and show that it is very closely related to the degeneracy. A graph is $k$-degenerate if it can be constructed starting from the empty graph by iteratively applying the following operation: Add a new vertex and make it adjacent to at most $k$ existing vertices. The degeneracy $\mathrm{d}(G)$ of a graph $G$ is the smallest $k$ such that $G$ is $k$-degenerate.

We show that all $d$-degenerate graphs are pandichotomous on ${𝒮}^{d-1}$ and in ${ℝ}^d$, for $d\ge 2$ (Theorem 11). In particular, it follows that all bipartite planar graphs are pandichotomous on ${𝒮}^2$ and in ${ℝ}^3$ (Corollary 12). Our bounds imply $\mathrm{ped}(G)\le \mathrm{d}(G)$ and $\mathrm{psd}(G)\le \mathrm{d}(G)-1$, for every graph $G$ with $\mathrm{d}(G)\ge 2$. We also show that these bounds are tight for the sphere (Corollary 14) and for ${ℝ}^2$ (Theorem 15) and almost tight for ${ℝ}^d$, for $d\ge 3$ (Theorem 13).

We also show that every $n$-vertex graph that is pandichotomous in ${ℝ}^d$ has at most $\mu dn$ edges, for some constant  (Theorem 16), and this bound is optimal up to the value of $\mu$. In the special cases $d\in \{1,2\}$, this affirmatively answers two open problems posed explicitly by Alam, Kobourov, Pupyrev, and Toeniskoetter [3]. Consequently, $\mathrm{d}(G)/(2\mu )\le \mathrm{ped}(G)\le \mathrm{d}(G)$ and $\mathrm{d}(G)/(2\mu )-1\le \mathrm{psd}(G)\le \mathrm{d}(G)-1$, for every graph $G$ (Corollary 19). In other words, the pandichotomic Euclidean and spherical dimensions are linearly tied to the degeneracy. As a direct consequence of these bounds (Corollary 20), we determine up to a constant factor the smallest dimension $d$ for which every $n$-vertex (bipartite) dichotomous ordinal graph is realizable in ${ℝ}^d$ (or ${𝒮}^{d-1}$).

For $K_{3,m}$ we can draw $U=\{u_1,u_2,u_3\}$ so that all eight subsets of $U$ are realized; see Figure 2. Therefore, any dichotomous ordinal $K_{3,m}$ admits a geometric realization. For $|U|\ge 4$ such a universal placement is not possible because an arrangement of $n$ circles has at most $n(n-1)+2$ cells [22]. So an arrangement of four circles has at most $14$ cells, whereas a four-element set has $16$ subsets. However, for $|U|=4$ and $|W|\le 6$ we can always obtain a geometric realization as follows. Let $V(W)=\{V(w):w\in W\}\subset 2^U$.

If there are at least three pairs in $V(W)$, then, given that $|V(W)|\le |W|\le 6$, the number of triples plus the number of singletons in $V(W)$ together is at most three. Thus, as $|U|=4$, there exists a vertex $u\in U$ such that $\{u\}\notin V(W)$ and $U\setminus \{u\}\notin V(W)$. So we can use the drawing depicted in Figure 2, where we assign $u$ to the central disk. As all subsets of $U$ other than $\{u\}$ and $U\setminus \{u\}$ are realized, this is a valid geometric realization of $G$.

Otherwise, there are at most two pairs in $V(W)$. We use the drawing depicted in Figure 2, where we assign the vertices of $U$ to the disks so that both pairs in $V(W)$ appear consecutively in the circular order of disks. (This works regardless of whether or not these pairs share a vertex.) As all subsets of $U$ other than the two pairs that correspond to opposite circles in the drawing are realized, this is a valid geometric realization of $G$. $◀$

The following elementary lemma about unit disks turns out helpful.

Let $U=\{u_1,u_2,u_3,u_4\}$ and $W=\{w_1,\mathrm{\dots },w_7\}$ denote the vertex partition. For each $w_i$, we can specify an associated set $U_i\subseteq U$ (such that exactly the edges between $w_i$ and $U_i$ are short; see Figure 3). We choose all four subsets of size three and the three subsets of size two that contain $u_4$, and distribute them among the vertices of $W$ arbitrarily. In any geometric representation, each set $U_i$ corresponds to a cell in the induced arrangement $𝒞$ of unit circles. Two more cells are required implicitly: The outer cell, which corresponds to $\mathrm{\varnothing }\subset U$, and a cell that corresponds to the whole set $U$ and is required by Helly’s Theorem [11] because disks are convex and we specified all triples to be among the sets $U_i$. Using these properties of $𝒞$ we can show that it cannot be realized using unit circles. It is crucial that the circles must have the same radius: If arbitrary radii are allowed, then a geometric realization exists (Figure 2). $◀$

First we specify a dichotomous ordinal $K_{5,5}$, see Figure 3 for an illustration.

Let $U=\{u_1,u_2,u_3,u_4,u_5\}$ and $W=\{w_1,w_2,w_3,w_4,w_5\}$ denote the partition of the vertex set. To each $w_i\in W$, for $1\le i\le 5$, we associate a set $\alpha (w_i)\subseteq U$ as follows:

where $i\oplus 1=(imod\mathrm{\hspace{0.17em}4})+1$. Now consider an arbitrary but fixed geometric realization of this dichotomous ordinal $K_{5,5}$. In a slight abuse of notation we identify the vertices with the corresponding points in the geometric realization. Denote by $D_i$ the unit disk centered at $u_i$, which represents the region of points that are in short distance to $u_i$. Let $W^{-}=\{w_1,w_2,w_3,w_4\}$. As $W^{-}\subset D_5$, whereas $w_5\notin D_5$, by convexity of $D_5$ all points of $W^{-}$ lie in an open halfplane through $w_5$. Let ${\varphi }_1,{\varphi }_2,{\varphi }_3,{\varphi }_4$ denote the counterclockwise order of the points from $W^{-}$ around $w_5$ within this halfplane. By symmetry of $W^{-}$ we may assume that ${\varphi }_1=w_1$ without loss of generality. We consider two cases.

Then by symmetry between $u_1$ and $u_2$ we may assume without loss of generality that ${\varphi }_4=w_4$. See Figure 4 (left) for illustration. By convexity of $D_1$, the triangle $\mathrm{△}=w_1{w}_4{w}_5={\varphi }_1{\varphi }_4{w}_5$ is contained in $D_1$. As $w_2,w_3\notin D_1$, we have ${\varphi }_2,{\varphi }_3\notin \mathrm{△}$. As $w_2,w_3,w_5\in D_3$ but $w_1,w_4\notin D_3$, the circle $\partial D_3$ crosses the line segment $w_1{w}_4$ twice in $D_5$, and it also crosses both of the line segments ${\varphi }_1{\varphi }_2$ and ${\varphi }_3{\varphi }_4$. Similarly, as $\mathrm{△}\subset D_1$ but $w_2,w_3\notin D_1$, the circle $\partial D_1$ crosses both line segments $w_5{w}_2$ and $w_5{w}_3$, and it also crosses both of the line segments ${\varphi }_1{\varphi }_2$ and ${\varphi }_3{\varphi }_4$. Let $c$ denote the chord of $D_3$ induced by ${\varphi }_1{\varphi }_4$. As $D_1\supset c$, by Lemma 5 we know that $D_1$ contains the part $A$ of $D_3$ on the side of $c$ that does not contain the center of $D_3$. This is the part that contains $w_5$ because the other part contains ${\varphi }_2,{\varphi }_3\notin D_1$. Similarly, as $D_5\supset c$, by Lemma 5 it follows that also $D_5\supset A$, which is a contradiction to $w_5\notin D_5$. Thus, this case is impossible.

Then we have ${\varphi }_4=w_3$ and both $|\alpha ({\varphi }_1)\cap \alpha ({\varphi }_3)|=1$ and $|\alpha ({\varphi }_2)\cap \alpha ({\varphi }_4)|=1$. By symmetry we may assume without loss of generality that ${\varphi }_2=w_2$ and ${\varphi }_3=w_4$. See Figure 4 (right) for illustration. Consider the two disks $D_1$ and $D_3$. They both contain $w_5$, and so the corresponding circles $\partial D_1$ and $\partial D_3$ intersect all of the rays $w_5{\varphi }_i$, for $1\le i\le 4$. As ${\varphi }_1,{\varphi }_3\in D_1\setminus D_3$ and ${\varphi }_2,{\varphi }_4\in D_3\setminus D_1$, the rays $w_5{\varphi }_1$ and $w_5{\varphi }_3$ intersect $\partial D_1$ before $\partial D_3$, whereas the rays $w_5{\varphi }_2$ and $w_5{\varphi }_4$ intersect $\partial D_3$ before $\partial D_1$. But then $\partial D_1$ and $\partial D_3$ cross in each of the cones ${\varphi }_i{w}_5{\varphi }_{i+1}$, for $1\le i\le 3$, which is impossible, since any two distinct circles intersect in at most two points.

As we arrived at a contradiction in both cases, we conclude that no geometric realization of this dichotomous ordinal $K_{5,5}$ exists. If, however, we allow disks with arbitrary radii, then a geometric realization exists, as depicted in Figure 5. $◀$

Let $G=(V,E_s\cup E_{\mathrm{\ell }})$ be a bipartite dichotomous ordinal graph such that $G_s=(V,E_s)$ is outerplanar. By Observation 2, we may assume that $G_s$ is connected. We root $G_s$ at an arbitrary vertex $r$. Let $V_k$, $k=0,\mathrm{\dots }$, be the BFS layers of $G_s$ rooted at $r$, i.e., $V_0=\{r\}$, $V_1$ is the set of neighbors of $r$, and $V_{k+1}$, $k\ge 1$ is the set of neighbors of the vertices in $V_k$ that are not already in $V_{k-1}$. We say that $w$ is a child of $v$ and $v$ is a parent of $w$ if $vw$ is an edge of $G_s$, $v\in V_k$ and $w\in V_{k+1}$ for some $k$. By outerplanarity, each vertex has at most two parents. We construct a planar drawing of $G_s$ with the following properties.

• $\mathrm{■}$

  The root $r$ is drawn with y-coordinate $y_0=0$. All vertices in layer $V_k$, $k>0$ are on a horizontal line ${\mathrm{\ell }}_k$ with y-coordinate $y_k$ strictly between $k-1$ and $k$.

• $\mathrm{■}$

  The distance between a vertex and its children is at most 1 while the distance between two vertices on consecutive layers is greater than 1 if they are not adjacent in $G_s$.

• $\mathrm{■}$

  For each vertex $v$ there is a vertical strip $S_v$ such that

  • –

    $v$ is in $S_v$,

  • –

    $S_w$ is contained in the union of the strips of $w$’s parents,

  • –

    $S_u$ and $S_v$ are internally disjoint if $u$ and $v$ are on the same layer.

Special care has to be taken if a vertex $w\in V_{k+1}$ has two parents $u$ and $v$, i.e., if $w$ closes an internal face. In that case, we want to draw $w$ on line ${\mathrm{\ell }}_{k+1}$, on the common boundary of $S_u$ and $S_v$, and with distance exactly one to both $u$ and $v$. $◀$

Extend $G_s=(V,E_s)$ by the remaining grid edges and require the new edges to be long. Use the construction in Figure 6 to place the vertices. Then the short edges are shorter than $n^2+1/2$, while the long edges have length at least $n^2+1$. Scale the drawing. $◀$

We draw the vertices on a circle $C$ of radius $\frac{1}{2}+ϵ$, for some small $ϵ>0$. For each point $p\in C$ there is a region $R(p)\subset C$ around its antipodal point $\overline{p}$ such that for a point $q\in C$ we have $\Vert p-q\Vert >1\iff q\in R(p)$. We draw the vertices $v_1,\mathrm{\dots },v_k$ on the spine such that for $i=1,\mathrm{\dots },k-1$ the vertex $v_{i+1}$ lies at the counterclockwise boundary of $R(v_i)$. Then we place the leaves (if any) attached to $v_i$ within a very short arc around the point $v_i^{\prime }$ close to $\overline{v_i}$. More precisely, we obtain $v_i^{\prime }$ by shifting $\overline{v_i}$ counterclockwise along $C$ by a small angle that monotonically increases with $i$. In this way, we ensure that the leaves of $v_i$ are far from $v_i$ but close to the leaves of the neighbors of $v_i$ along the spine. $◀$

Let $G$ be a $d$-degenerate dichotomous ordinal graph, for $d\ge 2$, and let $u_1,\mathrm{\dots },u_n$ be a vertex ordering such that $u_i$ has at most $d$ neighbors in $\{u_1,\mathrm{\dots },u_{i-1}\}$, for $1\le i\le n$. To obtain a geometric realization of $G$ we place the vertices on the sphere $S=\{p\in {ℝ}^d:\parallel p\parallel =\sqrt{2}/2\}$ such that for every $d$-tuple of vertices the corresponding vectors are linearly independent. For a vertex $p\in S$ denote by ${\overrightarrow{v}}_p$ the corresponding vector; the points in distance less than one to $p$ on $S$ form a hemisphere, which consists of all points $q\in S$ such that ${\overrightarrow{v}}_p{\overrightarrow{v}}_q>0$, where ${\overrightarrow{v}}_p{\overrightarrow{v}}_q$ denotes the scalar product between ${\overrightarrow{v}}_p$ and ${\overrightarrow{v}}_q$.

We place the vertices $u_1,\mathrm{\dots },u_n$ in this order. The first vertex $u_1$ is placed arbitrarily on $S$. Then for each $u_i$, for $2\le i\le n$, we have a set $Q=\{q_1,\mathrm{\dots },q_t\}\subset S$ of points, which correspond to the $t\le d$ neighbors of $u_i$ in $u_1,\mathrm{\dots },u_{i-1}$. Further, for each point in $Q$ we know whether it should be close to or far from $u_i$. Now we need to find a suitable point on $S$ that satisfies these constraints. We obtain the set $Q^{\prime }=\{q_1^{\prime },\mathrm{\dots },q_t^{\prime }\}$ from $Q$ by setting $q_j^{\prime }=q_j$, if $q_j$ should be close to $u_i$ and setting $q_j^{\prime }$ to the point antipodal to $q_j$ on $S$ if $q_j$ should be far from $u_i$. As $Q$ is linearly independent, so is $Q^{\prime }$. Furthermore, the linear system ${\overrightarrow{v}}_{q_j^{\prime }}\overrightarrow{x}=\overrightarrow{1}$, for $1\le j\le t$, has a (unique) solution ${\overrightarrow{x}}_0$. Normalizing ${\overrightarrow{x}}_0$ we obtain a point $r\in S$, such that ${\overrightarrow{v}}_r{\overrightarrow{v}}_{q_j^{\prime }}>0$, for all $1\le j\le t$. Thus, we can place $u_i$ at $r$ such that all constraints with respect to $Q$ are satisfied. The points on $S$ that lie in a $k$-dimensional subspace spanned by $k$ vertices, for , can easily be avoided when selecting $r$. In this way we ensure that for all $d$-tuples of vertices on $S$ the corresponding vectors are linearly independent. This realization also works for geodesic distances on ${𝒮}^{d-1}$ if we take an arc with angle $\pi /2$ as a unit. $◀$

Let $G=(V,E)$ be a planar bipartite graph on $n$ vertices. As a consequence of Euler’s formula, we have $|E|\le 2n-4$. By the handshaking lemma ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|\le 4n-8$ and, thus, the average degree in $G$ is strictly less than $4$. Consequently, every planar bipartite graph is $3$-degenerate, and the statement follows by Theorem 11. $◀$

We contrast the upper bound on the pandichotomic dimension in terms of the degeneracy provided by Theorem 11 by an almost matching lower bound in the Euclidean (Theorem 13) and a matching lower bound in the spherical case (Corollary 14), even for bipartite graphs. Note that every lower bound example is not just sporadic but spans an infinite family of examples, given that being pandichotomous is a monotone graph property.

We build a graph $G=(V,E)$ starting with a set $V_0$ of $d+2$ isolated vertices. Then for each of the $2^{d+2}$ many choices of assigning short or long to the vertices of $V_0$ we add a new vertex and connect it by edges to $V_0$ accordingly. Observe that $G$ is bipartite and $(d+2)$-degenerate by construction. Consider a geometric realization of $G$ and the corresponding arrangement $𝒜$ of the $d+2$ unit spheres centered at the vertices of $V_0$. In order to bound the number of full-dimensional cells in $𝒜$, we consider the standard parabolic lifting map $\lambda$, which orthogonally projects a point in ${ℝ}^d$ to the unit paraboloid in ${ℝ}^{d+1}$. This map has a number of useful properties, see, for instance, Edelsbrunner’s book [8, Section 1.4]. Specifically, the image $\lambda (S)$ of a sphere $S\subset {ℝ}^d$ lies on a hyperplane $h_S\subset {ℝ}^{d+1}$ such that a point $p\in {ℝ}^d$ lies inside $S$ if and only if its image $\lambda (p)$ lies below $h_S$. It follows that we may regard $𝒜$ as an arrangement of $d+2$ hyperplanes in ${ℝ}^{d+1}$. As such an arrangement has at most  many full-dimensional cells [16, Proposition 6.1.1], for at least one of the vertices in $V\setminus V_0$ its distance requirements with respect to $V_0$ are violated. Thus, there is no geometric realization of $G$ in ${ℝ}^d$. $◀$

We use the same graph $G$ as in the proof of Theorem 13, except that we start with a set $V_0$ of $d+1$ rather than $d+2$ isolated vertices. We consider ${𝒮}^{d-1}$ as a unit sphere $S\subset {ℝ}^d$. For a point $p\in S$, the set of points on $S$ in distance at most some fixed unit from $p$ can be expressed as an intersection $S\cap u_p$ where $u_p$ is a halfspace.

Suppose there is some geometric realization of $G$, and let $P\subset S$ denote the set of $d+1$ points that represent the vertices of $V_0$ in this realization. Consider the set $H$ of the $d+1$ bounding hyperplanes of the halfspaces $u_p$, for $p\in P$. The arrangement $𝒜$ of $H$ has at most  many full-dimensional cells [16, Proposition 6.1.1]. Thus, for at least one of the vertices in $V\setminus V_0$ there is no cell that satisfies its distance requirements with respect to $V_0$. It follows that there is no geometric realization of $G$ in ${𝒮}^{d-1}$. $◀$

In the Euclidean case, we give a tight lower bound in ${ℝ}^2$, albeit not for bipartite graphs.

We build a dichotomous ordinal graph $G$ on eight vertices as follows (Figure 8). Start with a set $V=\{v_1,v_2,v_3\}$ and a complete graph on $V$, all edges long. Then insert a vertex $c$ and connect it to all vertices in $V$ by a short edge. Next, insert a set $W=\{w_1,w_2,w_3\}$ of vertices as follows: the vertex $w_i$, for $i\in \{1,2,3\}$, is connected to $c$ by a long edge and to each vertex in $V_i^{-}:=V\setminus \{v_i\}$ by a short edge. Finally, we add a vertex $x$ that is connected to all vertices in $W$ by a short edge. Observe that $G$ is $3$-degenerate as constructed.

Consider any geometric realization $\mathrm{\Gamma }$ of $G$. In a slight abuse of notation we identify the vertices of $G$ with the corresponding points that represent them in $\mathrm{\Gamma }$. For a set $P\subset {ℝ}^2$ denote $I(P)={\bigcap }_{p\in P}\mathrm{B}(p,1)$ and $U(P)={\bigcup }_{p\in P}\mathrm{B}(p,1)$. As $x\in I(W)$, we have $I(W)\ne \mathrm{\varnothing }$ and $U(W)$ is simply connected. The constraints imposed by $G$ enforce $c\notin U(W)$ and $V\subset \mathrm{B}(c,1)\cap U(W)$. In particular, for each $i\in \{1,2,3\}$, the set $V_i^{-}$ is contained in the lens $L_i=I(\{c,w_i\})$. As $c\notin U(W)$, each $L_i$ has diameter strictly smaller than $\sqrt{3}$. Any lens in ${ℝ}^2$ of diameter strictly smaller than $\sqrt{3}$ contains at most two points at a pairwise distance at least one. Thus, in particular, we have $v_i\notin L_i$, for all $i\in \{1,2,3\}$.

We analyze the interaction of the circles $S_i=\mathrm{S}(w_i,1)$, for $i\in \{1,2,3\}$, with $C=\mathrm{S}(c,1)$. As $|L_i\cap V|\ge 2$ and as any two points in $V$ are at distance strictly larger than one, we have $|S_i\cap C|=2$, for all $i\in \{1,2,3\}$. As $c\notin U(W)$ and as $U(W)$ is simply connected, some part of $C$ is disjoint from $U(W)$. We use such a part to break up the circular sequence of intersection points between $C$ and the $S_i$ into a linear sequence $ℐ$ of six points (some but not all of which may coincide). On the one hand, as $|L_i\cap V|\ge 2$, for all $i\in \{1,2,3\}$, and as $|V|=3$, we have $L_i\cap L_j\ne \mathrm{\varnothing }$, for all $i,j\in \{1,2,3\}$. On the other hand, if $L_i\subseteq L_j$, for some $i,j\in \{1,2,3\}$ with $i\ne j$, then, given that $v_j\in V_i$ we also have $v_j\in L_j$, a contradiction. It follows that up to the indexing of $W$ we have $ℐ=1,2,3,1,2,3$, where we write an integer $i$ to indicate an intersection $C\cap S_i$.

Let $q$ denote the intersection point of $S_1\cap S_3$ in $\mathrm{B}(c,1)$. Note that $q\notin L_2$ because $q\in L_2$ would imply $L_1\cap L_3\subseteq L_2$ and thus $v_2\in L_2$, a contradiction. We continuously move a unit disk $D$ starting from $D=\mathrm{B}(w_2,1)$ towards $c$ such that the center $d$ of $D$ is on the line segment $w_{2}c$. We stop the movement as soon as $d\in \mathrm{S}(q,1)$. This process is well defined because $q\notin \mathrm{B}(w_2,1)$ and $q\in L_1\cap L_3\subset \mathrm{B}(c,1)$. Furthermore, during the whole movement we have $L_2\subset D\subset U(W)$ and the disk $D^{\prime }$ at the end of the movement also contains $L_1\cap L_3$. Thus, the lens $L=D^{\prime }\cap \mathrm{B}(c,1)$ contains all of $V$ and given that $L\subset U(W)$ it has diameter strictly smaller than $\sqrt{3}$, a contradiction. $◀$

The examples discussed above demonstrate that the bound from Theorem 11 is tight in the worst case, that is, for some graphs. In the following, we will show that the bound is also tight for all graphs, up to a multiplicative constant. We first estimate the edge density of pandichotomous graphs in ${ℝ}^d$ and show that it is linearly bounded in $d$. In fact, we prove a stronger result, namely that every sufficiently dense graph $G$ not only is not pandichotomous in ${ℝ}^d$, but in fact, asymptotically almost all partitions of the edge-set of $G$ into short and long edges yield dichotomous ordinal graphs that are not realizable in ${ℝ}^d$.

In the proof of Theorem 16, we will use the following result by Warren [25] on the number of sign-patterns of a collection of multivariate polynomials.

The following is an immediate consequence of the above.

Let $X:=\{𝐱\in {ℝ}^N|\forall i\in \{1,\mathrm{\dots },m\}:q_i(𝐱)\ne 0\}$. Consider the map $f:X\to {\{+1,-1\}}^m$, defined by $f(𝐱)=(\mathrm{sgn}(q_1(𝐱)),\mathrm{\dots },\mathrm{sgn}(q_m(𝐱)))$. It is easy to see, using the continuity of the polynomials $q_1,\mathrm{\dots },q_m$, that $f$ is continuous. Let $C$ be a topological component of $X$. The restriction of $f$ to $C$ is a continuous map on a connected topological space that takes on only finitely many (at most $2^m$) values. Since every such map is constant, we find that $f$ is constant on every component of $X$. Hence, the size of $𝒮=\mathrm{im}(f)$ is bounded by the number of components of $X$. The statement now follows from Theorem 17. $◀$

Assume w.l.o.g. that $G=(V,E)$ has vertex set $V=\{1,\mathrm{\dots },n\}$. Let $({𝐱}_1,\mathrm{\dots },{𝐱}_n)$ be an $n$-tuple of points in ${ℝ}^d$, no two of which are at distance exactly one. The distance-pattern of $({𝐱}_1,\mathrm{\dots },{𝐱}_n)$ w.r.t. $G$ is the map $s_G({𝐱}_1,\mathrm{\dots },{𝐱}_n):E\to \{+1,-1\}$, where

for every edge $ij\in E$. In other words, given a configuration of points $({𝐱}_1,\mathrm{\dots },{𝐱}_n)$ in ${ℝ}^d$, the distance-pattern captures the information of which edges of $G$ in a geometric realization placing vertices $1,\mathrm{\dots },n$ at points ${𝐱}_1,\mathrm{\dots },{𝐱}_n$, respectively, are long or short.

Next, we estimate the size of the set $𝒮$ of all possible distance-patterns for $G$. Concretely, $𝒮$ is the set of all mappings $s_G({𝐱}_1,\mathrm{\dots },{𝐱}_n)$ where $({𝐱}_1,\mathrm{\dots },{𝐱}_n)$ ranges over all $n$-tuples of points in ${ℝ}^d$, no two of which are at distance $1$. Let us denote by $M$ the number of partitions $E_s\cup E_{\mathrm{\ell }}=E$ of the edge-set of $G$ such that the dichotomous ordinal graph $(V,E_s\cup E_{\mathrm{\ell }})$ is realizable in ${ℝ}^d$. Let $p$ denote the fraction of such partitions compared to all possible partitions of $E$. Note that $M=p{2}^m$ and that $p=1$ if and only if $G$ is pandichotomous.

Consider any one of the $M$ partitions $E_s\cup E_{\mathrm{\ell }}$ of the edge-set $E$ for which $(V,E_s\cup E_{\mathrm{\ell }})$ is realizable in ${ℝ}^d$. By Observation 1 we may assume a threshold of $\delta =1$ and that we use a set of points with no unit distances. The distance-pattern of the corresponding tuple of $n$ points in $d$-space then has value $+1$ for every long and $-1$ for every short edge.

Since any two distinct partitions of $E$ into short and long edges result in different distance-patterns in $𝒮$ this way, it follows that $|𝒮|\ge M$, as claimed. $\mathrm{⊲}$

Next, we obtain an upper bound on $|𝒮|$ using Theorem 17.

For any two points $𝐱,𝐲\in {ℝ}^d$, we have $\Vert 𝐱-𝐲\Vert >1$ if and only if ${\Vert 𝐱-𝐲\Vert }^2-1>0$, and if and only if . Further, the expression

is a polynomial of degree two in the coordinates of $𝐱,𝐲$. It is therefore natural to associate with every edge $ij\in E$ of $G$ a polynomial $q_{i,j}$, defined as $q_{i,j}({𝐱}_1,\mathrm{\dots },{𝐱}_n):={\Vert {𝐱}_i-{𝐱}_j\Vert }^2-1$. The collection $\left(q_{i,j}|ij\in E\right)$ then forms a set of $m$ polynomials, each of degree $2$, in the $N:=dn$ variables corresponding to the coordinates of ${𝐱}_1,\mathrm{\dots },{𝐱}_n$. For every tuple $({𝐱}_1,\mathrm{\dots },{𝐱}_n)$ of points in ${ℝ}^d$, no two at unit distance, we have $s_G({𝐱}_1,\mathrm{\dots },{𝐱}_n)(ij)=\mathrm{sgn}(q_{i,j}({𝐱}_1,\mathrm{\dots },{𝐱}_n))$.

Hence, the set $𝒮$ defined before coincides with the set $𝒮$ defined in Corollary 18 for the collection $\left(q_{i,j}|ij\in E\right)$ of $m$ multivariate polynomials. We therefore obtain, using the degree bound $2$ for the polynomials,

$\mathrm{⊲}$

Using Claims 1 and 2, we obtain the inequality

Since $c>2$, we have $m\ge (c+\epsilon )dn>2dn$. This implies that the term $\left(\genfrac{}{}{0pt}{}{m}{k}\right)$ is monotonically increasing for $k=0,1,\mathrm{\dots },dn$. Hence, we may bound the right hand side above by

Let $x:=\frac{m}{dn}\ge c+\epsilon$. Using the estimate $\left(\genfrac{}{}{0pt}{}{a}{\lambda a}\right)\le 2^{aH(\lambda )}$, which holds for any $a\in \mathbb{N}$ and $\lambda \in (0,1)$, see e.g., [17, Lemma 9.2], we find

Taking logarithms and dividing by $dn$ this simplifies to

Consider the function $f(x)=x-3-x\cdot H(1/x)=x-3-x{\log }_{2}x+(x-1){\log }_2(x-1)$. Observe that $f$ is strictly monotonically increasing and continuous for $x\ge 2$ and that it has a unique positive root $c\approx 7.1815$.

It follows that $f(c+\epsilon )>f(c)=0$, and, since $x\ge c+\epsilon$, Equation 1 above implies that

Since the right hand side of the last inequality tends to $-\mathrm{\infty }$ as $dn\to \mathrm{\infty }$, it follows that $p\to 0$ for $dn\to \mathrm{\infty }$. Hence, it is indeed true that asymptotically almost all partitions $E_s\cup E_{\mathrm{\ell }}=E$ of the edge-set of $G$ into short and long edges yield dichotomous ordinal graphs with no geometric representation in ${ℝ}^d$. This completes the proof of the first statement.

It remains to show that if $G$ is pandichotomous ($p=1$), then the explicit bound $m\le \mu dn$ with $\mu :=7.2240208$ holds for all $n\in \mathbb{N}$ and $d\ge 2$. Set $\varphi (z)=2/z$ and observe that $\varphi \to 0$ for $z\to \mathrm{\infty }$. We can then express Equation 1 as . The trivial bound $m\le \left(\genfrac{}{}{0pt}{}{n}{2}\right)$ suffices to show that $m\le \mu dn$, unless , i.e., unless $\lceil 4\mu +1\rceil \le n$. As $\varphi$ is monotonically decreasing, it follows that . For the value $\mu =7.2240208$ we obtain , whereas $f(\mu )>0.033333334>1/30$. Therefore, as $f$ is monotonically increasing, it follows that , as claimed. $◀$

By Theorem 16 every graph $G$ that is pandichotomous in ${ℝ}^d$ has at most $\mu dn$ edges, for some absolute constant . Thus, the minimum degree of $G$ is at most $\lfloor 2\mu d\rfloor$ and so $G$ is $k$-degenerate, for $k=\lfloor 2\mu d\rfloor$. This implies $\mathrm{d}(G)\le 2\mu \cdot \mathrm{ped}(G)$ and so $\frac{\mathrm{d}(G)}{2\mu }\le \mathrm{ped}(G)\le \mathrm{d}(G)$. Since $\mathrm{psd}(G)\ge \mathrm{ped}(G)-1$ we obtain the lower bound for the spherical dimension. The upper bounds follow from Theorem 11. $◀$