Selected Open Problems in Discrete Geometry and Optimization

Abstract

A list of questions and problems posed and discussed in September 2011 at the following consecutive events held at the Fields Institute, Toronto: Workshop on Discrete Geometry, Conference on Discrete Geometry and Optimization, and Workshop on Optimization. We hope these questions and problems will contribute to further stimulate the interaction between geometers and optimizers.

1 Short Questions

1.1 Question by Imre Bárány, Endre Makai, Jr., Horst Martini, and Valeriu Soltan

The problem posed below can also be found in the article [27] (p. 469) written by the second and third of its posers.

Let $X \subset {\mathbb{R}}^{d}$. Following Klee, one calls x′, x′ ∈ X (where x′≠x′) antipodal if there are different parallel supporting hyperplanes H′, H′ of convX such that x′ ∈ H′ and x′ ∈ H′ (cf. [26], p. 420). Moreover, $X \subset {\mathbb{R}}^{d}$ is antipodal if for all x′, x′ ∈ X with x′≠x′ we have that x′ and x′ are antipodal. Answering a problem of Erdős and Klee, Danzer and Grünbaum [25] proved that for $X \subset {\mathbb{R}}^{d}$, if X is antipodal, then | X | ≤ 2^d. This is sharp for the vertices of a parallelotope.

We pose a generalization of this theorem:

Question 1.

Suppose S is a set of segments in ${\mathbb{R}}^{d}$ such that for every s′,s′∈ S with s′≠s′ there are different parallel supporting hyperplanes H′, H′ of the convex hull $\text{conv}(\bigcup \{s: s \in S\})$ , such that s′⊂ H′ and s′⊂ H′. Then is it true that |S|≤ 2 ^d−1 ?

Comments. If true, this would be sharp: an example would be the set of all edges of a parallelotope, parallel to a given edge.

Of course, more generally, we may consider a set S _k of k-simplices in ${\mathbb{R}}^{d}$, which satisfy the word-for-word analogue of the above property. Is it true, that then | S _k  | ≤ 2^d − k? If true, this would be sharp: an example would be simplices on all k-faces of a parallelotope, parallel to a given k-face. Here 1 ≤ k ≤ d − 2. (Observe that for $k = d - 1$ the statement is evidently true.)

I. Talata, (Oral Communication, unpublished), proved the case d = 3 and k = 1.

1.2 Question by Károly Bezdek

A plank is a closed region of the d-dimensional Euclidean space ${\mathbb{E}}^{d}$ bounded by a pair of parallel hyperplanes. The width of a plank is the distance between its boundary hyperplanes.

Question 2.

Given a family of planks whose sum of widths is smaller than 2, what is the maximum volume of the part of the unit ball in ${\mathbb{E}}^{d}$ that can be covered by the planks?

Comments. One might expect that the maximum volume in question is reached when the planks do not overlap and their union forms one plank concentric with the unit ball. Indeed, this is so in ${\mathbb{E}}^{3}$. For a somewhat stronger statement in ${\mathbb{E}}^{3}$ and its proof see Theorem 4.5.2 in [28]. The above question and the expected answer in two dimensions are motivated by the well-known solution (attributed to A. Tarski, 1932) of a problem on covering the unit circle by a family of planks. (For more details we refer the interested reader to Chap. 4 of [28].)

Recall that ${\mathbb{S}}^{d}$ stands for the d-dimensional unit sphere in (d + 1)-dimensional Euclidean space ${\mathbb{E}}^{d+1},d \geq 2$. A spherically convex body is a closed, spherically convex subset K of ${\mathbb{S}}^{d}$ with interior points and lying in some closed hemisphere, thus, the intersection of ${\mathbb{S}}^{d}$ with a (d + 1)-dimensional closed convex cone of ${\mathbb{E}}^{d+1}$ different from ${\mathbb{E}}^{d+1}$. The inradius r(K) of K is the spherical radius of the largest spherical ball contained in K.

Question 3.

Let the spherically convex bodies $\mathbf{K}_{1},\ldots,\mathbf{K}_{n}$ cover the spherical ball B of radius $r(\mathbf{B}) < \frac{\pi } {2}$ in ${\mathbb{S}}^{d},d \geq 2$ . Then prove or disprove that $\sum _{i=1}^{n}r(\mathbf{K}_{i})\geq r(\mathbf{B})$ .

Comments. R. Schneider and the author [29] have proved the following related result: If the spherically convex bodies $\mathbf{K}_{1},\ldots,\mathbf{K}_{n}$ cover the spherical ball B of radius $r(\mathbf{B}) \geq \frac{\pi } {2}$ in ${\mathbb{S}}^{d},d \geq 2$, then $\sum _{i=1}^{n}r(\mathbf{K}_{i}) \geq r(\mathbf{B})$. Furthermore, we note that the Euclidean analogue of the latter result has been proved by V. Kadets in [30] using an approach completely different from the one of [29].

1.3 Question by Peter Brass

Question 4.

Is it true that for each set of points in general position that results from an $\sqrt{n} \times \sqrt{n}$ grid in three-dimensional space by a small perturbation, every triangulation of the set consists of at most $O\left ({n}^{3/2}\right )$ simplices?

Comments. Any set of n points in three-dimensional space that is in general position allows many different triangulations, and unlike in the two-dimensional situation, different numbers of simplices are possible. Any set of n points has a triangulation with O(n) simplices, but it can have much larger triangulations, up to $O\left ({n}^{2}\right )$. But some point sets do not allow that large triangulations. I believe that for the perturbed-grid-square $O\left ({n}^{3/2}\right )$ is the maximum. For the perturbed-grid-cube I have a bound of $O\left ({n}^{5/3}\right )$, which is not sharp; the bound of $O\left ({n}^{3/2}\right )$ would be sharp for the perturbed-grid-squares.

1.4 Question by Antoine Deza

An arrangement $\mathcal{A}_{\:d,n}$ of n hyperplanes in dimension d is simple if any d hyperplanes intersect at a distinct point. The d-dimensional polyhedra defined by the hyperplanes of an arrangement $\mathcal{A}_{\:d,n}$ are called the cells of $\mathcal{A}_{\:d,n}$. The bounded facets of an unbounded cell are called external. Let $\Phi _{\mathcal{A}}(d,n)$ be the minimum number of external facets for any simple arrangement defined by n hyperplanes in dimension d.

Question 5.

We hypothesize that $\Phi _{\mathcal{A}}(d,n + 1) \geq \Phi _{\mathcal{A}}(d,n) + \Phi _{\mathcal{A}}(d - 1,n)$ for n > d ≥ 3, and that the inequality is satisfied with equality for d = 3 and n ≥ 6, i.e., $\Phi _{\mathcal{A}}(3,n) = {n}^{2} - 3n + 4$ for n ≥ 6.

Comments. The hypothesized inequality holds for $n=d+1$ since $\Phi _{\mathcal{A}}(d,d+1) = d+1$ and $\Phi _{\mathcal{A}}(d,d + 2) = d(d + 1)$. For d = 2, we have $\Phi _{\mathcal{A}}(2,n) = 2(n - 1)$ for n ≥ 4 and, thus, $\Phi _{\mathcal{A}}(2,n + 1) = \Phi _{\mathcal{A}}(2,n) + \Phi _{\mathcal{A}}(1,n)$ for n ≥ 4 since $\Phi _{\mathcal{A}}(1,n) = 2$. The hypothesized inequality holds for all know values of $\Phi _{\mathcal{A}}(d,n)$ and is satisfied with equality for (d, n) = (3, 6) and (3, 7), see [31]. A strengthening of the lower bound of $\Phi _{\mathcal{A}}(3,n) \geq n(n - 2)/3 + 2$ would improve the upper bound for the average diameter of a bounded cell of a simple arrangement of n hyperplanes in dimension 3. We refer to [32] for more details about the relation of the average diameter of a bounded cell of a simple arrangement of n hyperplanes in dimension d to $\Phi _{\mathcal{A}}(d,n)$, and to the Hirsch conjecture recently disproved by Santos [33].

1.5 Question by Gábor Fejes Tóth

The maximum volume of the intersection of a fixed ball in ${\mathbb{E}}^{d}$ and a variable simplex of given volume V is attained when the simplex is regular and concentric with the ball. This statement easily follows by Steiner symmetrization.

Question 6.

Show that the above statement holds true in spherical and hyperbolic space as well.

Comments. Apart of the two-dimensional case the problem is open. If true, the statement has some important consequences. It implies that the simplex of maximum volume inscribed in a ball in S ^d or H ^d is regular, results proved by Böröczky [34] and Peyerimhoff [35], respectively. It also implies the conjecture that the simplex of minimum volume circumscribed a ball in S ^d or H ^d is regular. For the spherical case the statement implies the following: The volume of the part of S ^d covered by d + 2 congruent balls attains its maximum if the centers of the balls lie in the vertices of a regular simplex.

1.6 Question by Włodzimierz Kuperberg

Question 7.

What is the minimum number q(n) of cubes in ${\mathbb{R}}^{n}$ of edge length smaller than 1 whose union contains a unit cube?

Comments. The smaller cubes in question are not assumed to be parallel (homothetic) to the covered unit cube, for in that case the corresponding minimum number would be exactly 2ⁿ, since on one hand, a smaller homothetic cube contains at most one vertex of the unit cube, and on the other hand, 2ⁿ smaller homothetic cubes suffice to cover the unit cube.

It is not difficult to prove that q(2) = 3 and that q(n) ≤ n + 1 for every n, but the exact value of q(n) has not yet been established for any n ≥ 3.

1.7 Question by Jon Lee

Question 8.

For n ≥ 2, the Boolean Quadric Polytope $\mathcal{P}_{n}$ is the convex hull in dimension $d = n(n + 1)/2$ of the 0∕1 solutions to $x_{i}x_{j} = y_{ij}$ for all i < j in N:={ 1,2,…,n}. Give a formula or good bounds for the d-dimensional volume of $\mathcal{P}_{n}$ .

Comments. The polytope $\mathcal{P}_{n}$ is contained in $\mathcal{Q}_{n}$, the solution set of the linear inequalities: y _ij  ≤ x _i , y _ij  ≤ x _j , $x_{i} + x_{j} \leq 1 + y_{ij}$, for all i < j in N. In [36], we demonstrated that the d-dimensional volume of $\mathcal{Q}_{n}$ is ${2}^{2n-d}n!/(2n)!$. So this is an upper bound on the d-dimensional volume of $\mathcal{P}_{n}$. We would like to see a significant improvement in this upper bound and/or a non-trivial lower bound. There is quite a lot known about further linear inequalities satisfied by $\mathcal{P}_{n}$, so there are avenues to explore for trying to get a significant improvement in the upper bound.

1.8 Question by Horst Martini

Question 9.

Characterize geometrically those n-simplices in ${\mathbb{E}}^{n}$ , n ≥ 3, for which the incenter lies on the Euler line.

Comments. It is well known that for any triangle T in ${\mathbb{E}}^{2}$ the circumcenter C, the centroid S, the orthocenter O, and the center Fof the nine-point circle lie on one line—the Euler line e of T. It is also known that the incenter I of T lies on e if and only if T is isosceles, with e as axis of symmetry. No analogous characterization is known for n-simplices in ${\mathbb{E}}^{n}\ (n \geq 3)$ whose incenter I lies on their Euler line, which still is the affine hull of C and S; see the problem posed above. Only the following is known (see [37]): Let T be an n-dimensional orthocentric simplex (n ≥ 3), i.e., the n + 1 altitudes of T still have a common point. Then C, S, and I of T are collinear if and only if T is biregular, which means: The vertex set of T can be partitioned into two disjoint subsets V ₁, V ₂ such that convV ₁, convV ₂ form regular simplices and all segments [x, y], x ∈ V ₁, y ∈ V ₂, are of equal length. This directly generalizes the planar result and supports somewhat the “philosophy” that orthocentric n-simplices (n ≥ 3) are the “true” higher dimensional analogues of triangles.

1.9 Question by Benjamin Matschke

Conjecture 1.

(A Multicolored Carathéodory Conjecture). Let r ≥ 2 and N ≥ 1 be integers. N can be assumed to be very large, that is, N ≥ N ₀(r) for some N ₀(r). Suppose we are given r(N + 1) points P _ij in ${\mathbb{R}}^{N}$ that are indexed by 1 ≤ i ≤ r and 1 ≤ j ≤ N + 1. Assume that 0 ∈ conv{P _1j , …, P _rj } for all 1 ≤ j ≤ N + 1. Assume further that the index set {1, 2, …, N + 1} is partitioned as $C_{1} \uplus \ldots \uplus C_{m}$ such that all color classes are small: | C _k  | ≤ r − 1 for all 1 ≤ k ≤ m. Then there exist k ₁, …, k _N + 1 ∈ { 1, …, r} such that $0 \in \text{conv}\{P_{k_{1},1},\ldots,P_{k_{N+1},N+1}\}$ and for any two distinct a, b in the same color class C _k we have k _a ≠k _b .

Comments. This is an—admittedly technical—multicolored version of Bárány’s colored Carathéodory theorem (1982). If true this conjecture implies the new colored Tverberg theorem by Blagojević, Ziegler and me (2009), also for non-primes r. Hence, the conjecture is particularly interesting when r is not a prime and r − 1 divides N. The first interesting case is r = 4 and N = 9, which, if true, would imply the new colored Tverberg theorem in the smallest open non-prime case r = 4 and d = 2.

1.10 Question by Valeriu Soltan

Conjecture 2.

If $K \subset {\mathbb{R}}^{n}$ is a compact convex set and n ₁, …, n _s are positive integers with $n_{1} + \cdots + n_{s} = n + 1$, then, for every point z ∈ K, non-empty faces F ₁, …, F _s of K exist such that

$$\displaystyle{z \in \text{conv}\left (F_{1} \cup \cdots \cup F_{s}\right )}$$

and

$$\displaystyle{\text{dim}F_{i} \leq n_{i} - 1\ \ \text{for\ all}\ \ i = 1,\ldots,s.}$$

Comments. For convex polytopes K the conjecture holds true.

2 Comprehensive Research Problems

2.1 The Contact Number Problem of Unit Sphere Packingsby Károly Bezdek

Let B be a ball in the d-dimensional Euclidean space ${\mathbb{E}}^{d}$. Then the contact graph of an arbitrary finite packing by non-overlapping translates of B in ${\mathbb{E}}^{d}$ is the (simple) graph whose vertices correspond to the packing elements and whose two vertices are connected by an edge if and only if the corresponding two packing elements touch each other. One of the most basic questions on contact graphs is to find the maximum number of edges that a contact graph of n non-overlapping translates of the given Euclidean ball B can have in ${\mathbb{E}}^{d}$. Harborth [44] proved the following remarkable result on the contact graphs of congruent circular disk packings in ${\mathbb{E}}^{2}$. The maximum number of touching pairs in a packing of n congruent circular disks in ${\mathbb{E}}^{2}$ is precisely $\lfloor 3n -\sqrt{12n - 3}\rfloor$. The analogue question in the hyperbolic plane has been studied by Bowen in [42]. We prefer to quote his result in the following geometric way: Consider circle packings in the hyperbolic plane, by finitely many congruent circles, which maximize the number of touching pairs for the given number of congruent circles. Then such a packing must have all of its centers located on the vertices of a triangulation of the hyperbolic plane by congruent equilateral triangles, provided the diameter D of the circles is such that an equilateral triangle in the hyperbolic plane of side length D has each of its angles equal to $\frac{2\pi } {N}$ for some N > 6.

Now, we are ready to phrase the Contact Number Problem of finite congruent sphere packings in ${\mathbb{E}}^{3}$. For a given positive integer n ≥ 2 find the largest number C(n) of touching pairs in a packing of n congruent balls in ${\mathbb{E}}^{3}$. One can regard this problem as a combinatorial relative of the long-standing Kepler conjecture on the densest unit sphere packings in ${\mathbb{E}}^{3}$, which has been recently proved by Hales [43]. It is natural to continue with the following question.

Problem 1.

Find those positive integers n for which C(n) can be achieved in a packing of n unit balls in ${\mathbb{E}}^{3}$ consisting of parallel layers of unit balls each being a subset of the densest infinite hexagonal layer of unit balls.

Harborth’s result [44] implies in a straightforward way that if the maximum number of touching pairs in packings of n congruent circular disks in ${\mathbb{E}}^{2}$ is denoted by c(n), then

$$\displaystyle{\lim _{n\rightarrow +\infty }\frac{3n - c(n)} {\sqrt{n}} = \sqrt{12} = 3.464\ldots.}$$

The author [39] has proved the following estimates in higher dimensions. The number of touching pairs in an arbitrary packing of n > 1 unit balls in ${\mathbb{E}}^{d}$, d ≥ 3 is less than

$$\displaystyle{\frac{1} {2}\tau _{d}\,n - \frac{1} {{2}^{d}}\delta _{d}^{-\frac{d-1} {d} }\;{n}^{\frac{d-1} {d} },}$$

where τ _d stands for the kissing number of a unit ball in ${\mathbb{E}}^{d}$ (i.e., it denotes the maximum number of non-overlapping unit balls of ${\mathbb{E}}^{d}$ that can touch a given unit ball in ${\mathbb{E}}^{d}$) and δ _d denotes the largest possible density for (infinite) packings of unit balls in ${\mathbb{E}}^{d}$. Now, recall that on the one hand, according to the well-known theorem of Kabatiansky and Levenshtein [47] τ _d  ≤ 2^{0. 401d(1 + o(1))} and $\delta _{d} \leq {2}^{-0.599d(1+\text{o}(1))}$ as d →  + ∞ on the other hand, τ ₃ = 12 (for the first complete proof see [48]) moreover, according to the recent breakthrough result of Hales [43] $\delta _{3} = \frac{\pi } {\sqrt{18}}$. Thus, by combining the above results together we get that the number of touching pairs in an arbitrary packing of n > 1 unit balls in ${\mathbb{E}}^{d}$ is less than

$$\displaystyle{\frac{1} {2}{2}^{0.401d(1+\text{o}(1))}\,n -\frac{1} {2}{2}^{-0.401(d-1)(1-\text{o}(1))}\;{n}^{\frac{d-1} {d} }}$$

as d →  + ∞ and in particular, it is less than

$$\displaystyle{6n -\frac{1} {8}{\left ( \frac{\pi } {\sqrt{18}}\right )}^{-\frac{2} {3} }\;{n}^{\frac{2} {3} } = 6n - 0.152\ldots {n}^{\frac{2} {3} }}$$

for d = 3. Next we report on a recent improvement on the latter estimate. In order, to state that theorem in a proper form we need to introduce a bit of additional terminology. If $\mathcal{P}$ is a packing of n unit balls in ${\mathbb{E}}^{3}$, then let $C(\mathcal{P})$ stand for the number of touching pairs in $\mathcal{P}$, that is, let $C(\mathcal{P})$ denote the number of edges of the contact graph of $\mathcal{P}$ and call it the contact number of $\mathcal{P}$. Moreover, let C(n) be the largest $C(\mathcal{P})$ for packings $\mathcal{P}$ of n unit balls in ${\mathbb{E}}^{3}$. Finally, let us imagine that we generate packings of n unit balls in ${\mathbb{E}}^{3}$ in such a special way that each and every center of the n unit balls chosen, is a lattice point of the face-centered cubic lattice Λ _fcc with shortest non-zero lattice vector of length 2. Then let C _fcc (n) denote the largest possible contact number of all packings of n unit balls obtained in this way. Before stating our main theorem we make the following comments. First, recall that according to [43] the lattice unit sphere packing generated by Λ _fcc gives the largest possible density for unit ball packings in ${\mathbb{E}}^{3}$, namely $\frac{\pi }{\sqrt{18}}$ with each ball touched by 12 others such that their centers form the vertices of a cuboctahedron. Second, it is easy to see that $C_{fcc}(2) = C(2) = 1,C_{fcc}(3) = C(3) = 3,C_{fcc}(4) = C(4) = 6$. Third, it is natural to conjecture that $C_{fcc}(9) = C(9) = 21$. Based on the trivial inequalities $C(n + 1) \geq C(n) + 3,C_{fcc}(n + 1) \geq C_{fcc}(n) + 3$ valid for all n ≥ 2, it would follow that $C_{fcc}(5) = C(5) = 9,C_{fcc}(6) = C(6) = 12,C_{fcc}(7) = C(7) = 15$, and $C_{fcc}(8) = C(8) = 18$. In general, clearly C(n) ≥ C _fcc (n) ≥ 3n − 6. Furthermore, we note that C(10) ≥ 25, C(11) ≥ 29, and C(12) ≥ 33. In order, to see that one should take the union U of two regular octahedra of edge length 2 in ${\mathbb{E}}^{3}$ such that they share a regular triangle face T in common and lie on opposite sides of it. If we take the unit balls centered at the nine vertices of U, then there are exactly 21 touching pairs among them. Also, we note that along each side of T the dihedral angle of U is concave and in fact, it can be completed to 2π by adding twice the dihedral angle of a regular tetrahedron in ${\mathbb{E}}^{3}$. This means that along each side of T two triangular faces of U meet such that for their four vertices there exists precisely one point in ${\mathbb{E}}^{3}$ lying outside U and at distance 2 from each of the four vertices. Finally, if we take the 12 vertices of a cuboctahedron of edge length 2 in ${\mathbb{E}}^{3}$ along with its center of symmetry, then the 13 unit balls centered about them have 36 contacts implying that C(13) ≥ 36. Whether in any of the inequalities C(10) ≥ 25, C(11) ≥ 29, C(12) ≥ 33, and C(13) ≥ 36 we have equality seems to be an open question. In connection with this problem we call the reader’s attention to the very recent and highly elegant article of Hayes [45]. It gives an overview of the computational methods presented in the papers [38] and [46] that are based on exhaustive enumeration and elementary geometry. The main results are: $C(9) = 21,C(10) = 25$ [38] and C(11) = 29 [46]. However, the status of the mathematical rigour of the approaches of [38] as well as [46] remains to be seen. For C(n) in general, when n is an arbitrary positive integer, we have the following estimates proved in [40] and [41].

Theorem 1.

• (i) $C(n) < 6n - 0.926{n}^{\frac{2} {3} }$ for all n ≥ 2.

• (ii) $C_{fcc}(n) < 6n -\frac{3\root{3}\of{18\pi }} {\pi } {n}^{\frac{2} {3} } = 6n - 3.665\ldots {n}^{\frac{2} {3} }$ for all n ≥ 2.

• (iii) $6n -\root{3}\of{486}{n}^{\frac{2} {3} } < C_{fcc}(n) \leq C(n)$ for all $n = \frac{k(2{k}^{2}+1)} {3}$ with k ≥ 2.

As an immediate result we get

Corollary 1.

$$\displaystyle{0.926 < \frac{6n - C(n)} {{n}^{\frac{2} {3} }} < \root{3}\of{486} = 7.862\ldots }$$

for all $n = \frac{k(2{k}^{2}+1)} {3}$ with k ≥ 2.

The latter claim leads us to the following rather basic question.

Problem 2.

Does the limit $\lim _{n\rightarrow +\infty }\frac{6n-C(n)} {{n}^{\frac{2} {3} }}$ exist?

The following was noted in [39]. Due to the Minkowski difference body method the family $\mathcal{P}_{\mathbf{K}}:=\{ \mathbf{t}_{1} + \mathbf{K},\mathbf{t}_{2} + \mathbf{K},\ldots,\mathbf{t}_{n} + \mathbf{K}\}$ of n translates of the convex body K in ${\mathbb{E}}^{d}$ is a packing if and only if the family $\mathcal{P}_{\mathbf{K}_{\mathbf{o}}}:=\{ \mathbf{t}_{1} + \mathbf{K}_{\mathbf{o}},\mathbf{t}_{2} + \mathbf{K}_{\mathbf{o}},\ldots,\mathbf{t}_{n} + \mathbf{K}_{\mathbf{o}}\}$ of n translates of the symmetric difference body $\mathbf{K}_{\mathbf{o}}:= \frac{1} {2}(\mathbf{K} + (-\mathbf{K}))$ of K is a packing in ${\mathbb{E}}^{d}$. Moreover, the number of touching pairs in the packing $\mathcal{P}_{\mathbf{K}}$ is equal to the number of touching pairs in the packing $\mathcal{P}_{\mathbf{K}_{\mathbf{o}}}$. Thus, for this reason and for the reason that if K is a convex body of constant width in ${\mathbb{E}}^{d}$, then K _o is a ball of ${\mathbb{E}}^{d}$, Theorem 1 extends in a straightforward way to translative packings of convex bodies of constant width in ${\mathbb{E}}^{3}$.

2.2 On Gram and Euclidean Graph Realizations by Monique Laurent and Antonios Varvitsiotis

We present two open problems about the graph parameters ed(G), gd(G) and ν ⁼(G), which deal with some geometric realizations of graphs.

Problem 3.

Determine the validity of the inequality:

$$\displaystyle{ \mathrm{ed}(\nabla G) \leq \mathrm{ ed}(G) + 1, }$$

(1)

relating the Euclidean dimension of a graph G and of its suspension ∇ G.

Comments: Given a graph G = ([n], E), its Euclidean dimension is the graph parameter ed(G) which is defined as the smallest integer k ≥ 1 such that, for every family of vectors p ₁, …, p _n , there exists another family of vectors $q_{1},\ldots,q_{n} \in {\mathbb{R}}^{k}$ satisfying

$$\displaystyle{\|p_{i} - p_{j}\|_{2} =\| q_{i} - q_{j}\|_{2},\ \forall \{i,j\} \in E.}$$

The suspension graph ∇ G is obtained from G by adding to it a new node and making it adjacent to all the nodes of G.

The parameter ed(G) was studied in [49] where it is shown that for any fixed k ≥ 1, the class of graphs satisfying ed(G) ≤ k is closed under the operation of taking minors. That is, the Euclidean dimension does not increase if one deletes or contracts an edge e in G: $\mathrm{ed}(G \setminus e),\mathrm{ed}(G/e) \leq \mathrm{ ed}(G)$. Then, the Graph Minor Theorem of Robertson and Seymour implies that, for any fixed k ≥ 1, there exists a finite family of graphs $G_{1},\ldots G_{t_{k}}$ having the property that ed(G) ≤ k if and only if G does not have any minor isomorphic to any of $G_{1},\ldots,G_{t_{k}}$. In other words, the graph property ed(G) ≤ k can be characterized by finitely many minimal forbidden minors. In [49, 50] the full list of minimal forbidden minors is identified for k ∈ { 1, 2, 3}. Specifically, K _k + 2 is the only minimal forbidden minor when k ∈ { 1, 2} and, for ed(G) ≤ 3, there are two minimal forbidden minors: K ₅ and the octahedral graph K _2, 2, 2.

The following inequality is shown in [54], relating the Euclidean dimension of a graph and of its suspension:

$$\displaystyle{ \mathrm{ed}(\nabla G) \geq \mathrm{ ed}(G) + 1. }$$

(2)

Thus our first problem asks whether the converse inequality holds or, equivalently, whether it is true that

$$\displaystyle{ \mathrm{ed}(\nabla G) =\mathrm{ ed}(G) + 1. }$$

(3)

By combining results from [49] and [54] it follows that the answer is positive when ed(G) ≤ 3, i.e., when G is K ₅ and K _2, 2, 2-minor free.

In a similar manner, the Gram dimension gd(G) is defined as the smallest integer k ≥ 1 such that, for every family of vectors p ₁, …, p _n , there exists another family of vectors $q_{1},\ldots,q_{n} \in {\mathbb{R}}^{k}$ satisfying

$$\displaystyle{\|p_{i}\|_{2} =\| q_{i}\|_{2},\ \forall i \in [n],\ \text{ and }\ p_{i}^{\mathsf{T}}p_{ j} = q_{i}^{\mathsf{T}}q_{ j},\ \forall \{i,j\} \in E.}$$

This parameter was introduced in [53, 54] and its study is motivated by its connection with the low rank positive semidefinite matrix completion problem.

In [53, 54] it is shown that, for any fixed k ≥ 1, the class of graphs satisfying gd(G) ≤ k is closed under taking minors. Moreover, it is shown that K _k + 1 is the only minimal forbidden minor for k ∈ { 1, 2, 3} and that K ₅ and K _2, 2, 2 are the only minimal forbidden minors for the graph property gd(G) ≤ 4. We also show the following equality, which relates the Gram dimension of a graph to the Euclidean dimension of its suspension:

$$\displaystyle{ \mathrm{gd}(G) =\mathrm{ ed}(\nabla G). }$$

(4)

Combining with (2), we obtain that gd(G) ≥ ed(G) + 1 for any graph G. Therefore, Problem 1 is equivalent to the validity of the following equality:

$$\displaystyle{ \mathrm{gd}(G) =\mathrm{ ed}(G) + 1. }$$

(5)

Problem 4.

Determine the validity of the inequality

$$\displaystyle{ \mathrm{gd}(G) {\leq \nu }^{=}(G), }$$

(6)

relating the Gram dimension gd(G) and the van der Holst parameter ν ⁼(G).

Comments: Let $\mathcal{S}_{+}^{n}$ denote the cone of n ×n positive semidefinite matrices. Given a graph G = ([n], E) consider the cone

$$\displaystyle{\mathcal{C}(G) =\{ M \in \mathcal{S}_{+}^{n}: M_{ ij} = 0\ \text{ for }\{i,j\}\not\in E\text{ and }i\not =j\}.}$$

The parameter ν ⁼(G) is defined as the maximum corank of a matrix $M \in \mathcal{C}(G)$ satisfying the following nondegeneracy property:

$$\displaystyle{\forall X \in {\mathcal{S}}^{n}\ \ \ MX = 0,\ X_{ ii} = 0\ \forall i \in V,\ X_{ij} = 0\ \forall \{i,j\} \in E\ \Longrightarrow X = 0,}$$

known as the Strong Arnold Property. This graph parameter was introduced in [52] and its study is motivated by its relation to the celebrated graph invariant μ(G) of Colin de Verdière [51].

In [52] is shown that, for any fixed k ≥ 1, the class of graphs with ν ⁼(G) ≤ k is closed under taking minors. Additionally, the full list of minimal forbidden minors was determined for k ∈ { 1, 2, 3, 4}. Surprisingly, it turns out that the forbidden minors for the property ν ⁼(G) ≤ k coincide with the forbidden minors for the property gd(G) ≤ k, for each k ∈ { 1, 2, 3, 4}.

This observation prompted the investigation of possible links between these two parameters. A first result in this direction was established in [53, 54] where it was shown that, for any graph G,

$$\displaystyle{ \mathrm{gd}(G) {\geq \nu }^{=}(G). }$$

(7)

Our second problem asks for the validity of the converse inequality. In other words, is it true that the two graph parameters gd( ⋅) and ν ⁼( ⋅) coincide? We know that the answer is positive, e.g., for the graphs with Gram dimension at most 4, and for chordal graphs.

2.3 Non-convex Optimization Approaches to Network Localization by Anthony Man-Cho So and Yinyu Ye

Determining the positions of a set of n points in Euclidean space based on knowledge of a subset of the $\left ({ n \atop 2} \right )$ pairwise distances is a fundamental geometric problem with numerous applications. For instance, in location-aware networks—which support a host of services such as emergency response [14], mobile advertising [18], and target tracking [23]—wireless nodes that are deployed in an area of interest must be able to localize themselves using distance measurements obtained from direct communications with their neighbors. Another example can be found in biochemistry, where the positions of atoms in a molecule—which provide important information about the properties and functions of the molecule—are typically determined from a set of geometric constraints that include a subset of the inter-atomic distances [6]. As the above examples suggest, in many applications of the localization problem, it is only meaningful to localize the points in an Euclidean space of given dimension, say in ${\mathbb{R}}^{2}$ or ${\mathbb{R}}^{3}$. Unfortunately, such a fixed-dimensional localization problem is intractable in general [17]. In fact, as shown in Biswas and Ye [5], the d-dimensional localization problem can be formulated as a rank-constrained semidefinite program (SDP), namely,

$$\displaystyle{ \begin{array}{c@{\quad }l} \mbox{ find} \quad &Z \in {\mathbb{R}}^{n\times n} \\ \mbox{ such that}\quad &\mathcal{E}(Z) = u, \\ \quad &Z \succcurlyeq \mathbf{0},\,\mbox{ rank}(Z) \leq d. \end{array} }$$

(8)

Here, the linear operator $Z\mapsto \mathcal{E}(Z) = (\mbox{ tr}(E_{1}Z),\ldots,\mbox{ tr}(E_{m}Z)) \in {\mathbb{R}}^{m}$ and vector $u \in {\mathbb{R}}^{m}$ are determined by the available distance measurements, d ≥ 1 is the target dimension in which the input instance should be localized, and Z ≽ 0 means that Z is a symmetric positive semidefinite matrix. On the other hand, by dropping the non-convex constraint rank(Z) ≤ d, one immediately obtains an SDP relaxation of the fixed-dimensional localization problem. Such a relaxation and its variants have been extensively studied in recent years (see, e.g., [3, 4, 7, 9, 10, 12, 16, 19, 21, 22, 24]) and are very natural as far as polynomial-time solvability is concerned. Moreover, they have the added advantage that in many cases, localization accuracy guarantees can be established; see, e.g., [10, 20–22, 24]. However, standard interior-point algorithms for solving SDPs will always return the solution with the highest rank [21], which means that they are unlikely to deliver a feasible solution to the rank-constrained problem (8) in general. Thus, it is interesting to ask whether there are other efficient approaches for finding low-rank solutions to the SDP relaxation of (8).

In a recent work, Ji et al. [11] depart from the convex relaxation paradigm and develop a non-convex optimization approach for tackling Problem (8). Such an approach is motivated by ideas from low-rank matrix recovery—a topic that has received significant interest recently; see, e.g., the website [15] and the references therein. Specifically, for a given p ∈ (0, 1], consider the following regularized version of Problem (8):

$$\displaystyle{ \begin{array}{ccc@{\quad }l} {\Gamma }^{{\ast}}& =& \mbox{ minimize} \quad &f_{p}(Z) =\sum _{ i=1}^{n}\sigma _{ i}{(Z)}^{p} \\ & &\mbox{ subject to}\quad &\mathcal{E}(Z) = u, \\ & & \quad &Z \succcurlyeq \mathbf{0}.\end{array} }$$

(9)

Here, σ _i (Z) is the i-th singular value of Z. The value (f _p (Z))^1 ∕ p is known as the Schatten p-quasi-norm of Z, and it is easy to verify that f ₁(Z) = tr(Z) and f _p (Z) → rank(Z) as $p \searrow 0$ for all $Z \succcurlyeq \mathbf{0}$. This suggests that the Schatten quasi-norms can be effective in finding a low-rank solution to Problem (9), especially when p is small. However, a fundamental challenge associated with Problem (9) is that the function $Z\mapsto f_{p}(Z)$ is non-convex when p ∈ (0, 1). Indeed, the problem of minimizing the Schatten p-quasi-norm over a system of linear matrix inequalities is NP-hard for any fixed p ∈ (0, 1); cf. [8]. To circumvent this difficulty, Ji et al. [11] design a potential reduction algorithm and show that it can approximate a first-order critical point of Problem (9) to any given accuracy in polynomial time. In other words, given an accuracy level ε > 0, the algorithm will return a solution $\bar{Z}$ in polynomial time that is feasible for (9) and satisfies one of the following conditions:

• (a) $\bar{Z}$ is an ε-optimal solution, i.e., $f_{p}(\bar{Z}) \leq \epsilon$.

• (b) $\bar{Z}$ is an ε-first-order critical point, i.e., there exists a multiplier $\bar{y} \in {\mathbb{R}}^{m}$ such that

  $$\displaystyle{p{\Lambda }^{p-1} -\sum _{ i=1}^{m}\bar{y}_{ i}\left ({U}^{T}E_{ i}U\right ) \succcurlyeq \mathbf{0}}$$

  and

  $$\displaystyle{0 \leq \frac{\mbox{ tr}\left (p\bar{{Z}}^{p} -\sum _{i=1}^{m}\bar{y}_{i}E_{i}\bar{Z}\right )} {f_{p}(\bar{Z})} \leq \epsilon,}$$

  where $\bar{Z} = U\Lambda {U}^{T}$ is the spectral decomposition of $\bar{Z}$ with $U \in {\mathbb{R}}^{n\times r}$, $\Lambda = \mbox{ Diag}(\lambda _{1},\ldots,\lambda _{r}) \in {\mathbb{R}}^{r\times r}$ and $r = \mbox{ rank}(\bar{Z})$, and $\bar{{Z}}^{p} = U{\Lambda }^{p}{U}^{T} = U\,\mbox{ Diag}(\lambda _{1}^{p},\ldots,\lambda _{r}^{p})\,{U}^{T}$.

Moreover, it is shown in [11] that if the input instance is universally rigid,¹ then the potential reduction algorithm can localize it in the required dimension, even though the algorithm may only return a first-order critical point. This indicates that the localizability guarantee of the potential reduction algorithm is at least as strong as that of the SDP relaxations in [4, 5]. Computationally, it is observed that the potential reduction algorithm can localize some of the globally rigid² but not universally rigid input instances in the required dimension [11]. It is worth noting that by an earlier result of So and Ye [21], the SDP relaxation of Biswas and Ye [5] will necessarily fail to localize such instances in the required dimension. This phenomenon strongly motivates a deeper investigation of the approach proposed in [11].

Problem 5.

In view of the above developments, it is clear that there are many directions for further investigation. One of the most immediate questions is to understand the power of the non-convex Schatten quasi-norm regularization in the context of localization. Specifically, can we characterize the class of input instances that can be localized in the required dimension by the potential reduction algorithm of Ji et al.? From the results in [11], it is clear that this class will be larger than that of universally rigid instances. However, it will certainly be smaller than that of globally rigid instances, since the problem of localizing an arbitrary globally rigid instance in the required dimension is intractable [2]. This also suggests that some new rigidity-theoretic notions may be waiting to be discovered.

Along the same direction, it will be interesting to study the rigidity-theoretic implications of Schatten quasi-norm regularization. A starting point could be to understand the rigidity-theoretic interpretations of the dual vector $\bar{y}$ in the definition of the first-order critical point. This is motivated by an earlier result of So and Ye [20], which states that each dual variable in the SDP relaxation of Biswas and Ye [5] corresponds to a stress on an edge of the input graph, and the optimality conditions of the SDP correspond to a certain equilibrium condition on the input graph. The work [20] has since motivated or been used to develop other rigidity-theoretic results (see, e.g., [1, 13]), and a natural question would be whether these results have counterparts in the Schatten quasi-norm regularization setting.