Congestion in networks and manifolds,
and fair-division problems

Dong Zhang Department of Mathematics, University of Southern California, Los Angeles CA 90089-2532, U.S.A. [email protected]

Abstract.

Several large scale networks, such as the backbone of the Internet, have been observed to behave like convex Riemannian manifolds of negative curvature. In particular, this paradigm explains the observed existence, for networks of this type, of a “congestion core” through which a surprising large fraction of the traffic transits, while this phenomenon cannot be detected by purely local criteria. In this practical situation, it is important to estimate and predict the size and location of this congestion core. In this article we reverse the point of view and, motivated by the physical problem, we study congestion phenomena in the purely theoretical framework of convex Riemannian manifolds of negative curvature. In particular, we introduce a novel method of fair-division algorithm to estimate the size and impact of the congestion core in this context.

This work was partially supported by the grant DMS-1711297 from the US National Science Foundation.

1. Introduction

1.1. Congestion on networks

Traffic congestion problems are critical in the study of network transportation, from rush-hour traffic jams on city highways to routing data between internet users. With applications to internet traffic, biological and social sciences, and material transportation, understanding the key structural properties of large-scale data networks is crucial for analyzing and optimizing performances, and for improving security and reliability [13].

In recent years, a great amount of empirical results have shown that many different types of data networks share features with negatively curved graphs with small hyperbolicity constants [1, 5, 7, 9, 10, 11, 12, 13, 14]. A consequence of this, consistent with experimental data, is that a large percentage of the traffic between vertices (nodes) tends to go through a relatively small subset of the network. This approach is based on a common and broadly applied method using insights from Riemannian geometry to study large scale networks. In particular, E. Jonckheere, M. Lou, F. Bonahon and Y. Baryshnikov [10] used this paradigm to predict the existence of a congestion core in negatively curved networks, which turned out to be consistent with observational data in [13].

On a more theoretical level, V. Chepoi, F. Dragan and Y. Vaxès [6] proved a more quantitative result: A Gromov $\delta$ -hyperbolic space admits a congestion core which intercects at least one-half of all geodesics of the space. They also found that such a core admits a radius of $4\delta$ .

Our goal is to better relate the congestion in a network to its geometric characteristics, such as its scale and curvature. In particular, we want to improve the quantitive measure of the density of congestion, namely, the percentage of all geodesic passing through a core, as well as providing methods to identify the location of the congestion core.

With is goal in mind, we reverse the point of view and, motivated by the congestion network problems, we consider similar properties for Riemannian manifolds. In particular, we exploit a completely new idea for this type of problem, borrowed from the general area of fair division algorithms; see the Fair-Cut Theorem 3 below.

1.2. The main theorem and its supporting properties

Our more precise result currently requires that we consider manifolds of constant negative curvature. We believe that a similar property should hold for variable negative curvature.

Recall that a Riemannian manifold is convex if any two points are joined by a unique geodesic arc, whose interior is disjoint from the boundary of the manifold. In particular, a compact convex manifold is always diffeomorphic to a closed ball.

Theorem 1 (Main Theorem).

Let $M$ be a compact convex $m$ -dimensional Riemannian manifold with constant negative sectional curvature $-k^{2}$ , with $k>0$ . Then, there exists a point $x_{0}\in M$ and a universal radius $r_{0}=\frac{1}{k}\log\left(\sqrt{2}+1\right)$ , such that at least $\frac{1}{m+1}$ of all the geodesics of the manifold pass through the ball $B(x_{0},r_{0})$ .

The dependence of the estimate on the dimension $m$ is certainly a flaw for applications to network. However, see Conjecture 23 in §6.2 for a conjectured uniform bound coming from our approach.

Our proof of Theorem 1 relies on two intermediate steps. The first one uses the following fundamental property of spaces of negative curvature.

In a convex Riemannian manifold $M$ of negative curvature $M$ , a point $x\in M$ and a unit vector $v\in T_{x}^{1}M$ determine a half-space $H(x,v)$ , consisting of all $y\in M$ such that the geodesic $[x,y]$ makes an angle $\leqslant\frac{\pi}{2}$ with $v$ at $x$ .

Theorem 2 (Blocked View Theorem).

Let $M$ be a convex Riemannian manifold of negative sectional curvature bounded above by $-k^{2}$ , with $k>0$ . Then, there exist a universal radius $r_{0}=\frac{1}{k}\log\left(\sqrt{2}+1\right)$ satisfying the following property: for every $x$ , $p\in M$ , the set of $q\in M$ such that the geodesic $[p,q]$ meets the ball $B(x,r_{0})$ contains the whole half-space $H(x,v_{p})$ , where $v_{p}$ is the unit tangent vector of the geodesic $[p,x]$ at $x$ .

In other words, the view of $H(x,v_{p})$ from the point $p$ is completely blocked by the ball $B(x,r_{0})$ . Such a property clearly fails if the curvature is allowed to approach 0.

This leads us to investigate the volumes of half-spaces $H(x,v)$ in $M$ . In Section 4, we introduce a geometric quantity that we call the fair-cut index of the manifold $M$ . It is defined as

\Phi(M)=\max_{x\in M}\min_{v\in T_{x}^{1}M}\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}M},

The next big idea in the proof of Theorem 1 is the following.

Theorem 3 (Fair-Cut Theorem).

Let $M$ be a compact convex $m$ -dimensional Riemannian manifold with non-positive constant sectional curvature that is also compact and convex. Then,

\Phi(M)\geqslant\frac{1}{m+1}.

Although our proof currently requires the curvature to be constant, this hypothesis is likely to be unnecessary.

A point $x_{0}$ where the maximum $\Phi(M)$ is attained is a fair-cut center for $M$ . The Fair-Cut Theorem can be rephrased as saying that every hyperplane passing through a fair-cut center cuts $M$ into pieces whose volume is at least $\frac{1}{m+1}$ times the volume of the whole manifold.

In Proposition 21, we show that the fair-cut centers form a convex subset of $M$ . In practice, this set is very often reduced to a single point, and the fair-cut center is unique.

2. Counting geodesics

2.1. Counting geodesics on a graph

To motivate the Riemannian setup, we first consider the case of graphs (or networks), which provides the motivation for this work.

A graph $G$ consists of a set $V$ of vertices (or nodes) and a set $E$ of edges (or links), such that every edge connects two vertices. The graph is connected if any two vertices $p$ , $q\in V$ can be connected by a path in $G$ , namely by a finite sequence of edges such that any two consecutive edges share an endpoint.

If we assign a positive length to each edge of $E$ (for instance a uniform length $1$ ), this defines a length for each path in $G$ , namely the sum of the lengths of the edges in the path. This defines the metric on the vertex set $V$ , where the distance between two vertices is the shortest length of a path joining them. A path in $G$ is geodesic if its length is shortest among all paths connecting its endpoints. We are interested in the set $\Gamma(G)$ of (oriented) geodesics of $G$ .

An important case is when the geodesic connecting two vertices $p$ , $q\in V$ is unique. In this case, we can label this geodesic as $[p,q]$ . Then, the set $\Gamma(G)$ is then the same as the square $V\times V$ of the vertex set $V$ . In particular,

\left|\Gamma(G)\right|=|V|^{2},

where $|\cdot|$ measures the size of a set.

To study congestion phenomena in a connected graph $G$ , we want to count the number of geodesics on a graph $G=(V,E)$ that pass through a given vertex $x\in V$ , or more generally near that vertex, and compare it to the total number of geodesics.

With this in mind, we introduce the set

C(x)=\{\gamma\in\Gamma(G);x\in\gamma\}

of geodesic traffic passing through the vertex $x\in V$ , as well as, for $r>0$ , the geodesic traffic set through the ball $B(x,r)$

C(x,r)=\{\gamma\in\Gamma(G);d(x,\gamma)\leqslant r\}.

Here $d(x,\gamma)$ denotes the shortest distance between $x$ and a vertex of the path $\gamma$ .

These are quantified by the numbers

\displaystyle D(x)

\displaystyle=\frac{|C(x)|}{|\Gamma(G)|}

\displaystyle D(x,r)

\displaystyle=\frac{|C(x,r)|}{|\Gamma(G)|}

which measure the density of traffic passing through the vertex $x$ , or through the ball $B(x,r)$ .

In this discrete setting, the sets $C(x)$ and $C(x,r)$ of course coincide when $r$ is less than the length of the shortest edge of $G$ .

2.2. Counting geodesics in a Riemannian manifold

We want to extend these ideas from graphs and networks to Riemannian manifolds.

Let $M$ be a compact Riemannian manifold with boundary. It is convex if any two points $p$ , $q\in M$ can be connected by a unique geodesic $[p,q]$ , meeting the boundary only at its endpoints (if at all). In particular, $M$ is then diffeomorphic to a closed ball.

In this case, we can identify the set $\Gamma(M)$ of geodesics of $M$ to the product $M\times M$ , and it makes sense to quantify the size of $\Gamma(M)$ as $|\Gamma(M)|=(\operatorname{vol}{M})^{2}$ where $\operatorname{vol}M$ is the volume of $M$ .

By analogy with the case of graphs, we then introduce the geodesic traffic set through the ball $B(x,r)$ as

C(x,r)=\{(p,q)\in M\times M;[p,q]\cap B(x,r)\neq\emptyset\},

and the density of the geodesic traffic passing through $B(x,r)$

D(x,r)=\frac{\operatorname{vol}{C(x,r)}}{(\operatorname{vol}{M})^{2}}

where, for the volume form $d\mu$ of $M$ , the volume $\operatorname{vol}{C(x,r)}$ is defined by

(1)

\operatorname{vol}{C(x,r)}=\int_{C(x,r)}d\mu(p)\,d\mu(q).

Note that, in this manifold setting, we are not interested in the geodesic traffic set passing through a single point, since it has measure 0 for the the volume form of $M\times M$ (except in the trivial case where $\dim(M)\leqslant 1$ ).

3. The Blocked View Theorem

We will restrict our attention to Riemannian manifolds of negative sectional curvature, which is the main framework where convexity occurs and is stable under perturbation. The Blocked View Theorem below is typical of negative curvature, and will provide a key estimate for our analysis.

We begin with a definition. Recall that $[p,q]$ denotes the geodesic arc going from $p$ to $q$ .

Definition 4 (The blocked view).

Let $M$ be a compact convex Riemannian manifold. For $p$ , $x\in M$ and a radius $r>0$ the blocked view set $C_{p}(x,r)$ is

C_{p}(x,r)=\big{\{}q\in M;[p,q]\cap B(x,r)\neq\emptyset\big{\}}.

In other words, $C_{p}(x,r)$ is the set of points $q$ whose view from $p$ is blocked by the ball $B(x,r)$ .

Then, Equation (1) can be rewritten as

(2)

\operatorname{vol}{C(x,r)}=\int_{p\in M}\operatorname{vol}{C_{p}(x,r)}~{}d\mu(p).

A point $x\in M$ and a unit tangent vector $v\in T_{x}^{1}M$ determine a half-space

H(x,v)=\big{\{}q\in M;~{}\langle v_{q},v\rangle\leqslant 0\text{ for the tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\}}.

Theorem 5 (Blocked View Theorem).

Let $M$ be a compact convex Riemannian manifold whose sectional curvature is bounded above by $-k^{2}$ with $k>0$ . Then, there exists a universal radius $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ such that, for any two distinct points $x$ , $p\in M$ , the blocked view set $C_{p}(x,r_{0})$ contains the half-space $H(x,v_{p})$ determined by the tangent vector $v+p$ of the geodesic $[p,x]$ at $x$ .

In other words, the view of the whole half-space $H(x,v_{p})$ from the point $p\in M$ is completely blocked by the ball $B(x,r_{0})$ . We call the universal radius $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ the blocking radius corresponding to the curvature bound $-k^{2}$ .

The proof of Theorem 5 is based on the following two lemmas.

Lemma 6.

In the $m$ -dimensional space $H^{m}_{k^{2}}$ of constant curvature $-k^{2}$ , consider two geodesics $[\bar{x},\bar{y}]$ and $[\bar{x},\bar{z}]$ making a right angle at $\bar{x}$ . Then, the distance from $\bar{x}$ to the geodesic $[\bar{y},\bar{z}]$ is uniformly bounded by $\frac{1}{k}\log\left(\sqrt{2}+1\right)$ .

Proof.

After rescaling the metric and restricting attention to a totally geodesic plane containing the three points $\bar{x}$ , $\bar{y}$ and $\bar{z}$ , we can arrange that $k=1$ and $m=2$ , and identify $H^{2}_{1}$ to the Poincaré disk model for the hyperbolic plane. After applying a suitable isometry, we can in addition assume that $\bar{x}$ coincides with the center $O$ of the disk. Also, moving $\bar{y}$ and $\bar{z}$ away from $x$ increases the distance from $\bar{x}$ to $[\bar{y},\bar{z}]$ . It therefore suffices to consider the case where $\bar{y}$ and $\bar{z}$ are in the circle at infinity $\partial_{\infty}H^{2}_{1}$ . In this special case, a simple computation in the Poincaré model shows that the distance from $x=O$ to $[\bar{y},\bar{z}]$ is exactly equal to $\log\left(\sqrt{2}+1\right)$ . This provides the required bound in the general case. ∎

Lemma 7.

Let $M$ be a convex Riemannian manifold whose sectional curvature is uniformly bounded above by $-k^{2}<0$ . Given a geodesic triangle $xyz$ in $M$ with a right angle at $x$ consider, in the space $H^{m}_{k^{2}}$ of constant curvature $-k^{2}$ , a triangle $\bar{x}\bar{z}\bar{p}$ with a right angle at $\bar{x}$ and whose legs are such that $d(x,y)=d(\bar{x},\bar{y})$ and $d(x,z)=d(\bar{x},\bar{z})$ . Then, the distance from $x$ to the geodesic $[y,z]$ is less than or equal to the distance from $\bar{x}$ to $[\bar{y},\bar{z}]$ . Namely,

d\big{(}x,[y,z]\big{)}\leqslant d\big{(}\bar{x},[\bar{y},\bar{z}]\big{)}.

Refer to caption — Figure 1. Comparing the triangles $xzp$ , $x^{\prime}z^{\prime}p^{\prime}$ and $\bar{x}\bar{z}\bar{p}$

Proof.

Consider another comparison triangle $x^{\prime}y^{\prime}z^{\prime}$ in $H^{m}_{k^{2}}$ , where $d(x,y)=d(x^{\prime},y^{\prime})$ , $d(x,z)=d(x^{\prime},z^{\prime})$ and $d(y,z)=d(y^{\prime},z^{\prime})$ . Using Proposition 1.7 of [2, Chap. II.1], ,

(3)

d(x,[y,z])\leqslant d(x^{\prime},[y^{\prime},z^{\prime}]).

By Toponogov’s theorem (see for instance [4, Chap. 2]), the angle of $x^{\prime}y^{\prime}z^{\prime}$ at $x^{\prime}$ is greater than the angle of $xyz$ at $x$ , so it is larger than $\pi/2$ . As a consequence, in the constant curvature space $H^{m}_{k^{2}}$ , the geodesic triangles $x^{\prime}y^{\prime}z^{\prime}$ and $\bar{x}\bar{y}\bar{z}$ are such that $d(x^{\prime},y^{\prime})=d(\bar{x},\bar{y})$ , $d(x^{\prime},z^{\prime})=d(\bar{x},\bar{z})$ , and the angle of $x^{\prime}y^{\prime}z^{\prime}$ at $x^{\prime}$ is greater than the angle of $\bar{x}\bar{y}\bar{z}$ at $\bar{x}$ . Moving these comparison triangles by isometries of $H^{m}_{k^{2}}$ , we can arrange that $x^{\prime}y^{\prime}z^{\prime}$ and $\bar{x}\bar{y}\bar{z}$ are contained in the same 2-dimensional space $H^{2}_{k^{2}}\subset H^{m}_{k^{2}}$ , modeled as the Poincaré disk. In addition, we can arrange that $x^{\prime}=\bar{x}$ , $y^{\prime}=\bar{y}$ , and the two triangles are on the same same side of $[x^{\prime},y^{\prime}]=[\bar{x},\bar{y}]$ , as illustrated in Figure 1. Since the legs $[x^{\prime},z^{\prime}]$ and $[\bar{x},\bar{z}]$ are also of the same length, a simple geometric argument in the Poincaré disk shows that

(4)

d(x^{\prime},[y^{\prime},z^{\prime}])\leqslant d(\bar{x},[\bar{y},\bar{z}]).

The combination of (3) and (4) completes the proof. ∎

We are now ready to prove Theorem 5.

Proof of the Blocked View Theorem 5.

Remember that we are trying to show that, for $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ , the blocked view set

C_{p}(x,r)=\big{\{}q\in M;[p,q]\cap B(x,r)\neq\emptyset\big{\}}

contains, for the tangent vector $v_{p}$ of the geodesic $[p,x]$ at $x$ , the half-space

H(x,v_{p})=\big{\{}q\in M;~{}\langle v_{p},v_{q}\rangle\leqslant 0\text{ for the tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\}}.

With this goal in mind, consider a point $q\in H(x,v_{p})$ . Since $p$ is in the complement of the half-space $H(x,v_{p})$ , there exists a point $z$ in the intersection of the geodesic $[p,q]$ and of the boundary $\partial H(x,v_{p})$ . By construction, the triangle $xpz$ has a right angle at the vertex $x$ .

The combination of Lemmas 6 and 7 then shows that $x$ is at distance at most $r_{0}$ from the geodesic $[p,z]$ , and therefore from the geodesic $[p,q]$ . As a consequence, the view from $p$ to $q$ is blocked by the ball $B(x,r_{0})$ , and $q$ belongs to the blocked view set $C_{p}(x,r)$ .

This concludes the proof of the Blocked View Theorem 5. ∎

4. The fair cut of a pie

This section is now devoted to an apparently unrelated problem. The connection with the congestion problem will be explained in §5.

The issue is a fair-division scheme for a pie. Suppose that Alice and Bob want to split a cake, and that each of them wants to optimize the size of their share. Alice decides a point through which the knife should cut, and Bob decides in which direction to apply the cut. Alice knows that, wherever she picks a point, Bob will choose the cut through this point that will maximize his share, and consequently minimize Alice’s share. So Alice’s goal is to find a point where any cut will guarantee her an optimum share of the cake. We call such a point a “fair-cut center”.

In our case, the cake is replaced by a convex Riemannian manifold $M$ of negative curvature, and the knife cut at the point $x\in M$ occurs along a geodesic hyperplane $\partial H(x,v)$ .

4.1. Definitions and the Fair-Cut Theorem

Let $M$ be a compact convex Riemannian manifold. For a point $x\in M$ and a unit vector $v\in T_{x}^{1}M$ , the half-space

H(x,v)=\big{\{}q\in M;\langle v_{q},v\rangle\leqslant 0\text{ for the tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\}}

is bounded by the geodesic hyperplane

\partial H(x,v)=\big{\{}q\in M;\langle v_{q},v\rangle=0\text{ for the tangent vector }v_{q}\text{ of }[q,x]\text{ at }x\big{\}}

Definition 8 (A fair cut of the pie).

Let $M$ be a compact, convex $m$ -dimensional Riemannian manifold with non-positive sectional curvature. The fair-cut index of $M$ is the number

(5)

\Phi(M)=\max_{x\in M}{\min_{v\in T_{x}^{1}M}{\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}{M}}}}.

In other words, if we consider the function $f_{x}\colon T_{x}^{1}M\longrightarrow[0,1]$ defined by

f_{x}(v)=\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}{M}},

which measures the percentage of the pie corresponding to $H(x,v)$ , and the function $\varphi_{M}\colon M\longrightarrow[0,1]$ defined as the minimum

\varphi_{M}(x)=\min_{v\in T_{x}^{1}M}{f_{x}(v)},

then the fair cut index is

(6)

\Phi(M)=\max_{x\in M}\varphi_{M}(x)=\max_{x\in M}{\min_{v\in T_{x}^{1}M}{f_{x}(v)}}=\max_{x\in M}\min_{v\in T_{x}^{1}M}\frac{\operatorname{vol}{H(x,v)}}{\operatorname{vol}M}.

We will obtain the following estimate.

Theorem 9 (Fair-cut Theorem).

Let $M$ be a compact, convex $m$ -dimensional Riemannian manifold with constant non-positive sectional curvature.

Then,

\frac{1}{m+1}\leqslant\Phi(M)\leqslant\frac{1}{2}.

The upper bound is an immediate consequence of the observation that

\operatorname{vol}{H(x,v)}+\operatorname{vol}{H(x,-v)}=\operatorname{vol}{M}.

The lower bound $\frac{1}{m+1}$ will require more elaborate arguments, described in the next sections.

Note that there exists manifolds $M$ for which the upper bound $\Phi(M)=\frac{1}{2}$ is achieved. This will happen when $M$ is radially symmetric about a point $x_{0}$ , in the sense that for every $p\in M$ there is a point $q\in M$ such that $x_{0}$ is the midpoint of the geodesic arc $[p,q]$ . Indeed, in this case, $\operatorname{vol}{H(x_{0},v)}=\operatorname{vol}{H(x_{0},-v)}=\frac{1}{2}\operatorname{vol}{M}$ for every $v\in T^{1}_{x_{0}}M$ .

We begin with a couple of lemmas, in the next two sections

4.2. Lipschitz continuity for the volume function

We will need an estimate on the local variation of the volume function $\operatorname{vol}{H(\cdot,\cdot)}:T^{1}M\longrightarrow\mathbb{R}_{+}$ .

Lemma 10 (Lipschitz bound for the volume function).

Let $M$ be a compact, convex $m$ -dimensional Riemannian manifold with non-positive sectional curvature bounded in an interval $[-k_{1}^{2},0]$ with $k_{1}\geqslant 0$ . Suppose that $t\mapsto(x(t),v(t))$ is a smooth curve in the unit tangent bundle of $M$ . Then

(7)

\Big{|}\frac{d}{dt}\operatorname{vol}{H(x(t),v(t))}\Big{|}\leqslant C(k_{1},D)\Big{|}\frac{d}{dt}\big{(}x(t),v(t)\big{)}\Big{|}

where $C(k_{1},D)$ is a constant depending only on the lower curvature bound $-k_{1}^{2}$ and on an upper bound $D$ for the diameter of $M$ .

Proof.

The proof uses the property that

\frac{d}{dt}\operatorname{vol}{H\big{(}x(t),v(t)\big{)}}=\int_{\partial H(x(t),v(t))}\langle N(y(t)),J(y(t))\rangle~{}d\mu(t),

where $d\mu(t)$ is the volume form on the hyperplane, $y(t)$ is any point on the hyperplane, $N(y(t))$ is the normal vector of $\partial H(x(t),v(t))$ at $y(t)$ , and $J(y(t))=\frac{d}{dt}y(t)$ . A proof can for instance be found in [8, Eqn. (7.2)].

Also, standard comparison arguments with Jacobi fields gives

\big{|}\langle N(y(t)),J(y(t))\rangle\big{|}\leqslant\big{|}J(y(t))\big{|}\leqslant\big{|}\cosh_{k_{1}}(D)+\sinh_{k_{1}}(D)\big{|},

where the functions $\cosh_{k_{1}}$ and $\sinh_{k_{1}}$ are defined as

\displaystyle\cosh_{k_{1}}(x)

\displaystyle=\cosh(k_{1}x)

\displaystyle\sinh_{k_{1}}(x)

\displaystyle=\frac{1}{k_{1}}\sinh(k_{1}x).

Finally, the volume $\operatorname{vol}{\partial H(x(t),v(t))}$ is bounded by a universal constant times $\sinh_{k_{1}}(D)^{n-1}$ . The required property then follows from these estimates. ∎

In particular, the function $\varphi_{M}$ is continuous. By compactness of the unit tangent bundle $T^{1}M$ , it attains its maximum at a point $x_{0}\in M$ such that

	$\displaystyle\varphi_{M}(x_{0})$	$\displaystyle=\Phi(M)=\max_{x\in M}{\varphi_{M}(x)}$
		$\displaystyle=\max_{x\in M}\min_{v\in T_{x_{0}}^{1}M}{f_{x_{0}}(v)}=\max_{x\in M}\min_{v\in T_{x_{0}}^{1}M}{\frac{\operatorname{vol}{H(x_{0},v)}}{\operatorname{vol}{M}}}.$

Definition 11.

Let $M$ be a compact, convex $m$ -dimensional Riemannian manifold with non-positive sectional curvature. A point $x_{0}\in M$ such that $\varphi_{M}(x_{0})=\Phi(M)$ is a fair-cut center for $M$ .

4.3. Moving half-spaces to their interiors

Lemma 12.

Let $M$ be an $m$ -dimensional Riemannian manifold of negative sectional curvature, then the sum of the angles of a geodesic triangle in $M$ is less than $\pi$ .

Proof.

This is an easy application of comparison theorems; see for instance [2, Prop II.1.7]. ∎

The next lemma requires the curvature of our manifold $M$ to be constant.

Lemma 13.

In an $m$ -dimensional Riemannian manifold $M$ of constant negative sectional curvature, let $H(x_{0},v_{0})\subset M$ be the half-space defined by a point $x_{0}\in M$ and a unit vector $v_{0}\in T_{x_{0}}^{1}M$ . For any $x$ in the interior of the half-space $H(x_{0},v_{0})$ , there exists a vector $v\in T_{x}^{1}M$ such that $H(x,v)$ is contained in the interior of $H(x_{0},v_{0})$ . In particular, $\operatorname{vol}H(x,v)<\operatorname{vol}H(x_{0},v_{0})$ .

Similarly, if $x$ is in $M\setminus H(x_{0},v_{0})$ , there exists $v\in T_{x}^{1}M$ such that the interior of $H(x,v)$ contains $H(x_{0},v_{0})$ , and $\operatorname{vol}H(x,v)>\operatorname{vol}H(x_{0},v_{0})$ .

Proof.

Let $z$ be a point in the boundary $\partial H(x_{0},v_{0})$ that is closest to $x$ , and let $w\in T_{z}^{1}M$ be the vector tangent to the geodesic $[z,x]$ at $z$ . Because the curvature is constant, $H(z,w)=H(x_{0},v_{0})$ . If $v\in T_{x}^{1}M$ is tangent to $[z,x]$ at $x$ , we conclude that $H(x,v)$ is contained in the interior of $H(z,w)=H(x_{0},v_{0})$ . (Otherwise, one would see a triangle with two right angles, which is excluded by the negative curvature.)

The second part of the statement is proved in a similar way. ∎

Remark 14.

This is the only point where we need the curvature of $M$ to be constant. It is quite likely that a similar statement can be proved under a weaker hypothesis, for instance the classical curvature pinching property that the sectional curvature is in an interval $[-4a^{2},-a^{2}]$ with $a>0$ .

4.4. Minimizing directions at a fair-cut center

We now focus on a fair-cut center $x_{0}$ for the manifold $M$ .

Proposition 15.

Suppose that $M$ is a compact convex manifold with constant negative curvature, and let $x_{0}\in M$ be a fair-cut center. Let

	$\displaystyle V_{x_{0}}$	$\displaystyle=\big{\{}v\in T_{x_{0}}^{1}M;f_{x_{0}}(v)=\varphi_{M}(x_{0})=\Phi(M)\}$
		$\displaystyle=\big{\{}v\in T_{x_{0}}^{1}M;\operatorname{vol}{H(x_{0},v)}=\Phi(M)\operatorname{vol}(M)\}$

be the set of minimizing directions at $x_{0}$ . Then

M=\bigcup_{v\in V_{x_{0}}}H(x_{0},v).

Proof.

Suppose, in search of a contradiction, that the half-spaces $H(x_{0},v)$ with $v\in V_{x_{0}}$ do not cover all of $M$ . We will then show that $x_{0}$ is not a local maximum of the function $\varphi_{M}$ , contradicting its definition.

If there exists a point $p\in M$ that is not in the union of the $H(x_{0},v)$ with $v\in V_{x_{0}}$ , the tangent of the geodesic arc $[x_{0},p]$ at $x_{0}$ provides a unit tangent vector $u_{0}\in T_{x_{0}}^{1}M$ such that $\langle u_{0},v\rangle<0$ for every $v\in V_{x_{0}}$ .

In particular, the set $\{v\in T_{x_{0}}^{1}M;\langle u_{0},v\rangle<0\}$ is an open neighborhood of the minimizing set $V_{x_{0}}=\{v\in T_{x_{0}}^{1}M;\operatorname{vol}{H(x_{0},v)}=\Phi(M)\operatorname{vol}(M)\}$ . By compactness of $V_{x_{0}}$ , there consequently exists an $\alpha_{0}>0$ such that

\{v\in T_{x_{0}}^{1}M;\operatorname{vol}{H(x_{0},v)}<\Phi(M)\operatorname{vol}(M)+\alpha_{0}\}\subset\{v\in T_{x_{0}}^{1}M;\langle u_{0},v\rangle<0\}

In other words, for every $v_{0}\in T_{x_{0}}^{1}M$ , either

(8)

\operatorname{vol}{H(x_{0},v_{0})}\geqslant\Phi(M)\operatorname{vol}M+\alpha_{0}

(9)

\langle u_{0},v_{0}\rangle<0.

Let $g\colon(-\varepsilon,\varepsilon)\to M$ be a small geodesic arc with $g(0)=x_{0}$ and $g^{\prime}(0)=u_{0}$ . For $t>0$ , set $x_{t}=g(t)$ .

By definition of the function $\varphi_{M}(x)=\inf_{v\in T_{x}^{1}M}(\operatorname{vol}H(x,v))/(\operatorname{vol}M)$ and since $x_{0}$ realizes the maximum of this function, there exists $v_{t}\in T_{x_{t}}^{1}M$ such that

\operatorname{vol}H(x_{t},v_{t})=\varphi_{M}(x_{t})\operatorname{vol}M\leqslant\varphi_{M}(x_{0})\operatorname{vol}M=\Phi(M)\operatorname{vol}M.

Let $v_{0}\in T_{x_{0}}^{1}M$ be obtained by parallel translating $v_{t}$ along the geodesic $g$ .

The Lipschitz continuity property of Lemma 10 shows that, provided we chose $x_{t}$ sufficiently close to $x_{0}$ (depending only on the constant $\alpha_{0}>0$ arising in (8) ), we have that

	$\displaystyle\operatorname{vol}H(x_{0},v_{0})$	$\displaystyle\leqslant\operatorname{vol}H(x_{t},v_{t})+{\textstyle\frac{1}{2}}\alpha_{0}$
		$\displaystyle\leqslant\Phi(M)\operatorname{vol}M+{\textstyle\frac{1}{2}}\alpha_{0}$

by choice of $v_{t}$ . As a consequence, (8) cannot hold.

Therefore, $v_{0}$ satisfies (9). Since $v_{t}$ is obtained by parallel translating $v_{0}$ along the geodesic $g$ , $\langle v_{t},g^{\prime}(t)\rangle=\langle v_{0},u_{0}\rangle<0$ . Lemma 13 then provides another vector $w_{0}\in T_{x_{0}}^{1}M$ such that

\operatorname{vol}H(x_{0},w_{0})<\operatorname{vol}H(x_{t},v_{t})\leqslant\varphi_{M}(x_{0})\operatorname{vol}M.

However, the existence of $w_{0}$ would contradict the fact that $\varphi_{M}(x_{0})$ is defined as the infimum of $\operatorname{vol}H(x_{0},v)/\operatorname{vol}M$ over all $v\in T_{x_{0}}^{1}M$ .

This final contradiction concludes the proof of Proposition 15. ∎

We now improve Proposition 15, by bounding the number of half-spaces $H(x_{0},v)$ , with $v\in V_{x_{0}}$ , needed to cover the manifold $M$ .

This is based on the following elementary observation.

Lemma 16.

In a compact convex manifold $M$ with nonpositive curvature, let $V$ be a subset of the unit tangent space $T_{x_{0}}^{1}M$ . The following properties are equivalent:

(1)

$M$ is the union of the half-spaces $H(x_{0},v)$ as $v$ ranges over all vectors of $V$ ;
(2)

for every $w\in T_{x_{0}}^{1}M$ , there exists $v\in V$ with $\langle v,w\rangle\geqslant 0$ ;
(3)

in the vector space $T_{x}M$ , the point $0$ is in the convex hull $\mathrm{Conv}(V)$ of $V$ .

Proof.

The equivalence of (1) and (2) is easily seen by considering, for every $x\in M$ , the tangent vector $w$ of the geodesic $[x_{0},x]$ at $x_{0}$ .

The equivalence of (2) and (3) is an elementary property of convex sets in $\mathbb{R}^{m}$ . ∎

Proposition 17.

Let $M$ be a compact convex manifold with constant negative curvature, and let $x_{0}\in M$ be its fair-cut center. Then, there exists $n$ vectors $v_{1}$ , $v_{2}$ , …, $v_{n}\in V_{x_{0}}$ in the mininimizing set $V_{x_{0}}\subset T_{x_{0}}^{1}M$ , with $n\leqslant\dim M+1$ , such that

M=\bigcup_{i=1}^{n}H(x_{0},v_{i}).

Proof.

By Proposition 15,

M=\bigcup_{v\in V_{x_{0}}}H(x_{0},v).

Lemma 16 then shows that $0$ is in the convex hull of $V_{x_{0}}$ . By Caratheodory’s theorem [3], there exists a subset $\{v_{1},v_{2},\dots,v_{n}\}\subset V_{x_{0}}$ of cardinal $n\leqslant\dim M+1$ whose convex hull also contains $0$ . Another application of Lemma 16 then shows that $M$ is the union of the $H(x_{0},v_{i})$ with $i=1$ , $2$ , …, $n$ . ∎

4.5. Proof of the Fair-Cut Theorem

We are now ready to prove the Fair-Cut Theorem 9. We already observed that $\Phi(M)\leqslant\frac{1}{2}$ , so we just need to restrict attention to the lower bound. .

By definition of the fair-cut center $x_{0}\in M$ and of the minimizing set $V_{x_{0}}\subset T_{x_{0}}^{1}M$ ,

\frac{\operatorname{vol}{H(x_{0},v)}}{\operatorname{vol}{M}}=\varphi_{M}(x_{0})=\Phi(M).

for every $v\in V_{x_{0}}$ .

Proposition 17 then shows that there exists $\{v_{1},v_{2},\dots,v_{n}\}\subset V_{x_{0}}$ with $n\leqslant m+1$ such that

M=\bigcup_{i=1}^{n}H(x_{0},v_{i}).

As a consequence,

\operatorname{vol}{M}\leqslant\sum_{i=1}^{n}\operatorname{vol}{H(x_{0},v_{i})}=n\Phi(M)\operatorname{vol}{M}\leqslant(m+1)\Phi(M)\operatorname{vol}{M}.

This proves that $\Phi(M)\geqslant\frac{1}{m+1}$ . ∎

Remark 18.

The only place where we used the condition that the sectional curvature is constant was in the proof of Lemma 13. It seems quite likely that Proposition 17 and Theorem 9 hold without this hypothesis.

5. Proof of the Main Theorem

We now combine the Blocked View Theorem 5 and the Fair-Cut Theorem 9 to provide an estimate on the percentage density of geodesic traffic.

Theorem 19.

Let $M$ be an $m$ -dimensional compact convex Riemannian manifold of constant negative sectional curvature $-k^{2}$ , with $k>0$ . Then, there exists a universal radius $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ and a point $x_{0}\in M$ such that at least $\frac{1}{m+1}$ of all the geodesics of the manifold pass through the ball $B(x_{0},r_{0})$ .

Proof.

Let $x_{0}$ be the fair-cut center of $M$ provided by the Fair-Cut Theorem 9, and let $r_{0}=\frac{1}{k}\log(\sqrt{2}+1)$ be the radius of the Blocked View Theorem 5. As in Section 2.2, let

C(x_{0},r_{0})=\{(p,q)\in M\times M;[p,q]\cap B(x_{0},r_{0})\neq\emptyset\}

be the set of geodesics $[p,q]$ of $M$ passing through the ball $B(x_{0},r_{0})$ , and for $p\in M$ let

C_{p}(x_{0},r_{0})=\{q\in M;[p,q]\cap B(x_{0},r_{0})\neq\emptyset\}

be the set of points whose view from $p$ is obstructed by $B(x_{0},r_{0})$ .

We saw in Equation 2 that

\operatorname{vol}{C(x_{0},r_{0})}=\int_{p\in M}\operatorname{vol}{C_{p}(x_{0},r_{0})}~{}d\mu(p).

where $d\mu$ is the volume form of $M$ .

For a given $p\in M$ , the Blocked View Theorem 5 asserts that $C_{p}(x_{0},r_{0})$ contains a half-space $H(x_{0},v_{p})$ , so that

\operatorname{vol}{C_{p}(x_{0},r_{0})}\geqslant\operatorname{vol}H(x_{0},v_{p}).

By definition of the fair-cut center $x_{0}\in M$ and by the Fair-Cut Theorem 9,

\operatorname{vol}H(x_{0},v_{p})\geqslant\varphi_{M}(x_{0})\operatorname{vol}M\geqslant\Phi(M)\operatorname{vol}M\geqslant\frac{1}{m+1}\operatorname{vol}M.

Combining these inequalities then gives

\operatorname{vol}{C(x_{0},r_{0})}=\int_{p\in M}\operatorname{vol}{C_{p}(x_{0},r_{0})}~{}d\mu(p)\geqslant\frac{1}{m+1}(\operatorname{vol}M)^{2}.

As a consequence, at least $\frac{1}{m+1}$ of all the geodesics of the manifold pass through the ball $B(x_{0},r_{0})$ . ∎

Definition 20.

The ball $B(x_{0},r_{0})$ is the congestion core of $M$ .

Note that the size of this congestion core is uniquely determined by the curvature, the dimension of the manifold provides an estimate of the density of the congestion, while the global geometry of the manifold contributes to the location of the core.

6. Additional comments

We conclude with a few observations and conjectures.

6.1. The set of fair-cut centers

Proposition 21.

In a compact convex manifold of constant nonpositive curvature, the set of fair-cut centers is convex.

Proof.

Let $x_{1}$ and $x_{2}$ be two fair-cut centers for $M$ . We want to show that every point $x$ in the geodesic arc $[x_{1},x_{2}]$ is also a fair-cut center.

By Proposition 15, $x_{2}$ belongs to some minimizing half-space $H(x_{1},v)$ , namely a half-space such that

\frac{\operatorname{vol}H(x_{1},v)}{\operatorname{vol}M}=\varphi(x_{1})=\Phi(M).

We claim that, for any such minimizing half-space $H(x_{1},v)$ containing $x_{2}$ , the point $x_{2}$ is necessarily on the boundary $\partial H(x_{1},v)$ . Indeed, if $x_{2}$ was not in $H(x_{1},v)$ , let $p$ be the point of $\partial H(x_{1},v)$ that is closest to $x_{2}$ and let $w\in T_{x_{2}}^{1}M$ be the unit tangent vector to the geodesic arc $[x_{2},p]$ . Because the curvature is constant, the half-space $H(x_{2},-w)$ is strictly contained in $H(x_{1},v)$ . In particular, $\operatorname{vol}H(x_{2},-w)<\operatorname{vol}H(x_{1},v)$ , this would imply that

\varphi(x_{2})<\varphi(x_{1})=\Phi(M)=\varphi(x_{2}),

a contradiction.

Let $x\in[x_{1},x_{2}]$ be different from $x_{1}$ and $x_{2}$ , and let $H(x,v)$ be a minimizing hyperplane for $x$ . The same argument as before shows that $x_{2}$ cannot be contained in the interior of $H(x,v)$ , as this would again provide the contradiction

\varphi(x_{2})<\varphi(x)\leqslant\Phi(M)=\varphi(x_{2}).

Therefore, $x_{2}$ is in the boundary of $H(x,v)$ and, since the curvature is constant, $H(x,v)=H(x_{2},v_{2})$ for some $v_{2}\in T_{x_{2}}^{1}M$ . Then,

\varphi(x)=\frac{\operatorname{vol}H(x,v)}{\operatorname{vol}M}=\frac{\operatorname{vol}H(x_{2},v_{2})}{\operatorname{vol}M}\geqslant\varphi(x_{2})=\Phi(M),

from which we conclude that $x$ is also a maximum of the function $\varphi$ , namely is also a fair-cut center. ∎

In fact, we conjecture the much stronger result that the fair-cut center is unique.

6.2. Heuristics about the fair-cut index $\Phi(M)$

Our lower bound $\frac{1}{m+1}$ for the fair-cut index $\Phi(M)$ seems far from being sharp. A heuristic argument suggests a lower bound that is independent of the dimension, which would also improve our congestion estimates. We briefly discuss this argument.

In a given dimension $m$ , we can try to find a manifold $M$ that approximates the infimum of $\Phi(M)$ over all $m$ –dimensional convex manifolds of negative curvature. Because $\Phi(M)$ is invariant under rescaling of the metric by a positive scalar, it makes sense to assume that such an approximatively minimizing manifold exists in curvature 0. Then, by trial and error based on the Marching Hyperplanes method of the next section, it seems that the infimum in this curvature 0 case is realized by a simplex $\Delta_{n}$ in Euclidean space $\mathbb{R}^{m}$ . Since any two simplices in $\mathbb{R}^{m}$ are equivalent under an affine isomorphism, they have the same fair-cut index $\Phi(\Delta_{n})$ .

The set of fair-cut centers is invariant under all the symmetries of the simplex, and is convex by Proposition 21. It follows that the barycenter $x_{0}$ of $\Delta_{n}$ is necessarily a fair-cut center.

Conjecture 22.

Let $\Delta_{n}$ be a simplex in the Euclidean space $\mathbb{R}^{m}$ , with nonempty interior. Then

\Phi(\Delta_{n})=\left(\frac{m}{m+1}\right)^{m}.

This is equivalent to the statement that, for the barycenter $x_{0}$ of $\Delta_{n}$ , the minimizing set $V_{x_{0}}\subset T_{x_{0}}^{1}\Delta_{n}$ consists of all unit vectors pointing towards the vertices of $\Delta_{n}$ .

Note that $\left(\frac{m}{m+1}\right)^{m}$ is a decreasing function of $m$ , and converges to $\mathrm{e}$ as $m$ tends to $\infty$ . All these considerations lead us to the following conjecture.

Conjecture 23.

The fair-cut index $\Phi(M)$ of any compact convex manifold $M$ with non-positive sectional curvature satisfies the sharp inequality

\Phi(M)\geqslant\frac{1}{\mathrm{e}}.

6.3. A method to estimate the fair-cut centers

The existence of fair-cut centers was abstractly established by minimizing the function $\varphi(x)$ . In practice, it may be useful to have a rough estimate of the location of these fair-cut centers. For this, we can use the following consequence of our Main Theorem 1.

Lemma 24.

If $\operatorname{vol}{H(x_{1},v_{1})}<\frac{1}{m+1}\operatorname{vol}{M}$ for some $v_{1}\in T_{x_{1}}^{1}M$ , then any fair-cut center $x_{0}$ is located outside of the half-space $H(x_{1},v_{1})$ .

Proof.

Suppose not, meaning that $x_{0}$ is located inside $H(x_{1},v_{1})$ . Then, let $x_{2}$ be the projection of $x_{0}$ to $\partial H(x_{1},v_{1})$ , and let the vectors $v_{2}\in T_{x_{2}}^{1}M$ and $v_{0}\in T_{x_{0}}^{1}M$ be tangent to the geodesic arc $[x_{2},x_{1}]$ . Then, $H(x_{0},v_{0})$ is contained in $H(x_{2},v_{2})=H(x_{1},v_{1})$ , and

\varphi_{M}(x_{0})\leqslant\frac{\operatorname{vol}H(x_{0},v_{0})}{\operatorname{vol}M}\leqslant\frac{\operatorname{vol}H(x_{1},v_{1})}{\operatorname{vol}M}<\frac{1}{m+1}\leqslant\Phi(M),

contradicting the fact that $\varphi_{M}(x_{0})=\Phi(M)$ . ∎

Now let us provide a procedure which we call the Marching Hyperplanes Method, in attempt to locate the whereabouts of the fair-cut center.

Step 1: Start from a point $x_{1}$ on the boundary of $M$ , pick a direction $v_{x_{1}}$ that is perpendicular to $\partial M$ at $x_{1}$ and point inward, then march forward inside $M$ along the geodesic $g_{1}$ starting from $x_{1}$ following $v_{x_{1}}$ , until reached a point $x_{1,0}$ such that the half-space $H(x_{1,0},-v_{x_{1,0}})$ has the volume of $\frac{1}{m+1}\operatorname{vol}{M}$ , where $v_{x_{1,0}}$ is the parallel translation of $v_{x_{1}}$ along $g_{1}$ . We mark $\partial H_{1}=\partial H(x_{1,0},-v_{x_{1,0}})$ , as shown in Figure 2.

Step 2 to m+1 and maybe more: Pick points $\{x_{i}\}$ , $i=2,...,m+1$ , and maybe more, on $\partial M$ , together with directions $v_{x_{i}}$ that is perpendicular to $\partial M$ at $x_{i}$ and point inward, then repeat the marching forward as Step 1, so we end up with lots of marked hyperplanes $\{\partial H_{i}\}$ , $i=2,...,m+1$ , and maybe more.

Final Step: By Proposition 24, the fair-cut center $x_{0}$ is outside any half-spaces that we have marched over, namely, it is located inside the entity that is bounded by all the hyperplanes, as shown in Figure 3.

Although this method does not provide a precise location the fair-cut center, for a small amount of steps, it does give us a very refined vicinity to locate the fair-cut center. In practice, I will suggest using the lower bound in Conjecture 23, i.e., $\frac{1}{e}$ , instead of $\frac{1}{m+1}$ , when the dimension increases.

References

[1] Aaron B Adcock, Blair D Sullivan, and Michael W Mahoney. Tree-like structure in large social and information networks. In 2013 IEEE 13th International Conference on Data Mining, pages 1–10. IEEE, 2013.
[2] Martin R Bridson and André Haefliger. Metric spaces of non-positive curvature, volume 319. Springer Science & Business Media, 2013.
[3] Constantin Carathéodory. Über den variabilitätsbereich der koeffizienten von potenzreihen, die gegebene werte nicht annehmen. Mathematische Annalen, 64(1):95–115, 1907.
[4] Jeff Cheeger and David G Ebin. Comparison theorems in Riemannian geometry, volume 365. American Mathematical Soc., 2008.
[5] Wei Chen, Wenjie Fang, Guangda Hu, and Michael W Mahoney. On the hyperbolicity of small-world and treelike random graphs. Internet Mathematics, 9(4):434–491, 2013.
[6] Victor Chepoi, Feodor F Dragan, and Yann Vaxès. Core congestion is inherent in hyperbolic networks. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2264–2279. SIAM, 2017.
[7] Fabien De Montgolfier, Mauricio Soto, and Laurent Viennot. Treewidth and hyperbolicity of the internet. In 2011 IEEE 10th International Symposium on Network Computing and Applications, pages 25–32. IEEE, 2011.
[8] Harley Flanders. Differentiation under the integral sign. The American Mathematical Monthly, 80(6):615–627, 1973.
[9] Edmond Jonckheere, Poonsuk Lohsoonthorn, and Francis Bonahon. Scaled Gromov hyperbolic graphs. Journal of Graph Theory, 57(2):157–180, 2008.
[10] Edmond Jonckheere, Mingji Lou, Francis Bonahon, and Yuliy Baryshnikov. Euclidean versus hyperbolic congestion in idealized versus experimental networks. Internet Mathematics, 7(1):1–27, 2011.
[11] W Sean Kennedy, Onuttom Narayan, and Iraj Saniee. On the hyperbolicity of large-scale networks. arXiv preprint arXiv:1307.0031, 2013.
[12] Poonsuk Lohsoonthorn. Hyperbolic geometry of networks. 2003. PhD thesis, University of Southern California.
[13] Onuttom Narayan and Iraj Saniee. Large-scale curvature of networks. Physical Review E, 84(6):066108, 2011.
[14] Yuval Shavitt and Tomer Tankel. Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Transactions on Networking, 16(1):25–36, 2008.

Congestion in networks and manifolds, and fair-division problems

Abstract.

1. Introduction

1.1. Congestion on networks

1.2. The main theorem and its supporting properties

Theorem 1 (Main Theorem).

Theorem 2 (Blocked View Theorem).

Theorem 3 (Fair-Cut Theorem).

2. Counting geodesics

2.1. Counting geodesics on a graph

2.2. Counting geodesics in a Riemannian manifold

3. The Blocked View Theorem

Definition 4 (The blocked view).

Theorem 5 (Blocked View Theorem).

Lemma 6.

Proof.

Lemma 7.

Proof.

Proof of the Blocked View Theorem 5.

4. The fair cut of a pie

4.1. Definitions and the Fair-Cut Theorem

Definition 8 (A fair cut of the pie).

Theorem 9 (Fair-cut Theorem).

4.2. Lipschitz continuity for the volume function

Lemma 10 (Lipschitz bound for the volume function).

Proof.

Definition 11.

4.3. Moving half-spaces to their interiors

Lemma 12.

Proof.

Lemma 13.

Proof.

Remark 14.

4.4. Minimizing directions at a fair-cut center

Proposition 15.

Proof.

Lemma 16.

Proof.

Proposition 17.

Proof.

4.5. Proof of the Fair-Cut Theorem

Remark 18.

5. Proof of the Main Theorem

Theorem 19.

Proof.

Definition 20.

6. Additional comments

6.1. The set of fair-cut centers

Proposition 21.

Proof.

6.2. Heuristics about the fair-cut index Φ​(M)\Phi(M)

Conjecture 22.

Conjecture 23.

6.3. A method to estimate the fair-cut centers

Lemma 24.

Proof.

References

Congestion in networks and manifolds,
and fair-division problems

6.2. Heuristics about the fair-cut index $\Phi(M)$