Levels in Arrangements: Linear Relations, the $g$-Matrix, and Applications to Crossing Numbers

Throughout this paper, let $r=d+1⩾1$, and let $S^d$ be the unit sphere in ${𝐑}^r$. We denote the standard inner product in ${𝐑}^r$ by $⟨\cdot ,\cdot ⟩$, and write $\mathrm{sgn}(x)\in \{-1,0,+1\}$ for the sign of a real number $x\in 𝐑$. For a sign vector $F\in {\{-1,0,+1\}}^n$, let $F_{+}$, $F_0$, and $F_{-}$ denote the subsets of coordinates $i\in [n]$ such that $F_i=+1$, $F_i=0$, and $F_i=-1$, respectively.

Let $V=\{v_1,\mathrm{\dots },v_n\}\subset {𝐑}^r$ be a set of $n⩾r$ vectors; fixing the labeling of the vectors, we will also view $V$ as a matrix $V=[v_1|\mathrm{\dots }|v_n]\in {𝐑}^{r\times n}$ with columns $v_i$. Unless stated otherwise, we assume that $V$ is in general position, i.e., that any $r$ of the vectors are linearly independent. We refer to $V$ as a vector configuration of rank $r$.

Every vector $v_i\in V$ defines a great $(d-1)$-sphere $H_i=\{x\in S^d\mid ⟨v_i,x⟩=0\}$ in $S^d$ and two open hemispheres

The resulting arrangement $𝒜(V)=\{H_1^{+},\mathrm{\dots },H_n^{+}\}$ of hemispheres in $S^d$ determines a decomposition of $S^d$ into faces of dimensions $0$ through $d$, where two points $u,u^{\prime }\in S^d$ lie in the relative interior of the same face of $𝒜(V)$ iff $\mathrm{sgn}(⟨v_i,u⟩)=\mathrm{sgn}(⟨v_i,u^{\prime }⟩)$ for $1⩽i⩽n$. Let $ℱ(V)$ be the set of all sign vectors $(\mathrm{sgn}(⟨v_1,u⟩),\mathrm{\dots },\mathrm{sgn}(⟨v_n,u⟩))\in {\{-1,0,+1\}}^n$, where $u$ ranges over all non-zero vectors (equivalently, unit vectors) in ${𝐑}^r$; we can identify each face of $𝒜(V)$ with its signature $F\in ℱ(V)$. By general position, the face with signature $F$ has dimension $d-|F_0|$ (the arrangement is simple, i.e., there are no faces with $|F_0|>d$). Moreover, we call $|F_{-}|$ the level of the face. Equivalently, the elements of $ℱ(V)$ correspond bijectively to the partitions of $V$ by oriented linear hyperplanes, and we will also call them the dissection patterns of $V$. In what follows, we will pass freely back and forth between a vector configuration $V$ and the corresponding arrangement $𝒜(V)$ and refer to this correspondence as polar duality (to distinguish it from Gale duality, see below).

We call a vector configuration $V$ pointed if it is contained in an open linear halfspace $\{x\in {𝐑}^r:⟨u,x⟩>0\}$, for some $u\in S^d$, or equivalently, if ${\bigcap }_{i=1}^n{H}_i^{+}\ne \mathrm{\varnothing }$. The closure of this intersection is then a simple (spherical) polytope $P$, the $0$-level of $𝒜(V)$. By radial projection onto the tangent hyperplane $\{x\in {𝐑}^r:⟨u,x⟩=1\}$, every pointed configuration $V\subset {𝐑}^r$ corresponds to a point set $S\subset {𝐑}^d$, see [30, Sec. 5.6]. The convex hull $P^{\circ }=\mathrm{conv}(S)$ is a simplicial polytope (the polar dual of $P$), and the elements of $ℱ(V)$ correspond to the partitions of $S$ by affine hyperplanes; in particular, $f_{s,0}(V)$ counts the $(s-1)$-dimensional faces of $P^{\circ }$, and $f_{0,k}(V)$ counts the $k$-sets of $S$.

The following two special vector configurations will play an important role in this paper.

Cyclic and cocyclic configurations are examples of neighborly and coneighborly configurations, which we define next. Let $V=\{v_1,\mathrm{\dots },v_n\}\subseteq {𝐑}^r$ be a vector configuration in general position. A subset $W\subseteq V$ is extremal if there exists a linear hyperplane $H$ bounding an open halfspace $H^{+}$ such that $W\subset H$ and $V\setminus W\subset H^{+}$. In particular, $V$ is pointed iff $\mathrm{\varnothing }\subset V$ is extremal.

Cyclic configurations are neighborly, cocyclic configurations are coneighborly [48, Cor. 0.8], and these notions are Gale dual to each other (see Section 2). Every neighborly vector configuration $V\subset {𝐑}^r$ is pointed, hence corresponds to a point set $S\subset {𝐑}^d$, $d=r-1$, and $V$ being neighborly means the simplicial $d$-polytope $\mathrm{conv}(S)$ is a neighborly polytope, i.e., every subset of $S$ of size at most $\lfloor \frac{d}{2}\rfloor$ forms a face. We note that for $r=1,2$ ($d=0,1$) neighborliness is the same as being pointed, and for $r=3,4$ ($d=2,3$) $V$ is neighborly iff the point set $S$ is in convex position. By a celebrated result of McMullen [31] neighborly polytopes maximize the number of faces of any dimension:

Eckhoff [20, Conj. 9.8], Linhart [26], and Welzl [46], independently of one another (and in slightly different forms) conjectured a far-reaching generalization of Theorem 4 for sublevels of arrangements. To state this conjecture, let $f_{s,⩽k}(V):={\sum }_{t⩽k}{f}_{s,t}(V)$.

A random sampling argument due to Clarkson (see [18]) shows that Conjecture 5 is true asymptotically, for fixed $r$ and $n,k\to \mathrm{\infty }$, up to a constant factor depending on $r$. For the case $s=d$ of vertices at sublevel $(⩽k)$, Conjecture 5 was proved by Peck [36] and by Alon and Győri [10] for $r⩽3$ and by Welzl [46] for pointed vector configurations in rank $r=4$. The second author [44] proved that it is true up to a factor of $4$ for arbitrary rank $r$. Here, we prove the conjecture for corank $n-r=3$.

By Gale duality (see Section 2), Theorem 6 yields the following result about crossing numbers.

Determining the crossing number $\mathrm{cr}(K_n)$ of the complete graph $K_n$ (the minimum number of crossings in any drawing of $K_n$ in the plane, or equivalently in the sphere $S^2$, with edges represented by arbitrary Jordan arcs) is one of the foundational unsolved problems in geometric graph theory, first studied by Hill in the 1950’s. Hill conjectured the following:

This is known to hold for $n⩽12$, but remains open in general (see [37, Sec. 1.3] or [42] for further background and references). There are several families of drawings showing that $\mathrm{cr}(K_n)⩽X(n)$ for all $n$, but the best lower bound to date [14] is $\mathrm{cr}(K_n)⩾0.985\cdot X(n)$.

We prove Hill’s conjecture for the following class of drawings. Let $V=\{v_1,\mathrm{\dots },v_n\}\subset S^2$ be a configuration of $n$ unit vectors in general position. If we connect every pair of vectors in $V$ by the shortest geodesic arc between them in $S^2$ (which is unique, since no two vectors are antipodal, by general position) we obtain a drawing of the complete graph $K_n$ in $S^2$, which we call a spherical arc drawing. Let $\mathrm{cr}(V)$ denote the number of crossings in this drawing.

The fact that coneighborly configurations yield spherical arc drawings of $K_n$ achieving the number $X(n)$ of crossings in Hill’s conjecture, and the connection to the Eckhoff–Linhart–Welzl conjecture were first observed by Wagner [44, 45]. It is known [35] that there are at least $n^{\frac{3}{2}(1-o(1))n}$ combinatorially different coneighborly configurations of $n$ vectors in $S^2$.

Spherical arc drawings generalize the well-studied class of rectilinear drawings of $K_n$ (given by $n$ points in general position in ${𝐑}^2$ connected by straight-line segments), which correspond to spherical arc drawings given by pointed vector configurations $V\subset S^2$.

Theorem 9 complements earlier results of Lovász, Vesztergombi, Wagner, and Welzl [29] and Ábrego and Fernández-Merchant [6], who showed that the rectilinear crossing number $\overline{\mathrm{cr}}(K_n)$ (the minimum number of crossings in any rectilinear drawing of $K_n$) is at least $X(n)$; in fact, $\overline{\mathrm{cr}}(K_n)⩾(\frac{3}{8}+\epsilon +o(1))\left(\genfrac{}{}{0pt}{}{n}{4}\right)$ for some constant $\epsilon >0$ [29]. Thus, unlike the spherical arc crossing number, the rectilinear crossing number $\overline{\mathrm{cr}}(K_n)$ is strictly larger than $X(n)⩾\mathrm{cr}(K_n)$ in the asymptotically leading term. We refer to [8] for a detailed survey, including a series of subsequent improvements [15, 9, 7, 4] leading to the currently best bound [5] $\overline{\mathrm{cr}}(K_n)>277/729\left(\genfrac{}{}{0pt}{}{n}{4}\right)+O(n^3)>0.37997\left(\genfrac{}{}{0pt}{}{n}{4}\right)+O(n^3)$. We remark that the arguments in [29, 6] have been generalized to verify Hill’s conjecture for other classes of drawings, including $2$-page drawings [2], monotone drawings [13], cylindrical, $x$-bounded, and shellable drawings [3], bishellable drawings [1], and seq-shellable drawings [34]. Currently we do not know how spherical arc drawings relate to these other classes of drawings.

The central notion of this paper is the $g$-matrix $g(V\to W)$ of a pair $V,W\in {𝐑}^{r\times n}$ of vector configurations, which encodes the difference $f(W)-f(V)$ between the $f$-matrices. The geometric definition of the $g$-matrix is given in Sec. 3, based on how the $f$-matrix changes by mutations in the course of generic continuous motion (an idea with a long history, see, e.g., [11]). The $g$-matrix is characterized by the following properties:

Linear relations between face numbers of levels in simple arrangements have been studied extensively [33, 24, 27, 12, 16].

The first set of linear relations is given by the antipodal symmetry $F\leftrightarrow -F$ of $ℱ(V)$:

Moreover, it is well-known [23, Sec. 18.1] that the total number of faces of a given dimension $d-s$ (of any level) in a simple arrangement in $S^d$ depends only on $n$, $d$, and $s$:

Linhart, Yang, and Philipp [27] proved the following result, which generalizes the classical Dehn–Sommerville relations for simple polytopes:

Let ${𝒱}_{n,r}$ denote the set of vector configurations $V\in {𝐑}^{r\times n}$ in general position. Let

be the affine space spanned by all $f$-matrices, and the linear space spanned by all $g$-matrices of pairs, respectively. Let ${𝒱}_{n,r}^0\subset {𝒱}_{n,r}$ be the subset of pointed configurations, and let

be the corresponding subspaces of ${𝔉}_{n,r}$ and ${𝔊}_{r,n}$. Answering a question posed by Andrzejak and Welzl [12], we determine these spaces:

As a specific base configuration $V_0$ in both theorems, one can take the cyclic vector configuration $V_{\text{cyclic}}(n,r)$ (see Example 2), whose $f$-matrix is known explicitly [12].

Any two configurations $V=\{v_1,\mathrm{\dots },v_n\}$ and $W=\{w_1,\mathrm{\dots },w_n\}$ of $n$ vectors in general position in ${𝐑}^r$ can be deformed into one another through a continuous family $V(t)=\{v_1(t),\mathrm{\dots },v_n(t)\}$ of vector configurations, where $v_i(t)$ describes a continuous path from $v_i(0)=v_i$ to $v_i(1)=w_i$ in ${𝐑}^r$. If we choose this continuous motion sufficiently generically, then there is only a finite set of events , called mutations, during which the combinatorial type of $V(t)$ (which is encoded by $ℱ(V(t))$), changes, in a controlled way (see Figures 1 and 2 for an illustration in the case $d=2$). Specifically, during a mutation, a unique $r$-tuple of vectors in $V(t)$, indexed by some $R=\{i_1,\mathrm{\dots },i_r\}\subset [n]$, momentarily becomes linearly dependent and the orientation of this $r$-tuple (i.e., the sign of $det[v_{i_1}|\mathrm{\dots }|v_{i_r}]$) changes, while the orientations of all other $r$-tuples of vectors remain unchanged. Thus, any two vector configurations are connected by a finite sequence $V=V_0,V_1,\mathrm{\dots },V_N=W$ such that $V_{s-1}$ and $V_s$ differ by a mutation, $1⩽s⩽N$.

We describe the change from $ℱ(V)$ to $ℱ(W)$ when $V$ and $W$ differ by a mutation. Let $R\in \left(\genfrac{}{}{0pt}{}{[n]}{r}\right)$ index the unique $r$-tuple of vectors that become linearly dependent. In terms of the polar dual arrangements, this means that the $r$-tuple of great $(d-1)$-spheres $H_i$, $i\in R$, momentarily intersect in an antipodal pair $u,-u$ of points in $S^d$. Immediately before and immediately after the mutation, these $r$ great $(d-1)$-spheres bound an antipodal pair of simplicial $d$-faces $\sigma ,-\sigma$ in $𝒜(V)$ and a corresponding pair of simplicial $d$-faces $\tau ,-\tau$ in $𝒜(W)$, respectively. We have $F\in ℱ(V)\setminus ℱ(W)$ iff the face of $𝒜(V)$ with signature $F$ is contained in $\sigma$ or $-\sigma$, and $F\in ℱ(W)\setminus ℱ(V)$ iff the face of $𝒜(W)$ with signature $F$ is contained in $\tau$ or $-\tau$. All other faces are preserved, i.e., they belong to $ℱ(V)\cap ℱ(W)$.

Let $Y\in ℱ(W)$ be the signature of $\tau$. We define a partition $[n]=I\bigsqcup J\bigsqcup A\bigsqcup B$ by

Define $j:=|J|$ and $k:=|B|$. We call the pair $(j,k)$ the type of the simplicial face $\tau$. The signature $X\in ℱ(V)$ of the corresponding simplicial face $\sigma$ of $𝒜(V)$ satisfies $X_i=-Y_i$ for $i\in R$ and $X_i=Y_i$ for $i\in [n]\setminus R$. Thus, $\sigma$ is of type $(r-j,k)$. Analogously, $-\tau$ and $-\sigma$ are of type $(r-j,n-r-k)$ and $(j,n-r-k)$, respectively, see Figures 1 and 2.

Let us define $f_{\sigma }(x,y):={\sum }_{F\subseteq \sigma }{x}^{|F_0|}{y}^{|F_{-}|}$, where we use the notation $F\subseteq \sigma$ to indicate that the sum ranges over all $F\in ℱ(V)$ corresponding to faces of $𝒜(V)$ contained in $\sigma$. The polynomials $f_{-\sigma }(x,y)$, $f_{\tau }(x,y)$, and $f_{-\tau }(x,y)$ are defined analogously. These four polynomials have a simple form:

We say that the mutation $V\to W$ is of Type $(j,k)\equiv (r-j,n-r-k)$. The reverse mutation $W\to V$ is of Type $(r-j,k)\equiv (j,n-r-k)$. We can summarize the discussion as follows:

Note that the right-hand side of (14) is zero if $2j=r$ or $2k=n-r$.

We are now ready to define the $g$-matrix $g(V\to W)$ of a pair of vector configurations.