Keywords: Combinatorial Fiedler theory, Optimization, Polyhedral geometry.

1 Introduction↩︎

Spectral graph theory studies graphs through the eigenvalues and eigenvectors of matrices naturally associated with them, such as the adjacency and Laplacian matrices. An early central example of this approach is Fiedler’s algebraic connectivity \(a(G)\) [1], the second-smallest Laplacian eigenvalue, which admits a Rayleigh quotient characterization as a minimization problem; more precisely, let \(G=(V,E)\) be a simple graph, then \[a(G) = \min_{\boldsymbol{x}\in\mathbf{R}^V} \left\{\sum_{uv\in E}(x_u-x_v)^2~:~\sum_{v\in V}x_v=0~\wedge~\sum_{v\in V}x_v^2=1\right\};\] see [2] for a systematic treatment. The corresponding eigenvectors, now called Fiedler vectors, assign a real coordinate to each vertex and can therefore be interpreted as one-dimensional representations of the graph. This interpretation underlies their use in graph partitioning and graph drawing [3], [4].

A recent contribution of Andrade and Dahl [5] initiates what they call combinatorial Fiedler theory, replacing the \(\ell_2\)-norm in the classical characterization of the \(a(G)\) parameter by the \(\ell_1\)-norm. They introduce the parameter \[\label{eq:b40G41} b(G) = \min_{\boldsymbol{x}\in\mathbf{R}^V} \left\{\sum_{uv\in E}|x_u-x_v|~:~\sum_{v\in V}x_v=0~\wedge~\sum_{v\in V}|x_v|=1\right\},\tag{1}\] which may be regarded as an \(\ell_1\) analog of the algebraic connectivity.⁶ The resulting problem preserves the flavor of classical theory, but shifts it from a primarily linear-algebraic setting to a discrete combinatorial one, closely related to sparsest cuts.

The main purpose of this paper is to extend this theory by studying its natural maximization counterpart. We introduce the parameter \[\label{eq:B40G41} B(G)=\max_{\boldsymbol{x}\in\mathbf{R}^V} \left\{\sum_{uv\in E}|x_u-x_v|~:~\sum_{v\in V}x_v=0~\wedge~\sum_{v\in V}|x_v|=1\right\}.\tag{2}\] Both parameters are defined as optimization problems over the same feasible region, with the same objective function. From the perspective of the classical \(\ell_2\)-theory, they may be regarded as the \(\ell_1\)-analogs of the two extremal Laplacian eigenvalues \(\lambda_2\) and \(\lambda_n\). While the minimization problem already admits a rich combinatorial interpretation [5], [6], the maximization problem appears not to have been systematically investigated before. One of our main results shows that \(B(G)\) has a simple exact form: if \(d_1\) and \(d_2\) are the two largest vertex degrees of \(G\), with possibly \(d_1=d_2\), then \(B(G)=\frac{1}{2}(d_1+d_2)\). Degree-sum expressions are familiar in the study of extremal Laplacian parameters, for instance in upper bounds for the largest Laplacian eigenvalue [7], [8]. Here, however, the degree average equals \(B(G)\).

As a first step, we extend some of the results of Andrade and Dahl so that they apply simultaneously to the minimization and maximization problems. In particular, both extrema admit solutions whose positive entries are all equal and whose negative entries are all equal. Thus, although the feasible region has infinite cardinality, both optimization problems can be reduced to a finite set \(\mathcal{G}\subset\mathbf{R}^V\) of structured vectors. This set has a natural combinatorial interpretation: its elements are in bijection with the ordered quasi-bipartitions \((P,N)\) of the vertex set, where \(P\) records the positive coordinates, \(N\) records the negative coordinates and the remaining vertices have coordinate zero. Under this correspondence, the objective function is expressed in terms of relative cut sizes, giving cut-based formulas for both \(b(G)\) and \(B(G)\). For the minimization problem, this recovers the characterization of Andrade and Dahl [5]; for the maximization problem, it leads to the degree formula stated above.

The second main contribution of our work is to reinterpret these optimization problems geometrically. The common feasible region can be viewed as the relative boundary of a hyperplane section of the \(\ell_1\) unit ball. This places the problem in a natural polyhedral setting related to the \(d\)-dimensional cuboctahedron [9] and to root polytopes [10].

Related \(\ell_1\)-spectral approaches to graph partitioning have also been studied in the context of Cheeger cuts [11]. In particular, Chang, Shao and Zhang use a cell decomposition of the feasible set for the graph \(1\)-Laplacian Cheeger problem, noting that the objective function is convex on each cell [12]. This is close in spirit to the approach taken here: we also decompose an \(\ell_1\)-type feasible region into cells adapted to the objective function; in our setting, this refinement makes the objective affine on each cell.

The paper is organized as follows. Section 2 develops the finite combinatorial formulation of the two optimization problems and proves the degree formula for \(B(G)\). Section 3 studies the geometry of the common feasible region, its cell decomposition, and the induced structure on \(\mathcal{G}\) to end with alternative geometric proofs of some of the main results. Section 4 applies the studied results to several graph families and counts the corresponding \(\ell_1\)-Fiedler vectors of \(\mathcal{G}\) in these examples. Section 5 proves the \(\#\mathrm{P}\)-completeness of counting the vectors in \(\mathcal{G}\) that attain \(B(G)\).

2 Preliminaries↩︎

Notice that both optimization problems, of Equation 1 and Equation 2 , are defined over the same feasible set \(\mathcal{F}\subset\mathbf{R}^V\) defined by \(\mathcal{F}=\{\boldsymbol{x}\in\mathbf{R}^V~:~\sum_{v\in V}x_v=0~\wedge~\sum_{v\in V}|x_v|=1\}\) and over the same objective function \(f:\mathbf{R}^V\rightarrow\mathbf{R}_{\geq0}\) given by \(f(\boldsymbol{x})=\sum_{uv\in E}|x_u-x_v|\), so we can rewrite Equations 1 and 2 as \[\label{eq:opt95problems95F} b(G)=\min_{\boldsymbol{x}\in\mathcal{F}}f(\boldsymbol{x}),~~B(G)=\max_{\boldsymbol{x}\in\mathcal{F}}f(\boldsymbol{x}).\tag{3}\]

The feasible set can be alternatively understood as the set of vectors whose positive components add to \(1/2\) and whose negative components add to \(-1/2\).

A vector that realizes one of the optimization problems of Equation 3 is called an \(\ell_1\)-Fiedler vector of that problem. That is, for example, that \(\boldsymbol{x}\in\mathcal{F}\) is an \(\ell_1\)-Fiedler vector for \(B(G)\) if and only if \(f(\boldsymbol{x})=B(G)\). A graph \(G\) might have many different \(\ell_1\)-Fiedler vectors; understanding how many there are is a natural question, analogous to the role played in the classical \(\ell_2\)-theory by the multiplicity of the Fiedler eigenvalue. We return to these counting questions later in the paper.

Among the \(\ell_1\)-Fiedler vectors of a graph \(G\), those of the form described in the next lemma yield the combinatorial characterization of \(b(G)\) and \(B(G)\). The following Lemma 2 corresponds to the first part of Theorem 3.2 in [5]. The proof given here follows the same general approach as the one in [5]. We nevertheless include it because it amends the final part of the argument and also extends it to the maximization case.

Consider the subset \(\mathcal{G}\subset\mathcal{F}\) consisting of the vectors for which all positive entries have the same value and all negative entries have the same value; that is, \(\mathcal{G}=\{\boldsymbol{x}\in\mathcal{F}\subset\mathbf{R}^V~:~x_u x_v>0 \Rightarrow x_u=x_v\}\). While \(\mathcal{F}\) has infinite cardinality, \(\mathcal{G}\) is finite, with \(|\mathcal{G}|=3^n-2^{n+1}+1\). Nevertheless, Lemma 2 shows that the optimization problems in Equation 3 can be restricted to this set. \[\label{eq:opt95problems95G} b(G)=\min_{\boldsymbol{x}\in\mathcal{G}}f(\boldsymbol{x}),~~B(G)=\max_{\boldsymbol{x}\in\mathcal{G}}f(\boldsymbol{x}).\tag{6}\]

The combinatorial description of the parameters \(b(G)\) and \(B(G)\) comes from the fact that, for vectors in \(\mathcal{G}\), the objective function \(f(\boldsymbol{x})=\sum_{uv\in E}|x_u-x_v|\) can be rewritten as the average of the relative cut sizes of a quasi-bipartition of \(V\). This relies on the natural bijection between \(\mathcal{G}\) and the set of ordered quasi-bipartitions of \(V\), which is established in the next proposition. We define the relevant concepts first.

For a subset \(S\subset V\) of the vertex set of any graph \(G=(V,E)\), the cut induced by \(S\) is the set of edges \(\delta(S) = \{uv\in E ~:~ u\in S \wedge v\in S^c\}\) that join a vertex of \(S\) with a vertex of its complement \(S^c=V\setminus S\). For a non-empty proper subset \(S\subset V\), the relative cut size of \(S\) is defined by the quotient \[\label{eq:xi40S41} \xi(S) = |\delta(S)|~/~|S|.\tag{7}\]

A quasi-bipartition of a set is simply a bipartition with the covering requirement relaxed. Thus, a pair \((S_1,S_2)\) of subsets of \(V\) is an ordered quasi-bipartition of \(V\) if \(S_1,S_2\neq\varnothing\) and \(S_1\cap S_2=\varnothing\). Let \(\Gamma\) be the set of all ordered quasi-bipartitions of \(V\), then we have the following result.

From the previous proposition, it follows that the optimization problems of \(f(\boldsymbol{x})=\sum_{uv\in E}|x_u-x_v|\) over vectors of \(\boldsymbol{x}\in\mathcal{G}\) can be reinterpreted as optimization problems of \(\frac{1}{2}\big(\xi(P)+\xi(N)\big)\) over ordered quasi-bipartitions \((P,N)\in\Gamma\). This is stated in the next result, of which the statement for \(b(G)\) is Theorem 3.2 of Andrade and Dahl [5].

Up to now, there has been a symmetry between the maximum and minimum optimization problems of \(f(\boldsymbol{x})\); this symmetry ends here. For a connected graph \(G\), no \(\ell_1\)-Fiedler vector of \(b(G)\) contains zero values [5]; however, for any graph with more than two vertices, there are always \(\ell_1\)-Fiedler vectors of \(B(G)\) that contain zero values. The following result fully characterizes the value of \(B(G)\) in terms of the two highest degrees among the vertices of \(G\).

Note that the \(\ell_1\)-Fiedler vector \(\boldsymbol{x}\in\mathcal{G}\) corresponding to the quasi-bipartition \((\{v_1\},\{v_2\})\) is given by \[x_v=\left\{\begin{matrix*}[r] 1/2, & \text{if } v=v_1,~\\ -1/2, & \text{if } v=v_2,~\\0, & \text{otherwise.}\end{matrix*}\right.\] Vectors of this form, with exactly one component equal to \(1/2\), exactly one equal to \(-1/2\), and all other components equal to zero, will play a key role in the geometric interpretation developed in the next section.

The combinatorial characterization obtained in this section admits a natural geometric reinterpretation. In the next section we study the feasible set as a polyhedral set embedded in the ambient space \(\mathbf{R}^V\), and place the finite set \(\mathcal{G}\) within that structure. This point of view provides a different perspective on the optimization problems defining \(b(G)\) and \(B(G)\), and also makes it possible to address structural questions about the corresponding \(\ell_1\)-Fiedler vectors, such as their location inside the feasible set and how many there are.

3 The geometry of combinatorial Fiedler theory↩︎

Let \(\mathcal{H}\) be the hyperplane containing the origin and normal to the all-ones vector \(\boldsymbol{1}\) in \(\mathbf{R}^V\), that is \[\mathcal{H}=\left\{\boldsymbol{x}\in\mathbf{R}^V~:~\boldsymbol{1}^\top\boldsymbol{x}=0\right\}=\left\{\boldsymbol{x}\in\mathbf{R}^V~:~\sum_{v\in V}x_v=0\right\}.\] Let \(\mathcal{B}\) be the \(\ell_1\) unit ball centered at the origin in \(\mathbf{R}^V\), that is \[\mathcal{B}=\left\{\boldsymbol{x}\in\mathbf{R}^V~:~\|\boldsymbol{x}\|_1\leq1\right\}=\left\{\boldsymbol{x}\in\mathbf{R}^V~:~\sum_{v\in V}|x_v|\leq1\right\}.\] The set \(\mathcal{B}\) is the convex hull of \(\{\pm\boldsymbol{e}_v\}_{v\in V}\) where \(\boldsymbol{e}_v\) are the standard basis vectors of \(\mathbf{R}^V\); it is called the cross polytope. Now, the set \(\bar{\mathcal{F}}=\mathcal{H}\cap\mathcal{B}=\{\boldsymbol{x}\in\mathbf{R}^V~:~{\sum_{v\in V}x_v=0} ~\wedge~ {\sum_{v\in V}|x_v|\leq1}\}\) is not quite our feasible set, but it can be cleanly characterized in terms of vectors \(\boldsymbol{e}_v\) in the following way, where we denote the convex hull of a set \(\mathcal{X}\subset\mathbf{R}^V\) by \(CH(\mathcal{X})\).

Our feasible set \(\mathcal{F}\) is the boundary relative to the hyperplane \(\mathcal{H}\) of the full polytope \(\bar{\mathcal{F}}\), we write \(\mathcal{F}=\partial_\mathcal{H}\bar{\mathcal{F}}\) to denote this. The following subsection gives visual depictions of the relevant sets for low-dimensional cases, along with some specific examples.

3.1 The geometry of \(\mathcal{F}\) in low dimensions↩︎

Consider the case of a vertex set of only three elements \(V=\{1,2,3\}\) so that \(\mathbf{R}^V\simeq\mathbf{R}^3\). There, the \(\ell_1\) unit ball \(\mathcal{B}\) is the octahedron represented in the leftmost panel of Figure 1 as an orthogonal projection on to the plane \(\mathcal{H}\). The intersection \(\bar{\mathcal{F}}=\mathcal{B}\cap\mathcal{H}\) is the hexagon that is shown in the center panel of the same Figure 1. The one-dimensional feasible set \(\mathcal{F}\) is the boundary of this hexagon. The \(\mathbf{R}^V\) coordinates of some of the twelve points of \(\mathcal{G}\subset\mathcal{F}\) are shown for reference in the rightmost panel of Figure 1.

As a first concrete example, Figure 2 shows, for the path on three vertices, how the points of \(\mathcal{G}\) can be interpreted as one-dimensional drawings of the graph and how the objective function corresponds to the sum of the lengths of all edges in this drawing.

The leftmost side of Figure 2 shows the actual drawings above the line in \(\mathbf{R}^1\) for all the points \(\boldsymbol{g}\in\mathcal{G}\). The coordinates of the \(\boldsymbol{g}\) vectors are listed in the table together with the corresponding objective function value. A notational convention is adopted for the points of \(\mathcal{G}\): the point corresponding to the quasi-bipartition \((P,N)=(\{1,2\},\{3\})\) is denoted by \(\boldsymbol{g}_{\scriptscriptstyle P,N}=\boldsymbol{g}_{\scriptscriptstyle 12,3}\). To the top-right of the figure all points of \(\mathcal{G}\) are placed above the hexagon \(\mathcal{F}\) in the same positions as in Figure 1. Below that, again in the same order, the value of \(f(\boldsymbol{x})=|x_1-x_2|+|x_2-x_3|\) is depicted schematically as the distance to the hexagon; each consecutive gray concentrical hexagon corresponds to an increase of \(1/4\) in the \(f\) value. This picture already illustrates, in the simplest non-trivial case, how the optimization problems are encoded by the geometry of the feasible set.

Consider now the case of a vertex set of four elements \(V=\{1,2,3,4\}\) such that \(\mathbf{R}^V\simeq\mathbf{R}^4\). In this case, the polytope \(\bar{\mathcal{F}}=\mathcal{H}\cap\mathcal{B}\) is a cuboctahedron, and the feasible set \(\mathcal{F}=\partial_\mathcal{H}\bar{\mathcal{F}}\) is its boundary relative to the three-dimensional hyperplane \(\mathcal{H}\). Figure 3 shows this configuration by means of an orthogonal projection of the ambient space \(\mathbf{R}^4\) onto \(\mathcal{H}\), so that the geometry of \(\mathcal{F}\) and the finite set \(\mathcal{G}\subset\mathcal{F}\) can be visualized in three dimensions. The visible vertices \(\boldsymbol{e}_{uv}=\frac{1}{2}(\boldsymbol{e}_u-\boldsymbol{e}_v)\) are labeled in the right panel in accordance with the axes shown in the left panel; they correspond to the points \(\boldsymbol{g}_{\scriptscriptstyle u,v}\) with \(u\neq v\) in \(\mathcal{G}\), those are the quasi-bipartitions \((\{u\},\{v\})\) for \(u\neq v\) under the bijection of Proposition 1. The other visible points of \(\mathcal{G}\) are also marked as black dots, they lie at the centers of edges and faces of \(\mathcal{F}\).

Figure 4 considers a particular graph as an example of this case of \(|V|=4\). A subset of connected points of \(\mathcal{G}\) are arbitrarily selected and highlighted over the cuboctahedron at the bottom-right of the figure. The corresponding \(\mathbf{R}^1\) drawing for those points are shown in the left side of the figure and to their side their corresponding objective value is given. Note that the configuration at the bottom of the pile of drawings \(\boldsymbol{g}_{\scriptscriptstyle 123,4}=(\frac{1}{6},\frac{1}{6},\frac{1}{6},-\frac{1}{2})\), corresponds to a minimizing solution for this particular graph, while the one at the top of the pile \(\boldsymbol{g}_{\scriptscriptstyle 3,2}=(0,-\frac{1}{2},\frac{1}{2},0)\) is a maximizing solution. The corresponding quasi-bipartitions for these two points are depicted over the graph at the top-right of the figure.

The placement of the points of \(\mathcal{G}\) inside the set \(\mathcal{F}\) in the general case, together with a formal description of the connection between points of \(\mathcal{G}\) and how the value of \(f\) changes when moving from point to point is discussed in the next subsection.

3.2 Geometric interpretation of the optimization problems↩︎

In the general case, for \(|V|=n>4\) the set \(\bar{\mathcal{F}}\) is an \((n-1)\)-dimensional polytope embedded in the ambient space \(\mathbf{R}^V\simeq\mathbf{R}^n\). The feasible set is its shell \(\mathcal{F}=\partial_\mathcal{H}\bar{\mathcal{F}}\) composed of \((n-2)\)-dimensional faces whose relative interior points have no coordinate equal to zero. Then come \((n-3)\)-dimensional faces in whose relative interiors points have exactly one coordinate equal to zero, \((n-4)\)-dimensional faces in whose relative interiors points have exactly two coordinates equal to zero, and so on. This ends at the vertices \(\boldsymbol{e}_{uv}=\boldsymbol{g}_{\scriptscriptstyle u,v}=\frac{1}{2}(\boldsymbol{e}_u-\boldsymbol{e}_v)\) for \(u\neq v\) in \(V\) (\(0\)-dimensional faces) for which exactly \(n-2\) coordinates are zero.

Alternative proofs of the results of Section 1 can be obtained from this geometric interpretation of the problem. It is convenient to introduce a decomposition of \(\mathcal{F}\) into \((n-2)\)-dimensional cells in whose relative interiors both the weak order between coordinates and the weak signs of each coordinate are preserved. Note that \(\mathcal{F}\) (also \(\mathcal{G}\)) depends only on the vertex set \(V\) and not on the edge set \(E\) that is considered. The key idea is that, with such a decomposition, the function \(f\) of any edge set \(E\) is linear in each cell.

For each bijection \(\pi:\{1,\ldots,n\}\rightarrow V\) assigning an order for the coordinates and each number \(k\) of non-negative coordinates \(k=1,\ldots,n-1\), we define a cell to be the following closed set: \[\label{eq:cell95def} \mathcal{C}(\pi,k)=\{\boldsymbol{x}\in\mathcal{F} ~:~ x_{\pi(1)} \geq\cdots\geq x_{\pi(k)}\geq0\geq x_{\pi(k+1)}\geq\cdots\geq x_{\pi(n)}\}.\tag{9}\] Note that in general \(\mathcal{F}\) is decomposed into \((n-1)\cdot n!\) cells; the \(12\) cells of the hexagon and some of the \(72\) cells of the cuboctahedron are shown in Figure 5.

The interiors (relative to \(\mathcal{F}\)) of the cells \(\mathcal{C}(\pi,k)\) are pairwise disjoint; the union of all the cells equals \(\mathcal{F}\). Two different cells might have common lower-dimensional faces. In particular, each cell \(\mathcal{C}(\pi,k)\) has \(k(n-k)\) vertices which are obtained precisely when all positive coordinates are equal, all negative coordinates are equal, and the remaining coordinates are zero. This fact follows from the simplex decomposition of the cells given later in Lemma 6, we state it here as a lemma for reference.

On each cell \(\mathcal{C}(\pi,k)\), the weak order of coordinates is fixed, so for each \(uv\in E\) the corresponding difference \(x_u-x_v\) is either always non-negative or always non-positive. Hence, the corresponding term \(|x_u-x_v|\) of \(f\) can be replaced either by \(x_u-x_v\) or by \(-(x_u-x_v)\), so we have the following result.

With these last results, we have the following alternative proofs for Lemma 2 and Theorem 2.

The discussion above places the optimization problems that define \(b(G)\) and \(B(G)\) in a polyhedral setting. The set \(\mathcal{G}\) consists of the vertices of the closed cells of \(\mathcal{F}\), and the function \(f\) is linear on each cell. In the next subsection we examine more closely how the finite set \(\mathcal{G}\) sits inside \(\mathcal{F}\), with particular attention to the way its points are connected through the surrounding cell structure.

3.3 The structure of \(\mathcal{G}\) inside \(\mathcal{F}\)↩︎

Recall the notation introduced in Proposition 1; for each ordered quasi-bipartition \((P,N)\in\Gamma\), we denote its corresponding point by \(\boldsymbol{g}_{\scriptscriptstyle P,N}\in\mathcal{G}\). As we saw in the last subsection, the set \(\mathcal{G}\) coincides with the set of vertices of the cells of \(\mathcal{F}\).

Among the points of \(\mathcal{G}\), there are two types that play a distinguished role. On the one hand, there are the points with only two non-zero coordinates, namely the points \(\boldsymbol{g}_{\scriptscriptstyle \{u\},\{v\}}\in\mathcal{G}\) for \(u\neq v\) in \(V\). These are the vertices of the polytope \(\bar{\mathcal{F}}\), and the maximum of \(f\) is attained at points of this form. We call these points the extremes of \(\mathcal{G}\). On the other hand, there are the points of \(\mathcal{G}\) with no zero coordinates, that is, the points \(\boldsymbol{g}_{\scriptscriptstyle P,N}\in\mathcal{G}\) such that \(P\cup N=V\), with \(P\cap N=\varnothing\). We call these points centers of \(\mathcal{G}\).

As an example consider the cell \(\mathcal{C}(1243,2)\) in Figure 5 above. It has four vertices, but among them just one center \(\boldsymbol{g}_{\scriptscriptstyle 12,34}=\left(\frac{1}{4},\frac{1}{4},-\frac{1}{4},-\frac{1}{4}\right)\) and one extreme \(\boldsymbol{g}_{\scriptscriptstyle 1,3}=\left(\frac{1}{2},0,-\frac{1}{2},0\right)\). In general, for each cell \(\mathcal{C}(\pi,k)\), there is exactly one center and one extreme among its vertices \(\boldsymbol{g}_{\scriptscriptstyle P,N}\in\mathcal{G}\cap\mathcal{C}(\pi,k)\). They are the points with \(P=\{\pi(1),\dots,\pi(k)\},~N=\{\pi(k+1),\dots,\pi(n)\}\) and \(P=\{\pi(1)\},~N=\{\pi(n)\}\), respectively.

This structure suggests considering not only the set \(\mathcal{G}\) itself, but also the neighboring relation induced on it by the cell decomposition of \(\mathcal{F}\). We define the quasi-bipartition graph as the graph whose vertex set is \(\mathcal{G}\), where two points of \(\mathcal{G}\) are adjacent whenever they are joined by an edge of some cell of \(\mathcal{F}\).

In order to understand which elements of \(\mathcal{G}\) are adjacent in the quasi-bipartition graph, we leverage the fact that each cell can be decomposed into a positive part and a negative part, similar to what was done in the proof of Lemma 3.

For a concrete example consider \(V=\{1,2,3,4,5\}\), and take the cell \(\mathcal{C}(13245,2)\) of the feasible set \(\mathcal{F}\). Then \[\mathcal{C}^+(13245,2)=\textstyle CH(\{(\frac{1}{2},0,0,0,0),~(\frac{1}{4},0,\frac{1}{4},0,0)\}),\] \[\mathcal{C}^-(13245,2)=\textstyle CH(\{(0,0,0,0,-\frac{1}{2}),~(0,0,0,-\frac{1}{4},-\frac{1}{4}),~(0,-\frac{1}{6},0,-\frac{1}{6},-\frac{1}{6})\}).\]

We refer to Fukuda [14] for a general treatment of polytopes constructed as Minkowski sums. In the present situation, however, the geometry is particularly simple: a coordinate that may be nonzero on \(\mathcal{C}^+(\pi,k)\) is identically zero on \(\mathcal{C}^-(\pi,k)\), and conversely. Hence every point of \(\mathcal{C}(\pi,k)\) has a unique representation as \(\boldsymbol{x}^++\boldsymbol{x}^-\) with \(\boldsymbol{x}^+\in\mathcal{C}^+(\pi,k)\) and \(\boldsymbol{x}^-\in\mathcal{C}^-(\pi,k)\). Equivalently, the addition map \((\boldsymbol{x}^+,\boldsymbol{x}^-)\mapsto \boldsymbol{x}^++\boldsymbol{x}^-\) is an affine isomorphism from \(\mathcal{C}^+(\pi,k)\times\mathcal{C}^-(\pi,k)\) to \(\mathcal{C}(\pi,k)\). Consequently, every edge of \(\mathcal{C}(\pi,k)\) is obtained by fixing one factor at a vertex and taking an edge of the other. Translating this description into the language of ordered quasi-bipartitions gives the desired characterization of adjacency in the quasi-bipartition graph.

In terms of ordered quasi-bipartitions, the vertices of \(\mathcal{C}^+(\pi,k)\) correspond to the nested positive sets \[\{\pi(1)\}\varsubsetneq \{\pi(1),\pi(2)\}\varsubsetneq\cdots\varsubsetneq\{\pi(1),\ldots,\pi(k)\},\] while the vertices of \(\mathcal{C}^-(\pi,k)\) correspond to the nested negative sets \[\{\pi(n)\}\varsubsetneq\{\pi(n-1),\pi(n)\}\varsubsetneq\cdots\varsubsetneq\{\pi(k+1),\ldots,\pi(n)\}.\] Therefore, moving along an edge of \(\mathcal{C}(\pi,k)\) means keeping one of the two sets fixed and replacing the other by another member of one of these nested chains.

The quasi-bipartition graph provides a convenient discrete model for the behavior of \(f\) on \(\mathcal{F}\). It is useful because it retains the adjacency structure of the cell decomposition on the finite set \(\mathcal{G}\). In this way, questions about the local behavior of \(f\) on \(\mathcal{F}\) can be reduced to questions about how \(f\) varies along the edges of this graph. Since \(f\) is affine on each cell, this leads naturally to studying its directional differences along those edges, which turn out to have a clean combinatorial characterization.

If \(\boldsymbol{g}\sim\boldsymbol{g}'\), we denote by \(\Delta(\boldsymbol{g}\to\boldsymbol{g}')f\) the directional difference of \(f\) along the oriented edge from \(\boldsymbol{g}\) to \(\boldsymbol{g}'\). Then, depending on which of the two parts changes, we have: \[\label{eq:Delta40gg41f}\begin{align} \Delta(\boldsymbol{g}_{\scriptscriptstyle P,N}\to\boldsymbol{g}_{\scriptscriptstyle P',N})f &= \frac{1}{2}\big(\xi(P')-\xi(P)\big), \\ \Delta(\boldsymbol{g}_{\scriptscriptstyle P,N}\to\boldsymbol{g}_{\scriptscriptstyle P,N'})f &= \frac{1}{2}\big(\xi(N')-\xi(N)\big). \end{align}\tag{12}\]

Now, in particular, let \(\boldsymbol{g}_{\scriptscriptstyle P,N}\in\mathcal{G}\) be a non-center, and write \(Z=V\setminus(P\cup N)\). Its two centralizing directions are the oriented edges \(\boldsymbol{g}_{\scriptscriptstyle P,N}\to \boldsymbol{g}_{\scriptscriptstyle P\cup Z,N}\) and \(\boldsymbol{g}_{\scriptscriptstyle P,N}\to \boldsymbol{g}_{\scriptscriptstyle P,N\cup Z}\).

This last result restates, in the present geometric setting, Corollary 3.3 of Andrade and Dahl [5], which states that, in the context of connected simple graphs \(G\), the \(\ell_1\)-Fiedler vectors of \(b(G)\) contain no zero coordinates.

A direct consequence of this fact, which will be used in the next section to count the number of \(\ell_1\)-Fiedler vectors for \(b(G)\), is the following:

That is, \(b(G)\) corresponds to a sparsest cut in \(G\); we want to partition \(V\) into \(S\) and its complement in \(V\), so that both of \(S\) and \(V\backslash S\) are large sets, but with only few edges between \(S\) and \(V\backslash S.\) The \(\ell_1\)-Fiedler vector \(\boldsymbol{x}^S\in\mathcal{G}\) for \(b(G)\) corresponding to a sparsest cut \(\delta(S)\) is \(\boldsymbol{x}^S=(x_v)_{v\in V}\) given by \[x_v=\left\{\begin{array}{rl} \frac{1}{2|S|}, & \text{ if } v \in S,~\\ -\frac{1}{2|V\backslash S|}, & \text{ if } v \in V\backslash S.\end{array}\right.\]

4 Examples↩︎

In this section, we illustrate the results of the previous sections on several graph families. For each example, the goal is to describe the points of \(\mathcal{G}\) that realize the optimization problems defining \(b(G)\) and \(B(G)\) and to explicitly count the corresponding \(\ell_1\)-Fiedler vectors. This also provides concrete examples for the counting problem studied in the next section. Only \(\ell_1\)-Fiedler vectors in \(\mathcal{G}\) are considered here, as otherwise there would be an infinite number of \(\ell_1\)-Fiedler vectors in many cases. We omit stating this restriction for each example throughout this section.

Each \(\ell_1\)-Fiedler vector for \(B(G)\) corresponds to an ordered quasi-bipartition \((P,N)\) of \(V\), see Proposition 1. If \(G\) has at least two vertices of same highest degree, then each of \(P\) and \(N\) is a subset of non-adjacent vertices of highest degree of \(G\). If \(G\) has only one vertex of highest degree, then one of \(P,N\) consists of only this vertex, and the other one is a subset of non-adjacent vertices among the vertices of second-highest degree. This observation allows counting the number of \(\ell_1\)-Fiedler vectors for \(B(G).\)

4.1 The complete graph \(K_n\)↩︎

The complete graph on \(n\) vertices \(K_n\) has \(B(K_n)= n-1.\) The quasi-bipartition \((P,N)\) corresponding to an \(\ell_1\)-Fiedler vector for \(B(K_n)\) has exactly one vertex from \(K_n\) in \(P\) and another one in \(N\). Then, the number of \(\ell_1\)-Fiedler vectors for \(B(K_n)\) is \(n^2-n.\)

On the other hand, \(K_n\) has \(b(K_n)=\frac{n}{2}\), also see [5]. Any partition of \(V\) into two non-empty subsets of vertices gives an \(\ell_1\)-Fiedler vector for \(b(K_n)\). Then, the number of \(\ell_1\)-Fiedler vectors for \(b(K_n)\) is \(2^n-2.\)

Note that the number of vertices and facets of the polytope \(\bar{\mathcal{F}}\), the \((n-1)\)-dimensional cuboctahedron [9], is precisely \(n^2-n\) and \(2^n-2\), respectively. Each vertex of \(\bar{\mathcal{F}}\) gives a solution for the minimization problem in Equation (2 ). Each center gives a solution to the optimization problem in Equation (1 ); each facet of \(\bar{\mathcal{F}}\) contains one center.

4.2 The wheel graph \(W_n\)↩︎

Let \(n\geq 4.\) The wheel graph on \(n\) vertices consists of a cycle on \(n-1\) vertices and one additional vertex that is adjacent to each vertex of the cycle. \(W_n\) has \(B(W_n)=\frac{n+2}{2}.\) In the ordered quasi-bipartition \((P,N)\) corresponding to an \(\ell_1\)-Fiedler vector for \(B(W_n)\), one of \(P\) and \(N\) consists of the high-degree vertex, and the other one consists of a non-empty subset of pairwise non-adjacent vertices from the cycle on \(n-1\) vertices. The number of ways to choose such a subset is given by the Lucas number \(L(n-1)\) minus \(1\), see [15]. The Lucas numbers \(L(n)\) satisfy \(L(n)=L(n-1)+L(n-2)\) for \(n \geq 2\), and \(L(0)=2\), and \(L(1)=1.\) Then, the number of \(\ell_1\)-Fiedler vectors for \(B(W_n)\) is \[2\left( \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}+\left(\frac{1-\sqrt{5}}{2}\right)^{n-1} \right)-2 .\] This is twice the Lucas number \(L(n-1)\) minus \(2\).

In order to determine \(b(W_n)\), we observe that each \(\ell_1\)-Fiedler vector for \(b(W_n)\) corresponds to a partition of \(V\) into two subsets, where one subset consists of a set of \(x\) consecutive vertices on the cycle, for some integer \(x.\) Then \(b(W_n) \leq \frac{n}{2}\frac{x+2}{x(n-x))}\). We verify that this function is minimized if we take \(x=\left\lfloor\sqrt{2n+4}-2\right\rfloor\) or \(x=\left\lceil\sqrt{2n+4}-2\right\rceil\). It follows that \[b(W_n)=\min\left\{\frac{n}{2}\frac{\left\lfloor\sqrt{2n+4}-2\right\rfloor+2}{\left\lfloor\sqrt{2n+4}-2\right\rfloor(n-\left\lfloor\sqrt{2n+4}-2\right\rfloor)}\;\;,\; \frac{n}{2}\frac{\left\lceil\sqrt{2n+4}-2\right\rceil+2}{\left\lceil\sqrt{2n+4}-2\right\rceil(n-\left\lceil\sqrt{2n+4}-2\right\rceil)} \right\}.\]

There are \((2n-2)\) \(\ell_1\)-Fiedler vectors for \(b(W_n)\).

We remark that in [5] the formula \(b(W_n)=\frac{n}{n-2}\) is given, which coincides with the formula for \(b(W_n)\) given here for \(n=4,5,6,7,8\) but gives an incorrect value for \(n=9.\) We have \(b(W_9)=\frac{5}{4}.\)

4.3 The cycle graph \(C_n\)↩︎

Let \(n \geq 3.\) The cycle graph on \(n\) vertices \(C_n\) has \(B(C_n)=2.\) Each \(\ell_1\)-Fiedler vector for \(B(C_n)\) corresponds to an ordered quasi-bipartition \((P,N)\) of the vertex set of \(C_n\), where both of \(P\) and \(N\) are non-empty subsets of pairwise non-adjacent vertices. Counting the number of \(\ell_1\)-Fiedler vectors for \(B(C_n)\) then generalizes the problem of counting the number of subsets of pairwise non-adjacent vertices from a cycle from [15]. Here we count the number of two disjoint subsets of pairwise non-adjacent vertices, instead of just one subset. Each such ordered quasi-bipartition \((P,N)\) can be encoded by a word \(w\) of length \(n\) from the alphabet \(\{r,b,0\}\), where no two consecutive \(r\) and no two consecutive \(b\) appear, and also the first and the last entry are not both \(b\) and not both \(r\). Also, at least one entry \(r\) and one entry \(b\) is needed in \(w\). The entries in the word with letter \(r\) are elements from \(P\), entries with letter \(b\) are elements from \(N\), and elements with letter \(0\) get coordinate \(0.\) We can model this with a directed graph, whose adjacency matrix \(A\) is \[A=\begin{blockarray}{cccc} r & b & 0 \\ \begin{block}{(ccc)c} 0 & 1 & 1 & r \\ 1 & 0 & 1 & b \\ 1 & 1 & 1 & 0 \\ \end{block} \end{blockarray}\] The number of words \(w\), but maybe only using at most two instead of all three letters, is the number of closed walks of length \(n\) in this graph. This number of words is equal to the trace of \(A^n.\) The eigenvalues of \(A\) are \(1-\sqrt{2}\), \(1+\sqrt{2}\), and \(-1\). Then, there are \((1-\sqrt{2})^n+(1+\sqrt{2})^n+(-1)^n\) such words \(w.\) Note that we also counted words that do not use both letters \(b\) and \(r\). Therefore, we need to subtract the number of words that only use at most one of letters \(r\) and \(b\). By [15], we subtract twice the Lucas number \(L(n)\). Since also the empty subset is counted in \(L(n)\), we add \(1.\) The number of \(\ell_1\)-Fiedler vectors for \(B(C_n)\) is \[(1+\sqrt{2})^n +(1-\sqrt{2})^n - 2\left( \left( \frac{1+\sqrt{5}}{2}\right)^{n}+\left(\frac{1-\sqrt{5}}{2}\right)^{n} \right) +(-1)^n +1.\] This is the difference between the Pell-Lucas number \(P\ell(n)\) and twice the Lucas number \(L(n)\), plus \((-1)^n\) plus \(1\). The Pell-Lucas numbers \(P\ell(n)\) satisfy \(P\ell(n)=2P\ell(n-1)+P\ell(n-2)\) for \(n\geq 2\), and \(P\ell(0)=P\ell(1)=2.\)

The cycle graph \(C(n)\) has \(b(C_n)= \frac{n}{ \lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor }\), see also [5]. For \(n\) even, there are \(n\) \(\ell_1\)-Fiedler vectors for \(b(C_n)\), and for \(n\) odd there are \(2n\) \(\ell_1\)-Fiedler vectors for \(b(C_n)\). These correspond to the partition of \(V\) into two subsets of \(\lceil \frac{n}{2} \rceil\) and \(\lfloor \frac{n}{2} \rfloor\) consecutive vertices of \(C_n\).

4.4 The path graph \(P_n\)↩︎

Let \(n \geq 4.\) The path graph on \(n\) vertices \(P_n\) has \(B(P_n)= 2\). Each \(\ell_1\)-Fiedler vector for \(B(P_n)\) corresponds to an ordered quasi-bipartition \((P,N)\) of the vertex set of \(P_n\), where both of \(P\) and \(N\) are non-empty subsets of pairwise non-adjacent vertices. As in Section 4.3, each such ordered quasi-bipartition \((P,N)\) can be encoded by a word \(w\) of length \(n\) from the alphabet \(\{r,b,0\}\), where no two consecutive \(r\) and no two consecutive \(b\) appear. In addition, at least one entry \(r\) and one entry \(b\) are needed in \(w\). But now, the first and last entry of \(w\) can be any letter. The number of such words \(w\), but maybe only using at most two instead of all three letters, is the number of length walks \(n-1\) in the graph with adjacency matrix \(A\) from Section 4.3. This number of words is equal to the sum of the elements of \(A^{n-1}\).
We define \(a(n)=\frac{ (1+\sqrt{2})^n + (1-\sqrt{2})^n +2(-1)^n}{4}\), \(b(n)=\frac{ (1+\sqrt{2})^n + (1-\sqrt{2})^n -2(-1)^n}{4}\), \(c(n) = \frac{ (1+\sqrt{2})^n - (1-\sqrt{2})^n}{2\sqrt{2}}\), and \(d(n)=\frac{ (1+\sqrt{2})^n + (1-\sqrt{2})^n }{2}.\) It follows by induction on \(n\), that for \(n\geq 1\), the matrix \(A^n\) has the form \[A^n=\begin{blockarray}{cccc} r & b & 0 \\ \begin{block}{(ccc)c} a(n) & b(n) & c(n) & r \\ b(n) & a(n) & c(n) & b \\ c(n) & c(n) & d(n) & 0 \\ \end{block} \end{blockarray}\] The sum of the number of elements in \(A^n\) is then \[2a(n)+2b(n)+4c(n)+d(n) = \frac{(1+\sqrt{2})^{n+2}+(1-\sqrt{2})^{n+2}}{2}.\] The number of words \(w\), but maybe only using at most two instead of all three letters, then is \[\frac{(1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1}}{2}.\] We need to subtract the number of words that use at most one of the letters \(r\) and \(b\). By [15], we subtract twice the Fibonacci number \[Fib(n+2)=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2}\right)^{n+2}-\left( \frac{1-\sqrt{5}}{2}\right)^{n+2}\right),\] and add \(1\) because the word consisting of only zeros is also counted with the Fibonacci number in [15].

We find that the number of \(\ell_1\)-Fiedler vectors for \(B(P_n)\) is \[\frac{(1+\sqrt{2})^{n+1}+(1-\sqrt{2})^{n+1}}{2}-\frac{2}{\sqrt{5}} \left(\left( \frac{1+\sqrt{5}}{2}\right)^{n+2}-\left( \frac{1-\sqrt{5}}{2}\right)^{n+2}\right)+1.\] This is exactly the difference between the modified Pell number \(Pe(n+1)\) and twice the Fibonacci number \(Fib(n+2)\) plus 1. The modified Pell numbers \(Pe(n)\) satisfy \(Pe(n)=2Pe(n-1)+Pe(n-2)\), for \(n\geq 2\), and \(Pe(1)=Pe(0)=1.\) The Fibonacci numbers \(Fib(n)\) satisfy \(Fib(n)=Fib(n-1)+Fib(n-2)\) for \(n\geq 3\), and \(Fib(1)=Fib(2)=1.\)

The path graph \(P(n)\) has \[b(P_n)=\frac{n}{2} \frac{1}{ \lceil \frac{n}{2} \rceil \lfloor \frac{n}{2} \rfloor},\] also see [5]. For \(n\) even, there are two \(\ell_1\)-Fiedler vectors for \(b(P_n)\), and for \(n\) odd there are four \(\ell_1\)-Fiedler vectors for \(b(P_n)\). These correspond to the partition of \(V\) into two subsets of \(\lceil \frac{n}{2} \rceil\) and \(\lfloor \frac{n}{2} \rfloor\) consecutive vertices of \(P_n\).

4.5 The complete bipartite graph \(K_{n,m}\)↩︎

For \(n=1\), the complete bipartite graph \(K_{1,m}\) has \(B(K_{1,m})=\frac{m+1}{2}\). Each \(\ell_1\)-Fiedler vector for \(K_{1,m}\) corresponds to an ordered quasi-bipartition \((P,N)\), where one of \(P\) and \(N\) is the vertex of high degree, and the other one is a non-empty subset of vertices from the \(m\) vertices of the other bipartition class. The number of \(\ell_1\)-Fiedler vectors for \(B(K_{1,m})\) is then \[2^{m+1}-2.\] For \(\min\{n,m\}\geq 2\), \(K_{n,m}\) has \(B(K_{n,m})=\max\{n,m\}\). Assume \(n>m>1\). Each \(\ell_1\)-Fiedler vector for \(K_{n,m}\) corresponds to an ordered quasi-bipartition \((P,N)\), where each of \(P\) and \(N\) is a non-empty subset of vertices from the bipartition class of \(m\) vertices. For each of these \(m\) vertices, there are three options, whether to assign it to \(P\), \(N\) or \(0\). We then subtract the number of options where only \(P\) and \(0\) are used, or only \(N\) and \(0\) are used. We find that the number of \(\ell_1\)-Fiedler vectors for \(B(K_{n,m})\) is \[3^{m}-2^{m+1}+1.\] Assume then that \(n=m>1\). \(K_{n,n}\) has \(B(K_{n,n})=n\). Each \(\ell_1\)-Fiedler vector for \(K_{n,n}\) corresponds to an ordered quasi-bipartition \((P,N)\), where each of \(P\) and \(N\) is a non-empty subset of vertices from the same bipartition class.

If \(P\) and \(N\) belong to the same bipartiton class, then we have \(2(3^n-2^{n+1}+1)\) \(\ell_1\)-Fiedler vectors, similar to the previous case.

If \(P\) and \(N\) belong to different bipartition classes, we have \(2(2^n-1)^2\) \(\ell_1\)-Fiedler vectors.

The number of \(\ell_1\)-Fiedler vectors for \(B(K_{n,n})\) is then \[2(3^n-2^{n+1}+1) + 2(2^n-1)^2 = 2\left(4^n + 3^n -2^{n+2}+2 \right).\]

5 A hardness result↩︎

The results of the previous section show that, for several natural graph families, the set of \(\ell_1\)-Fiedler vectors in \(\mathcal{G}\) can be explicitly described and counted in closed form. This naturally leads to the following general question: given a graph, how difficult is it to determine the number of \(\ell_1\)-Fiedler vectors?

It is worth highlighting that, on the minimization side, Andrade and Dahl [5] already showed that the computation of \(b(G)\) and a corresponding \(\ell_1\)-Fiedler vector is NP-hard, via the connection between \(b(G)\) and the sparsest cuts.

In this section, we focus on the maximization side. Although Theorem 2 shows that the value of \(B(G)\) admits a very simple expression, the structure of the subset of vectors of \(\mathcal{G}\) that attain that value is not trivial in general; the associated counting problem is computationally intractable.

References↩︎

---

1. Corresponding author. Departamento de Matemática y Física, Universidad de Magallanes, Avenida Bulnes 01855, Punta Arenas, Chile, jose.fernandezg@umag.cl, https://orcid.org/0000-0001-5349-4348.↩︎

2. Universidad Francisco de Vitoria, Spain, and Departament de Matemàtiques, Universitat Politècnica de Catalunya, Spain. Supported by project PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. andrea.delasheras@ufv.es https://orcid.org/0000-0002-7219-9771.↩︎

3. Departamento de Informática y Computación, Universidad Tecnológica Metropolitana, José Pedro Alessandri 1242, Ñuñoa, Santiago de Chile 7800002, Región Metropolitana, Chile, luis.herrerab@utem.cl, https://orcid.org/0000-0001-7338-7611.↩︎

4. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Spain. Supported by project PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. clemens.huemer@upc.edu, https://orcid.org/0000-0001-7557-0823.↩︎

5. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Spain. Supported by project PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. carlos.seara@upc.edu, https://orcid.org/0000-0002-0095-1725.↩︎

6. Note that throughout this work the indexation of the vectors \(\boldsymbol{x}\in\mathbf{R}^V\) is done directly over the elements of \(V\) to unclutter the notation as in the presentation by Brouwer and Haemers [2].↩︎

7. The algebraic trick, used again latter, is \(\displaystyle\sum_{j=1}^{k}\sum_{i=j}^{k}a_{i,j}=\sum_{1\leq j\leq i\leq k}a_{i,j}=\sum_{i=1}^{k}\sum_{j=1}^{i}a_{i,j}\), see Equation (2.32) in [13].↩︎