# Equivalence of Models of Cake-Cutting Protocols111This paper is based on the
second author’s final year project.

Paul W. Goldberg<EMAIL_ADDRESS>Ioana Iaru
Department of Computer Science<EMAIL_ADDRESS>Oxford University

###### Abstract

The cake-cutting problem involves dividing a heterogeneous, divisible resource
fairly between $n$ agents. Brânzei et al. , [6] introduced generalised cut and
choose (GCC) protocols, a formal model for representing cake-cutting protocols
as trees with “cut” and “choose” nodes corresponding to the agents’ actions,
and if-else statements.

In this paper, we identify an alternative and simpler extensive-form game
model for cake-cutting protocols, that we call branch choice (BC) protocols.
We show that the class of protocols we can represent using this model is
invariant under certain modifications to its definition. We further prove that
any such protocol can be converted to a restricted form in which the agents
first cut the cake and then get to choose between various branches leading to
different allocations. Finally, we show that this model has the same
expressive power as GCC protocols, i.e. they represent the same class of
protocols up to a notion of equivalence involving the bounds on envy that each
agent can guarantee for themselves. For this purpose, we introduce a new
notion of envy-equivalence of protocols.

##  1 Introduction

The cake-cutting problem is a fair division problem which involves dividing a
heterogeneous, divisible resource (the metaphorical “cake”) between several
agents, who have different preferences over different parts of the cake. In
practice, this framework can be used to divide various types of resources,
such as land or time. The modern study of this problem dates back to
Steinhaus, [12] and a description of its history can be found in the books by
Brams & Taylor, [2] or Robertson & Webb, [11].

To be able to tackle this problem, we need to establish what it means for a
division to be fair. There are two common criteria for fairness,
_proportionality_ , in which each of the $n$ agents receives a piece that they
consider to be worth at least $\frac{1}{n}$ of the entire cake, and _envy-
freeness_ , which means no agent prefers the piece another agent received over
their own. If the entire cake is allocated, envy-freeness implies
proportionality.

In the literature, well-known cake-cutting protocols are often described in
plain language, but to be able to reason about protocols more generally or
implement them on a computer, we require some formal model of computation.
There are several such models, the most well-known ones being the Robertson-
Webb model [11], which involves two types of queries: _Eval_ queries, which
ask an agent how much they value a given piece of cake, and _Cut_ queries, in
which an agent specifies where a piece of cake should be cut to be worth a
certain value, and the moving-knives model (see, for example, Dubins &
Spanier, [8]), in which a referee continuously moves one or more knives across
the cake until one of the agents calls “stop”.

More recently, Brânzei et al. , [5, 6] introduced a new model for cake-cutting
protocols, _generalised cut and choose_ (GCC) protocols, in which rather than
reporting their preferences to a referee, the agents divide the cake amongst
themselves. In the GCC model, a protocol is represented as a tree with _cut_
nodes, in which an agent makes a cut inside one of a set of pre-existing
pieces of cake, _choose_ nodes, in which an agent chooses from a set of
existing pieces and is allocated that piece, and _if-else statements_
depending on the execution history of the protocol.

In this paper, we propose an alternative model for representing cake-cutting
protocols as trees, _branch choice_ (BC) protocols: at _cut_ nodes, an agent
makes a cut inside a given piece of cake, similarly to GCC protocols, but at
_choose_ nodes, an agent instead gets to choose which branch of the tree to
proceed to. The resulting pieces are allocated to various agents at leaf
nodes. Having such a simple, restrictive model is an advantage when it comes
to automation, since making the different possible choices and their outcomes
more explicit would make it easier for AI agents to participate in a protocol.

We define various notions of equivalence between cake-cutting protocols, based
on the bounds on value/envy that an agent can guarantee for themselves in the
two protocols. We show that making various tweaks to the definition of BC
protocols (such as considering protocols that can be represented as directed
acyclic graphs rather than trees, or allowing agents to make a cut within a
sequence of pieces rather than a single piece), results in the same class of
protocols, up to what we call _strong envy-equivalence_. (Informally, an agent
can guarantee the same bounds on their envy against the other agents in both
protocols.)

We then prove that any BC protocol can be put into a special form in which all
the cut nodes come before the choose nodes, making it easier to reason about
the structure of the protocol. Finally, we show that in fact BC protocols have
the same expressive power as GCC protocols, and we look into how some classic
cake-cutting protocols can be represented as BC protocols.

###  1.1 Related Work

The Robertson-Webb query model, first introduced by Robertson & Webb, [11] and
formalised by Woeginger & Sgall, [14], which is the standard model for
discrete cake-cutting protocols in the literature, involves a referee who can
ask the agents two types of queries related to their valuation functions (see
Introduction), and divides the cake accordingly. A natural question is whether
there is an incentive for the agents to report their valuation functions
truthfully, i.e. whether there exist any strategy-proof protocols in the
Robertson-Webb model. Here, strategy-proofness means truthful reporting is a
dominant strategy for every agent, regardless of their valuation function.

Brânzei & Miltersen, [4] show this is impossible for any “interesting”
protocols in the Robertson-Webb model: any strategy-proof protocol for two
agents is dictatorial (there is a fixed agent who always gets the entire
cake), and, more generally, in any strategy-proof protocol for $n$ agents, at
least one agent gets an empty piece. There are some other papers that deal
with strategy-proofness and the closely related concept of truthfulness.

Notably, Chen et al. , [7] design a cake-cutting protocol that is truthful,
proportional, and envy-free for piecewise-uniform valuation functions, but
which uses a direct-revelation mechanism (i.e. the agents reveal their entire
valuation function to the referee), rather than the standard query model. A
recent paper by Tao, [13] proves that no such protocol can exist for the more
general case of strictly positive piecewise-constant valuations, and designs a
mechanism that satisfies a weaker notion of truthfulness.

Brânzei et al. , [5, 6] introduce the GCC protocols model described above, and
use it as a framework to design a protocol for which a contiguous allocation
is envy-free if and only if it is the outcome of a Nash equilibrium.

The BC protocols model introduced in this paper is different from the GCC
model in that instead of having agents choose which pieces of the cake they
receive, they choose which branch of the protocol to proceed to. In addition,
the agents’ actions are more restrictive, so that the ordering of the cuts is
encoded in the tree structure, which eliminates the need for if-else
statements.

Furthermore, our work does not focus on game-theoretic aspects like strategy-
proofness, though this would be an interesting topic to address in the future,
but rather on results related to the expressive power of the model, which is a
topic that Brânzei et al. , [5, 6] only touch on briefly, and considerations
such as the space complexity of implementing common protocols in this format.

For a readable introduction to the better-known cake-cutting protocols,
including algorithmic and strategic issues, see Procaccia, [10].

##  2 Background

###  2.1 Setting

The cake, which is represented as the interval $[0,1]$, must be divided
between $n$ _agents_. Each agent must be allocated a _piece of cake_ (i.e. a
finite union of disjoint intervals). The pieces of cake allocated to different
agents must be disjoint. We allow for an individual agent to be given no cake
(or an empty piece $[x,x]$), but every piece of cake must be allocated to some
agent.

The agents’ preferences are given by _private valuation functions_
$V_{1},V_{2},...,V_{n}$ that assign a value $V_{i}(a,b)$ to every subinterval
$[a,b]\subseteq[0,1]$. We extend the $V_{i}$ additively to pieces of cake,
writing $V_{i}(X)$ for the value of a piece of cake X. The valuation functions
are assumed to have the following properties:

  * •

_Normalization:_ $V_{i}(0,1)=1$

  * •

_Additivity:_ For any two disjoint intervals $I_{1}$ and $I_{2}$,
$V_{i}(I_{1}\cup I_{2})=V_{i}(I_{1})+V_{i}(I_{2})$

  * •

_Divisibility:_ For every interval $[a,b]\subseteq[0,1]$ and $0\leq\lambda\leq
1$ there exists $c\in[a,b]$ such that $V_{i}(a,c)=\lambda V_{i}(a,b)$. In
particular, this implies the valuation functions are _non-atomic_ :
$V_{i}(a,a)=0$ for every $a\in[0,1]$.

  * •

_Non-negativity:_ $V_{i}(a,b)\geq 0$ for any $a,b\in[0,1]$.

For an allocation $A=(X_{1},...,X_{n})$, where $X_{i}$ is the piece of cake
assigned to agent $i$, we define the _envy_ of agent $i$ towards agent $j$ as:

$envy_{A}(i,j)=\max(V_{i}(X_{j})-V_{i}(X_{i}),0)$

###  2.2 Generalised Cut and Choose (GCC) Protocols

A _generalised cut and choose (GCC) protocol_ [5, 6], is represented as a tree
in which each node corresponds to the action of an agent. There are three
types of nodes:

  * •

_cut_ nodes: an agent makes a cut between two existing cuts. More
specifically, agent $i$ is given a set
$S=\\{[x_{1},y_{1}],...,[x_{m},y_{m}]\\}$ of intervals representing contiguous
piece of cake, such that the endpoints of every piece are either 0,1, or cuts
made at a previous step. The agent picks an interval $[x_{j},y_{j}]$ and makes
a cut at some point $z$ in it.

  * •

_choose_ nodes: an agent chooses between a set of pieces induced by the
existing cuts. Agent $i$ is given a set $S$ as above. They choose an interval
$[x_{j},y_{j}]$ from $S$, and this interval then gets allocated to them. In
the special case $|S|=1$, the agent is essentially assigned a piece and there
is no actual “choice”.

  * •

_if-else_ nodes: These nodes can have multiple branches. The protocol
progresses to one of the branches based on an if-else statement. The
conditions in the if-else statement depend on the order of the cut points made
in the previous steps, and the execution history of the protocol
(Equivalently, the conditions depend on which pieces the agents cut or chose
at each of the previous steps).

Note that cut and choose nodes have at most one child each, so the protocol
only branches out at if-else nodes.

In the original paper by Brânzei et al. , [5], the if-else statements are not
explicitly included in the tree structure. Instead, the cut/choose nodes have
multiple children and progression to one of the children is based on an if-
else statement. We view if-else statements as separate nodes for simplicity.
It is easy to see that our interpretation and the original one have the same
expressive power.

Algorithm 1 shows how the Selfridge-Conway protocol [11], a classic envy-free
protocol for three agents, can be represented as a GCC protocol. Algorithm 2
shows the original protocol, for comparison.

1 CUT: Agent $1$ cuts in $[0,1]$ at point $x_{0}$.

2CUT: Agent $1$ cuts in $[x_{0},1]$ at point $x_{1}$.

3CUT: Agent $2$ cuts a piece from $\\{[0,x_{0}],[x_{0},x_{1}],[x_{1},1]\\}$
Label this piece $A$, dividing it into pieces $A_{1}$ and $A_{2}$. Let the
other two pieces be $B$ and $C$. CHOOSE: Agent $3$ chooses a piece from
$S=\\{A_{1},B,C\\}$.

4if  _Agent $3$ chose $A_{1}$_ then

5 CHOOSE: Agent $2$ chooses a piece from $S=\\{B,C\\}$.

6 CHOOSE: Agent $1$ chooses the last remaining piece in $S$.

7 CUT: Agent 2 cuts $A_{2}$ at $\frac{1}{3}$ of the value, resulting in two
pieces $A_{21}$, $A_{2}^{\prime}$.

8 CUT: Agent 2 cuts $A_{2}^{\prime}$ at $\frac{1}{2}$, resulting in two pieces
$A_{22}$, $A_{23}$.

9 CHOOSE: Agent 3 chooses a piece out of
$S^{\prime}=\\{A_{21},A_{22},A_{23}\\}$, WLOG $A_{21}$.

10 CHOOSE: Agent $1$ chooses a piece out of $\\{A_{22},A_{23}\\}$.

11 CHOOSE: Agent $2$ chooses the remaining piece.

12else

// Agent $3$ did not choose $A_{1}$

13 CHOOSE: Agent $2$ gets piece $A_{1}$.

14 CHOOSE: Agent $1$ chooses the last remaining piece in S.

15 CUT: Agent 3 cuts $A_{2}$ at $\frac{1}{3}$ of the value, resulting in two
pieces $A_{21}$, $A_{2}^{\prime}$.

16 CUT: Agent 3 cuts $A_{2}^{\prime}$ at $\frac{1}{2}$, resulting in two
pieces $A_{22}$, $A_{23}$.

17 CHOOSE: Agent 2 chooses a piece out of
$S^{\prime}=\\{A_{21},A_{22},A_{23}\\}$, WLOG $A_{21}$.

18 CHOOSE: Agent $1$ chooses a piece out of $\\{A_{22},A_{23}\\}$.

19 CHOOSE: Agent 3 chooses the remaining piece.

Algorithm 1 The Selfridge-Conway protocol, represented as a GCC protocol.
Strictly speaking, wherever the algorithm labels a piece or assumes w.l.o.g.
that a certain piece was chosen, we should have an if-else node with multiple
branches depending on which piece that is, but we have mostly omitted those
for simplicity.

1 Agent $1$ divides the cake into three pieces of value $\frac{1}{3}.$

2Let $A$ be the largest piece according to agent $2$. Let the other two pieces
be $B$ and $C$.

3Agent $2$ trims $A$ so that it is the same size as the second largest piece.
Label the trimmed piece $A_{1}$, and the trimmings $A_{2}$.

4Agent $3$ chooses a piece from $\\{A_{1},B,C\\}$.

5if  _Agent $3$ chose $A_{1}$_ then

6 Agent $2$ chooses one of $B$ and $C$.

7else

// Agent $3$ did not choose $A_{1}$

8 Agent $2$ gets piece $A_{1}$.

9Agent $1$ gets the last piece. It remains to divide the trimmings $A_{2}$.

10One of agents $2$ and $3$ got $A_{1}$. Call that agent $X$, and the other
agent $Y$.

11Agent $Y$ cuts $A_{2}$ into three equal pieces.

12Agent $X$ chooses one of the three pieces.

13Agent $1$ chooses one of the remaining two pieces.

Agent $Y$ gets the last remaining piece.

Algorithm 2 The Selfridge-Conway protocol.

###  2.3 Equivalence of Cake-Cutting Protocols

Since we are working with multiple models for representing cake-cutting
protocols, we need to define what it means for two protocols (possibly
represented in different models) to be “the same”. We will present multiple
possible notions of equivalence between cake-cutting protocols, which are all
based on various bounds agents can guarantee for themselves in terms of
value/envy, regardless of the other agents’ strategies, so they are
independent of the model used to represent a protocol.

Let $\mathcal{P}$ and $\mathcal{P^{\prime}}$ be two cake-cutting protocols.

  1. 1.

Value equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are equivalent if
the minimum value that each agent can guarantee for themselves is the same.
That is, if in the worst case for protocol $\mathcal{P}$ agent $i$ gets a
piece of value $\lambda$, then in the worst case for protocol
$\mathcal{P^{\prime}}$ the piece agent $i$ gets must have the same value
$\lambda$.

  2. 2.

Total envy equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are
equivalent if the maximum total amount of envy $\sum_{j=1,j\neq
i}^{n}envy(i,j)$ an agent can guarantee for themselves is the same in both
protocols.

  3. 3.

Pair-wise envy equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are
equivalent if, for any two agents $i$ and $j$, if in one of the protocols
agent $i$ can guarantee $envy(i,j)\leq M$, for some $M\in[0,1]$, then they can
guarantee the same bound holds in the other protocol.

  4. 4.

Strong envy equivalence: $\mathcal{P}$ and $\mathcal{P^{\prime}}$ are
equivalent if, for any agent $i$ and any set $S$ of agents not containing $i$,
if in one of the protocols agent $i$ can guarantee simultaneous bounds
$envy(i,j)\leq M_{j},\forall j\in S$, for some $M_{j}\in[0,1]$, then they can
guarantee the same bounds hold in the other protocol. This is the notion of
equivalence we will be using the most throughout the paper. Note this is still
quite broad, since, in particular, any two envy-free protocols will be
strongly envy-equivalent. A lot of our results involve protocols that appear
“similar” in a stronger sense (for example, some of our conversion algorithms
involve mimicking the actions in a given protocol in a different model), but
this is difficult to formalise and since, in practice, most protocols aim to
guarantee certain bounds on envy, our definition is good enough.

Note also that strong envy equivalence implies pair-wise envy equivalence
(taking $S=\\{j\\}$).

##  3 An Alternate Model for Cake-Cutting Protocols

In Section 3.1 we define the class of Branch Choice (BC) protocols. In
Sections 3.2 and 3.3 we consider variations of the definition, and we prove
that they are equivalent to the original one. In Section 3.4 we show that no
expressive power is lost in moving to a restricted version in which the “cut”
nodes must precede the “choose” nodes. In Section 3.5 we show that BC
protocols have the same expressive power as GC protocols. In Section 3.6 we
show that certain proportional protocols can be expressed as BC (equivalently
GCC) protocols.

###  3.1 Branch Choice (BC) Protocols

Consider the following alternative representation of cake-cutting protocols.
As before, we represent the protocols as trees, but this time we divide the
nodes into:

  * •

non-leaf nodes, which are further divided into:

    * –

_cut_ nodes: We have a partition of the cake into $m$ contiguous pieces,
ordered from left to right. Agent $i$ subdivides a piece $j$ by making one
cut. Trivial cuts (i.e. cutting at one of the ends of the piece) are allowed.
For convenience, we consider that for a piece $[x,y]$, cutting at one of the
ends, WLOG $x$, divides it into $[x,y]$ and a new piece $[x,x]$. Such “empty”
pieces will have value $0$ to any agent, but they allow us to keep track of
the number of pieces throughout the tree. Note $i$ and $j$ are both fixed,
unlike in the previous section.

    * –

_choose_ nodes: Given a partition of the cake as above, agent $i$ is allowed
to choose which child of the current node to proceed to, based on the position
of the cuts.

  * •

leaf nodes: Given a partition of the cake, each piece in the partition is
allocated to an agent. The allocation is represented as a mapping
$\\{1,...,m\\}\rightarrow\\{1,...,n\\}$ where $n$ is the number of agents, and
$m$ is the number of pieces in the partition. Note that for a given leaf, the
number $m$ of pieces the cake has been divided into by the time we reach that
leaf is one plus the number of cut nodes above the leaf, which does not depend
on the execution history, so the mapping is well-defined.

We say a cut/choose node corresponding to an action of agent $i$ is
_controlled by agent_ $i$.

We will refer to the class of protocols that can be represented in the above
form as _branch choice (BC) protocols_ to reflect the fact that at choose
nodes, an agent chooses which branch of the tree is executed.

Note we need to keep track of the execution history at every node (i.e. how
the cake is partitioned before the action corresponding to the current node).
We can either store this information at every node (requiring extra space), or
recover it from the unique path between the current node and the root (no
extra space). Both take linear time in the number of nodes to read, so we will
use the latter option and store no extra information at the nodes.

CUT: agent $1$ cuts into $[0,1]$ at point $x_{0}$CUT: agent $1$ cuts into
$[x_{0},1]$ at $x_{1}$*CHOOSE: agent $2$ chooses a branchCUT: ag. $2$ cuts
into $[0,x_{0}]$ at $y$CUT:ag. $2$ cuts into $[x_{0},x_{1}]$ at $y$…CUT:ag.
$2$ cuts into $[x_{1},1]$ at $y$…**CHOOSE: ag. $3$ chooses a branch……CUT: ag.
$2$ cuts into $[y,x_{0}]$ at $y_{1}$CUT: ag. $2$ cuts into $[y_{1},x_{0}]$ at
$y_{2}$***CHOOSE: ag. $2$ chooses a branch****CHOOSE: ag. $3$ chooses a
branch………*****CHOOSE: ag. $1$ chooses a branchALLOCATION:$[0,y]\mapsto
3$$[x_{0},x_{1}]\mapsto 2$$[x_{1},1]\mapsto 1$$[y,y_{1}]\mapsto
3$$[y_{1},y_{2}]\mapsto 1$$[y_{2},x_{0}]\mapsto 2$ALLOCATION:$[0,y]\mapsto
3$$[x_{0},x_{1}]\mapsto 2$$[x_{1},1]\mapsto 1$$[y,y_{1}]\mapsto
3$$[y_{1},y_{2}]\mapsto 2$$[y_{2},x_{0}]\mapsto 1$

Figure 1: (Partial) tree representation of a BC protocol that is strongly
envy-equivalent to the Selfridge-Conway protocol (i.e. it is envy-free). The
omitted subtrees, represented by “…”, are essentially copies of the one shown,
for some permutation of the pieces/agents. The complete tree would have $150$
nodes in total. See detailed explanation below.

In figure 1:

* \- agent $2$ trims the largest piece according to them (as per the original protocol). In our representation of the protocol, they have to choose the largest piece to minimise their envy.

** \- agent $3$ chooses which of the three “big” pieces $[0,y],[x_{0},x_{1}]$
and $[x_{1},1]$ they get.

*** \- agent $2$ chooses which of the remaining two “big” pieces they get. In
the two branches we have left out, where agent $1$ hasn’t chosen $[0,y]$,
agent $2$ is assigned $[0,y]$ by default and does not get a choice here.

****, ***** \- agents $3$ and $1$ choose which of the “trimmings” they are
assigned.

It can be shown that all other conditions in the original protocol (e.g. agent
$1$ cutting the piece into thirds at the beginning, agent $2$ trimming the
largest piece to be the same size as the second largest, etc.) can be
recovered by analysing where the agents need to cut to minimise their envy.

###  3.2 BC Protocols Represented as Directed Acyclic Graphs

As a generalisation, we can instead consider the class of cake-cutting
protocols that can be represented as _directed acyclic graphs_ (DAGs) using
the same types of nodes as BC protocols.

A DAG representing a cake-cutting protocol will have a designated _root_ node
that corresponds to the first action in the protocol. We will also assume that
every node is reachable from the root, as nodes that are not reachable will
not be relevant to the protocol. To ensure the DAG represents a valid
protocol, we must also require that if there are multiple paths from the root
to a node, all of them result in the same number of cuts, so that the number
of pre-existing cuts at a given node is well-defined and we can describe
actions like “agent $i$ cuts into the $j$-th piece”. This can provide a more
compact representation for certain protocols, but we will see that it is no
more “powerful” than the tree representation, that is, given a DAG
representing some protocol, we can represent the same protocol as a tree.

######  Theorem 1.

The protocols that can be represented as DAGs are exactly the BC protocols as
defined above.

###### Proof.

Clearly any BC protocol can be represented as a DAG by converting every edge
in the tree representation to a directed parent $\rightarrow$ child edge.

Conversely, let $G$ be a DAG representing a cake-cutting protocol. We will
produce a tree representation of the same protocol. The root and nodes with a
single parent can be translated directly into the tree. For nodes with
multiple parents, the key idea is to make one copy of the node and its
descendants for each parent. Every path from the root to the node in the
initial graph $G$ corresponds to a path from the root to one of the copies of
the node in the resulting graph. Therefore the new graph represents the same
protocol. By repeating this step until there are no more nodes with multiple
parents, we will obtain a tree representation of the protocol.

This algorithm will always terminate, but to eliminate repeated work we want
to ensure that a node’s descendants are converted to tree nodes before the
node itself (otherwise we might have to run the process multiple times for
copies of the same descendant). We can do this by finding a topological
ordering of the tree, and then converting the nodes in reverse topological
order.

Therefore, any protocol represented as a DAG can also be represented as a
tree, so the protocols that can be represented as DAGs are precisely the BC
protocols. ∎

###  3.3 Extended BC Protocols

We will now consider a modified definition of BC protocols, which allows an
agent to choose which piece of cake to cut from a sequence of consecutive
pieces, and allows for allocating a sequence of pieces to some agent at once
by only specifying the endpoints of the sequence.

The advantage of this more flexible definition is that we can ignore some
extraneous cuts in the execution of the protocol, as we will see, for example,
in the proof of theorem 4. We will show that, in fact, this extended
definition has the same expressive power as the original one.

  * •

Instead of having some agent $i$ cut into a single piece $[x,y]$ with no other
cuts inside it, we allow for _cut_ nodes that ask agent $i$ to make a cut
between two existing cuts $x$ and $y$ (which might not be consecutive).

  * •

At _leaves_ , instead of allocating each interval, we allow for allocating the
piece of cake between two (potentially non-consecutive) cuts $x$ and $y$ to
some agent, with the constraint that $x<y$ (so if the ordering of $x$ and $y$
cannot be determined solely from the structure of the protocol, and depends on
the decisions of the agents, this is not a valid allocation). Note this is
essentially the same as BC protocol allocation, except the allocation can be
written more concisely, ignoring intermediate cuts if consecutive intervals
are allocated to the same agent.

######  Example.

If agent $1$ makes a cut at $x\in[0,1]$ and agent $2$ then makes a cut at
$y\in[0,1]$, we cannot have an allocation $[0,x]\mapsto 1$, $[x,y]\mapsto 2$,
$[y,1]\mapsto 1$, because it might be the case that $y<x$. But if instead we
restrict the second cut to $y\in[x,1]$, the allocation is valid. In both
cases, $[0,x]\mapsto 1$, $[x,1]\mapsto 2$ is also a valid allocation.

We will refer to protocols covered by this definition as _extended BC
protocols_. Note that indeed any protocol covered by the original definition
of BC protocols is covered by the modified definition, with no changes needed.

######  Theorem 2.

For any extended BC protocol, we can construct a strongly envy-equivalent BC
protocol. This results in a $\Theta(n!)$ blowup in the size of the tree
representation of the protocol.

###### Proof.

Construction: We convert the cut nodes in topological order, so when we reach
a node, we know that all of its descendants are already “valid” nodes in the
original definition. For a cut node “agent $i$ cuts between $x$ and $y$”,
suppose there are $n$ other cuts $x_{1},...,x_{n}$ between $x$ and $y$. Note
$n$ is fixed, because we have already converted all of the current node’s
descendants, so we know the ordering of the pre-existing cuts at this stage.
We replace our cut node with a choose node with $n$ cut node children,
corresponding to cutting in $[x,x_{1}],[x_{1},x_{2}],...,[x_{n},y]$,
respectively. Each child will have a copy of the initial cut node’s subtree.

We also need to modify the leaf nodes. After modifying the cut nodes, the
ordering of the cuts at each leaf node is now fixed, so we can replace an
allocation $[x,y]\mapsto j$ with one that allocates each continuous piece
between $x$ and $y$ to agent $j$.

Complexity analysis: This conversion process terminates, but it results in an
$\Theta(n!)$ blowup in the size of the tree (where n is the initial number of
nodes). Consequently, the running time is also $\Theta(n!)$.

To see this, consider the worst case, in which we have a chain of $n$ cut
nodes that are all of the form “agent $j$ cuts in $[0,1]$ at $x_{i}$”, with
$1\leq i\leq n$).

For the first cut node we don’t have to do anything. For the second cut node,
we replace it with a choose node with $2$ branches corresponding to cuts in
$[0,x_{0}]$ and $[x_{0},1]$, respectively.

In each of these two branches, there will be a copy of the third cut node,
which needs to be replaced with a choose node with $3$ branches, etc.

See figures 2 and 3 for an example.

CUT: agent $1$ cuts $[0,1]$ at $x$CUT: agent $2$ cuts $[0,1]$ at $y$CUT: agent
$3$ cuts $[0,1]$ at $z$

Figure 2: Worst-case for n=3, before conversion.

CUT: agent $1$ cuts into $[0,1]$ at $x$CHOOSE: agent $2$ chooses a branchCUT:
agent $2$ cuts into $[0,x]$ at $y$CUT: agent $2$ cuts into $[x,1]$ at
$y$CHOOSE: agent $3$ chooses a branchCHOOSE: agent $3$ chooses a
branchCUT:agent $3$ cuts into $[0,y]$ at $z$CUT:agent $3$ cuts into $[y,x]$ at
$z$CUT:agent $3$ cuts into $[x,1]$ at $z$CUT:agent $3$ cuts into $[0,x]$ at
$z$CUT:agent $3$ cuts into $[x,y]$ at $z$CUT:agent $3$ cuts into $[y,1]$ at
$z$

Figure 3: Worst-case for n=3, after conversion.

∎

######  Corollary 3.

BC protocols and extended BC protocols represent the same class of protocols,
up to strong envy-equivalence.

###  3.4 Converting BC Protocols to “Cuts Before Choices” Form

In this section, we will prove that any BC protocol can be converted to a
“nice” form in which all the cut nodes come before all the choose nodes, so,
intuitively, the agents first cut up the cake, and then they make choices
between branches leading to various allocations.

######  Theorem 4.

Any extended BC protocol can be converted into a strongly envy-equivalent
extended BC protocol in which no choose node in the tree representation of the
protocol has a cut node descendant. The conversion algorithm runs in
polynomial time, and the size (number of nodes) of the original tree is equal
to the size of the resulting tree.

###### Proof.

Let $\mathcal{P}$ be a cake-cutting protocol. If the protocol already
satisfies the required condition, we are done. Otherwise, suppose the extended
BC tree representation of $\mathcal{P}$ contains a choose node with a cut node
descendant. In particular, there must be a choose node with a cut node child
“agent $i^{\prime}$ cuts between $x_{k}$ and $x_{k+1}$ at point $y$”.

We will describe an algorithm to move the cut node above the choose node (as
in figures 4 and 5) without affecting the resulting allocation (each agent
will be assigned the same piece of cake as in the initial protocol, except
potentially cut up differently). The advantage of this form is that it makes
it easier to reason about the protocol.

CHOOSE:agent $i$ chooses a branchCUT:agent $i^{\prime}$ cuts between $x_{k}$
and $x_{k+1}$ at point $y$…$V$…

Figure 4: Choose node with cut node child.

CHOOSE: agent $i$ chooses a branchCUT: agent $i^{\prime}$ cuts between $x_{k}$
and $x_{k+1}$ at point $y$…$V$…

Figure 5: Subtree obtained by moving the cut node above the choose node in 4.

Note the cut node only has one child, call it $V$, which can be any kind of
node. Moving the cut node above the choose node will not affect the
subprotocol defined by $V$’s branch. In the other branches, we just ignore the
cut at $y$ (which extended BC protocols allow) and execute the protocol
exactly as before.

We repeat this process until there is no choose node with a cut node child.
This protocol will contain no choose node with a cut node descendant. Since
the conversion algorithm does not affect the allocation, any simultaneous
bounds on an agent’s envy towards other agents in the initial protocol will
carry over to the resulting protocol, so the two are strongly envy-equivalent.

Furthermore, the running time of the conversion algorithm is polynomial (we
move each cut node up the tree at most $n$ times, where $n$ is the total
number of nodes, and there are at most $n$ cut nodes).

Since no nodes are added and deleted, the size of the resulting tree is equal
to the size of the original tree. ∎

######  Lemma 5.

Any BC protocol can be converted into a strongly envy-equivalent BC protocol
in which every choose node either has:

  * •

no cut node descendants, or

  * •

only cut node children, in which case if the choose node is controlled by
agent $i$, the cut node children are guaranteed to be controlled by agent $i$
and correspond to cuts in a sequence of consecutive pieces.

The conversion results in a $\Theta(n!)$ blowup in the size of the tree
representation.

###### Proof.

Let $\mathcal{P}$ be a BC protocol. In particular, $\mathcal{P}$ can be viewed
as an extended BC protocol, so by theorem 4 we can convert it to a strongly
envy-equivalent “cuts before choices” extended BC protocol
$\mathcal{P}^{\prime}$ in which no choose node in the tree representation of
the protocol has a cut node descendant, resulting in a tree similar to the one
in the figure below.

CUT: agent $1$ cuts $[0,1]$ at $x_{1}$CUT: agent $2$ cuts $[0,1]$ at
$x_{2}$…CUT: agent $i$ cuts $[0,1]$ at $x_{i}$CHOOSE: agent $1$ chooses a
branch

We can then convert $\mathcal{P}^{\prime}$ back to a BC protocol using the
algorithm in theorem 2.

In the last conversion, a cut node “agent $i$ cuts between $x_{0}$ and
$x_{n}$” in $\mathcal{P}^{\prime}$ will either be unchanged, if there are no
other cuts between $x_{0}$ and $x_{n}$, or it will be split into a choose node
“agent $i$ chooses a branch” with $n$ cut node children “agent $i$ cuts
between $x_{j}$ and $x_{j+1}$” corresponding to each of the intermediate
pieces (where $x_{1},...,x_{n-1}$ are all the existing cuts between $x_{0}$
and $x_{n}$, from left to right).

The choose nodes in $\mathcal{P^{\prime}}$ will not be changed/moved, so they
will still have no cut node descendants after the conversion.

Therefore the resulting protocol has the required form, and is strongly envy-
equivalent to the original protocol $\mathcal{P}$. The $\Theta(n!)$ blowup in
size comes from the last conversion. ∎

######  Theorem 6.

Any BC protocol can be converted into a strongly envy-equivalent BC protocol
in which no choose node in the tree representation of the protocol has a cut
node descendant.

###### Proof.

Let $\mathcal{P}$ be a BC protocol.

We start by converting $\mathcal{P}$ to the form in lemma 5. The resulting
tree will look like in figure 6: a chain of $m-1$ cut nodes, followed by a
choose node with $\leq m$ branches, then a level with $\leq m$ cut nodes, one
in each branch, then $\leq m$ choose nodes each with $\leq m+1$ branches,
etc., until the last level of cut nodes (whose choose node parents will each
have $\leq m+k$ branches, where $k$ is the number of levels of cut nodes).
Below that level, the tree only contains choose nodes and allocation nodes.

CUT at $x_{1}\in[0,1]$CUT at $x_{2}\in[x_{1},1]$…CUT at
$x_{m-1}\in[x_{m-2},1]$$m-1$ cut nodesCHOOSE: agent i chooses a branch ($\leq
m$ branches). . .CUT: agent $i$ cuts at $y_{0}\in[0,x_{1}]$CUT: agent $i$ cuts
at $y_{m}\in[x_{m-1},1]$CHOOSE: agent $j$ chooses ($\leq m+1$ branches)CHOOSE:
agent $j$ chooses ($\leq m+1$ branches)CUT:agent $j$ cuts at
$z_{0}\in[0,y_{0}]$CUT:agent $j$ cuts at $z_{1}\in[y_{0},x_{1}]$CUT:agent $j$
cuts at $z_{m}\in[x_{m-1},1]$. . .CUT:agent $j$ cuts at
$z_{0}^{\prime}\in[0,x_{1}]$. . .CUT:agent $j$ cuts at
$z_{m-1}^{\prime}\in[x_{m-1},y_{m}]$CUT:agent $j$ cuts at
$z_{m}^{\prime}\in[y_{m},1]$

Figure 6: Protocol in the form in lemma 5.

We can assume that we are in the case where we always have the maximum number
of branches at each choose node, i.e. all the “$\leq$” signs above are
equalities. In particular, that means that at a choose node with cut node
children, we will have one cut node corresponding to each contiguous piece of
cake, so if there are $n$ cuts $x_{1}...,x_{n}$ when we reach the choose node,
it will have cut node children corresponding to cuts into
$[0,x_{1}],[x_{1},x_{2}]...$ up to $[x_{n},1]$.

We can make this assumption because if we want to restrict the cut to the
interval $[x_{i},x_{j}]$, we can just remove the branches corresponding to
making a cut outside of that interval at the end of the protocol.

We now aim to convert this protocol to one where no choose node has a cut node
descendant, by moving cut node children above their choose node parent one by
one, as in figures 4 and 5.

The difficulty here is that unlike with extended BC protocols in theorem 4,
when we move a cut node above its choose node parent, we need to modify the
other branches of the choose node to account for the extra cut, so that the
resulting protocol is still a BC protocol.

Suppose there are $k$ levels of cut nodes below the topmost choose node.

If $k=0$, there are no cut nodes below the topmost choose node, so we are
done.

For $k>0$, we start with the topmost level of cut nodes, which will be the
children of the topmost choose node. There are $m$ cut nodes “agent $i$ cuts
at $y_{j}$ into $[x_{j},x_{j+1}]$”, $j\in\\{0,...,m\\}$, where
$x_{0}=0,x_{m}=1$.

We start by moving the leftmost cut node, “agent $i$ cuts at
$y_{0}\in[0,x_{1}]$”, above its parent. We do not need to modify the branch
that cut node was in, but for the other $m-1$ branches, we need to do the
following in each branch:

  * •

the topmost cut node is unchanged;

  * •

on the second level of cut nodes, we need to split the cut node “agent $j$
cuts at $z_{0}^{\prime}\in[0,x_{1}]$” into two cut nodes corresponding to cuts
in $[0,y_{0}]$ and $[y_{0},x_{1}]$.

  * •

on the following level, we need to split exactly one cut node in each of the
$m+2$ branches to account for the extra cut at $y_{0}$, etc.

In total, this will add $0$ cut nodes on the first level, $m-1$ on the second
level, $(m-1)(m+1)$ on the second level,…, $(m-1)(m+1)(m+2)...(m+k)$ on the
$k$-th (last) level. In particular, the process terminates.

We repeat this process for the other $m-1$ cut nodes on the first level. At
the end, the tree will look like in figure 7, and there will be $k-1$ levels
of cut nodes below the top choose node.

CUTCUT…CUT$2m-1$ cut nodesCHOOSE: agent i chooses a branch ($m$ branches). .
.CHOOSE: agent $j$ chooses ($2m+1$ branches)CHOOSE: agent $j$ chooses ($2m+1$
branches)CUT:agent $j$ cuts …CUT:agent $j$ cuts …CUT:agent $j$ cuts …. .
.CUT:agent $j$ cuts …. . .CUT:agent $j$ cuts …CUT:agent $j$ cuts …

Figure 7: Protocol after moving first level of cut nodes above choose node.

Now, each of the $m$ choose nodes below the top choose node have $2m+1$ cut
node children. Starting from the leftmost of these choose nodes and its left
most cut node child, we move the child above the parent, and then move it
above the top choose node. We repeat this process until we have moved all
$m(2m+1)$ cut nodes on this level above the top choose node.

Now there are $k-2$ levels of cut nodes below the top choose node.
Recursively, we can move the cut nodes on each level above the top choose
node. Since the number of levels decreases at each step, and the process for a
single level terminates, the whole conversion process terminates.

At the end, we also need to “fix” the allocation nodes to account for the
extra cuts, by changing an allocation $[x,y]\rightarrow j$ to
$[x,x_{0}]\rightarrow j,...,[x_{N},y]\rightarrow j$, where $x_{0},...x_{N}$
are all the cuts between $x$ and $y$. This takes time $O(ac)$ where $a$ is the
number of allocation nodes and $c$ the number of cut nodes in the final tree.

The resulting protocol will have no cut nodes before the top choose node, so
clearly it will contain no choose node with a cut node descendant.

Note that pulling a cut node above its choose node parent and splitting cut
nodes in the other branches as above does not affect the allocation, hence the
protocols before and after each step are strongly envy-equivalent. Therefore
the original protocol and the final protocol are strongly envy-equivalent. ∎

###  3.5 Equivalence to GCC Protocols

In this section, we will prove that GCC and BC protocols can express the same
class of protocols, up to strong envy-equivalence.

######  Theorem 7.

For any GCC protocol, there is a strongly envy-equivalent BC protocol.

###### Proof.

We will refer to a tree representation of a GCC protocol as a _GCC-tree_ (with
GCC-cut, GCC-choose, and GCC-if-else nodes), and to a tree representation of a
BC protocol as _BC-tree_ (with BC-cut and BC-choose nodes, and BC-
leaves/allocation nodes).

Consider a protocol that can be represented as a GCC-tree T. We will construct
a BC-tree representation of it by replacing each node $v$ in T and its subtree
with an equivalent BC-subtree, in topological order. Before we start this
process, we connect a BC allocation node to each leaf of T (with the actual
allocation to be filled in later).

  * •

If $v$ is a GCC-cut node: At node $v$, agent $i$ chooses a piece from a set
$S$ and cuts into it. Since $S$ contains disjoint pieces, we can always extend
it to a partition of the cake $S^{\prime}$. We replace node $v$ with a BC-
choose node, with $|S|$ children, so there is one child for each piece $P\in
S$. The child corresponding to a piece $P$ will be a BC-cut node representing
the action “agent $i$ cuts into piece $P$”. The subtree of each child in the
BC-tree will be a copy of $v$’s subtree. In the BC-choose node, the agent can
choose which child to proceed to, so they effectively get a choice of which
piece from $S$ to cut into.

  * •

If $v$ is a GCC-choose node: At node $v$, agent $i$ chooses a piece from a set
$S$ and that piece gets assigned to them. Once again, we replace node $v$ with
a BC-choose node with $|S|$ children, one for each piece $P\in S$, and make
the subtree of each child a copy of $v$’s subtree. The agent will choose to
progress to the child corresponding to the piece they would have chosen in the
GCC protocol. We now need to ensure that piece $P$ actually gets assigned to
agent $i$ in the BC protocol. We add “agent $i$ gets piece $P$” to each BC-
leaf in the subtree corresponding to piece $P$. At the end of the conversion
process, each BC-leaf will contain a valid allocation of the entire cake.

  * •

If $v$ is a GCC-if-else node: By definition, the conditions in the if-else
statement at $v$ depend on which pieces the agents cut/chose at each of the
previous steps of the protocol. But since we have already converted all of
$v$’s ancestors to BC nodes, the decisions the agents made at each step before
the current node are already determined, so we know what the result of the if-
else statement will be and which branch the protocol will progress to. Hence,
we remove all the other branches, then delete the if-else node $v$ and connect
the single remaining branch to $v$’s parent.

Note that after we have converted every node $v$ in the GCC-tree, the tree
will only branch out at BC-choose nodes, and progression to a child will only
depend on the choice the agent makes at that node.

The protocol represented by the resulting BC-tree essentially simulates every
action in the initial protocol using BC-tree nodes. In particular, every agent
will get the same piece of cake they would have gotten in the initial
protocol. Therefore, any simultaneous bounds on their envy levels towards
other agents in the initial GCC protocol carry over to the BC protocol. Hence
the two protocols are strongly envy-equivalent. ∎

######  Remark 1.

The definition of choose/cut nodes in GCC protocols is ambiguous as to whether
the set $S$ of pieces of cake an agent is given is restricted to continuous
pieces (i.e. pieces $[x,y]$ such that there is no other cut between $x$ and
$y$), or we also allow for pieces that contain previous cuts.

Note that the above proof assumes the former, but the result also holds for
the more extensive definition, since, by a similar argument to the one in the
proof of theorem 2, if a piece $[x,y]$ contains cuts $x_{1},...,x_{n}$ we can
split it into $n+1$ pieces $[x,x_{1}],...,[x_{n},y]$ and add an if-else node
below to establish which of these $n+1$ pieces the agent acted on. This way,
we can convert a protocol in the more extensive definition to the restricted
one, and then convert it to a BC protocol via theorem 7.

######  Theorem 8.

For any BC protocol, there is a strongly envy-equivalent GCC protocol.

###### Proof.

We start by putting the BC protocol in the “cuts before choices” form given by
theorem 6.

The BC-cut nodes can then be trivially converted to GCC-cut nodes. The BC-
leaves can be converted to a chain of GCC-choose nodes (so if agent $i$ is
allocated some interval $[x,y]$ in the original node we make them “choose” the
piece $[x,y]$ instead. If agent $i$ gets multiple intervals, we will have one
GCC-choose node for each).

It remains to simulate the BC-choose nodes (in which an agent chooses which
branch of the tree to proceed to) using GCC nodes. We will do this by creating
a piece that has value $0$ for every agent, and then dividing that piece
between all $n$ agents. Each agent will then further divide their piece and
“choose” between various sub-pieces of it to artificially simulate branch
choices.

The actual protocol will be run on the remaining cake, which will be an
interval $[a_{n},1],a_{n}\geq 0$ such that $V_{i}([a_{n},1])=1$ for every $i$.
We can do this by replacing the endpoint $0$ with $a_{n}$ in every node of the
protocol. Clearly any envy bounds in the original protocol will hold in the
new protocol, since the piece $[0,a_{n}]$ that we cut off has no value for any
of the agents.

Explicitly, we add the following chain of cuts at the beginning of the
protocol:

  * •

agent $1$ cuts into $[0,1]$ at point $a_{1}$

  * •

agent $2$ cuts into $[0,a_{1}]$ at point $a_{2}$

…

  * •

agent $n$ cuts into $[0,a_{n-1}]$ at point $a_{n}$

The optimal strategy for agent $i$ is to cut at some $a_{i}$ such that
$V_{i}([0,a_{i}])=0$, so the piece $[0,a_{n}]$ will have value $0$ for all
agents, as required. This is because the agents cannot control how much of the
piece $[0,a_{n}]$ they get, so they want it to have as little value for them
as possible.

  * •

agent $1$ cuts into $[0,a_{n}]$ at point $b_{1}$

  * •

agent $2$ cuts into $[0,b_{1}]$ at point $b_{2}$

…

  * •

agent $n-1$ cuts into $[0,b_{n-2}]$ at point $b_{n-1}$

Now, agent $i$ will use the piece $[b_{i},b_{i-1}]$ (where
$b_{n}=0,b_{0}=a_{n}$) to simulate their BC-choose nodes as follows:

If there are $m$ BC-choose nodes controlled by agent $i$ in the tree, they cut
their piece $m-1$ times, dividing it into $m$ pieces. Each piece will
correspond to a choose node.

If the BC-choose node corresponding to the $j$-th piece has $k$ branches, we
replace it with the following process:

  * •

Agent $i$ divides the $j$-th piece into $k$ sub-pieces, one for each branch.

  * •

In a GCC-choose node, agent $i$ chooses one of the $k$ sub-pieces.

  * •

In a GCC-if-else node, we proceed to one of the $k$ branches, depending on
which piece the agent chose.

  * •

The agent gets the other $k-1$ pieces one by one (using a GCC choose node for
each one).

Note that not all of agent $i$’s $m$ BC-choose nodes might be reached in a
specific run of the protocol, since they might be in different branches. This
means that in some branches, the pieces corresponding to those choose nodes
will not have been allocated to anyone. To resolve this issue, agent $i$ gets
the remaining sub-pieces of $[b_{i},b_{i-1}]$ at the end.

This way, agent $i$ always gets the entire interval $[b_{i},b_{i-1}]$, so the
interval $[0,a_{n}]$ is all allocated to various agents.

Note there are some extra cuts in the cake at $a_{1},...,a_{n-1}$ that we have
ignored in the protocol. This is fine in the more extensive interpretation of
GCC protocols, and it can be converted to the more restrictive interpretation
by the Remark above.

The resulting protocol will be strongly envy-equivalent to the initial
protocol, since, as explained above, none of the steps in the conversion
process affect the envy bounds. ∎

######  Corollary 9.

If we allow for the more extensive interpretation of GCC protocols (as in
remark 1), any extended BC protocol can be converted to a strongly-envy
equivalent GCC protocol in polynomial time.

###### Proof.

Consider the conversion algorithm given in the proof of theorem 8. Apart from
converting the BC protocol to an equivalent BC protocol in “cuts before
choices” form at the start, and converting the resulting GCC protocol to fit
the more restrictive interpretation of the definition at the end, the rest of
the algorithm runs in polynomial time, since we only add a polynomial number
of nodes to the tree.

Therefore, if we use the more extensive interpretation of GCC protocols
instead, we can use theorem 4 to convert the original protocol to an extended
BC protocol in “cuts before choices” form in polynomial time, then run the
conversion algorithm as before. ∎

Note this argument does not work for the reverse conversion (GCC to BC) given
by theorem 7, because there we specifically make use of the more restrictive
classes of protocols when converting, for example, GCC if-else nodes.

###  3.6 Proportional Cake-Cutting Protocols

A cake-cutting protocol for $n$ agents is said to be proportional if each
agent is guaranteed to receive a piece of cake with value at least
$\frac{1}{n}$ according to their own valuation function. There are a number of
well-known proportional cake-cutting protocols, such as the Dubins-Spanier
protocol [8] and the Even-Paz protocol [9].

In this section, we look at how these can be represented as GCC and BC
protocols.

The discrete Dubins-Spanier protocol works as follows: each agent $i$ makes a
cut at a point $a_{i}$ such that $V_{i}([0,a_{i}])=\frac{1}{n}$. The agent who
made the leftmost cut $a_{j}$ gets the piece $[0,a_{j}]$. That agent is then
removed and we repeat the protocol on the remaining cake $[a_{j},1]$ with the
other $n-1$ agents. The last agent gets the remaining piece of cake.

Brânzei, [3] describes how the Dubins-Spanier protocol can be implemented as a
GCC protocol. Each agent is asked to make a cut in $[0,1]$ at some point
$a_{i}$. The leftmost cut $a_{j}$ is then determined using an If-Else node
with $n$ branches, then, in the $j$-th branch, agent $j$ “chooses” a piece
from the singleton set $\\{[0,a_{j}]\\}$, and we repeat the procedure for the
other $n-1$ agents on the remaining cake, ignoring the cuts made at previous
steps. This protocol clearly respects the proportionality condition, so, in
our language, it is value-equivalent to the original protocol. Any bounds on
envy from the original protocol would also clearly carry over, so they are
strongly envy-equivalent. Note that the size of the resulting GCC tree is
$\Theta(n!)$, because there are $n$ branches on the first if-else node, then
$n-1$ branches for each of those, etc. The runtime of the protocol is
$\Theta(n^{2})$ if we just count the queries/nodes, as in the original
protocol, and $\Theta(n^{3})$ if we also consider the comparisons inside each
if-else node, since to find the leftmost cut we need to compare the position
of each cut to the other $n-1$.

We can implement this as a BC protocol either by converting the GCC
implementation using theorem 7, or as an extended BC protocol as follows:
agent $1$ makes a cut in $[0,1]$ at $a_{1}$, agent $2$ chooses between two
branches (one for cutting in $[0,a_{1}]$ and the other one for $[a_{1},1]$),
the next agent chooses between two branches corresponding to cutting left or
right of the current leftmost node. After this, we know who made the leftmost
cut $a_{j}$ in a specific branch. At the end of the protocol agent $j$ will
get allocated the piece $[0,a_{j}]$. We repeat the algorithm for the other
$n-1$ agents on the remaining cake, ignoring the cuts made at previous steps.
There are $2^{n-1}$ branches in the first step, then for each of those there
are $2^{n-2}$ branches in the second step, etc. So the size of the tree is
$2^{n-1}2^{n-2}...2^{1}=2^{\frac{n(n-1)}{2}}$, so the size of the protocol is
$\Theta(2^{n^{2}})$.

The Even-Paz protocol for $n$ agents, is as follows:

  * •

Each agent makes a cut at $z_{i}\in[0,1]$ such that
$V_{i}([0,z_{i}])=\frac{1}{2}$.

  * •

The algorithm finds the $\lfloor\frac{n}{2}\rfloor$-th cut, which divides the
cake into two “halves”.

  * •

Each half is divided recursively amongst the agents whose cuts were inside
that half (with the agent who made the $\lfloor\frac{n}{2}\rfloor$-th cut
going into the first half).

The runtime is $\Theta(n\log(n))$.

We can implement the Even-Paz protocol as a GCC protocol as follows: each
agent makes a cut at $z_{i}\in[0,1]$, then in an if-else node with $n$
branches, we identify the $\lfloor\frac{n}{2}\rfloor$-th cut. We repeat the
procedure for each half for the $n/2$ agents who cut into that half. There are
$n$ branches in the first step, then in each of those we have $n/2$ branches
for dividing the first half, each of which then splits into $n/2$ branches for
dividing the second half, etc. Assuming $n=2^{k}$ for simplicity, the size of
the tree is
$n(\frac{n}{2})^{2}(\frac{n}{4})^{2}...=2^{k}2^{2(k-1)}2^{2(k-2)}...2^{2}=2^{k+2\frac{k(k-1)}{2}}=2^{k^{2}}$,
so $\Theta(2^{k^{2}})=\Theta(n^{\log(n)})$, and the resulting protocol is
value-equivalent (so, in particular, proportional) and strongly envy-
equivalent to the original one.

For the extended BC protocol implementation, agent $1$ makes a cut at $a_{1}$
in $[0,1]$, agent $2$ chooses between two branches (for cutting in $[0,a_{1}]$
or $[a_{1},1]$ respectively), agent $3$ chooses between three branches
(corresponding to cutting into each of the three existing pieces), etc. After
this, we know the ordering of the cuts in a specific branch, so, in
particular, the $\lfloor\frac{n}{2}\rfloor$-th cut. We recurse on the two
halves of the cake. Assuming $n=2^{k}$, we get $n!$ branches in the first
step, $((\frac{n}{2})!)^{2}=\Theta(n!)$ branches in the second step, etc, so
the size of the tree is $n!((\frac{n}{2})!)^{2}((\frac{n}{4})!)^{2}...$

##  4 Conclusions and Future Work

###  4.1 Conclusion

In this paper, we defined a new model for representing cake-cutting protocols
as trees, called branch choice (BC) protocols, which differs from other models
in that instead of choosing specific pieces of cake, the agents get to choose
which branch of the tree to proceed to at a certain point, and then the cake
is allocated at the end. We showed that various modifications to the model do
not impact its expressive power. We also proved that any BC protocol can be
converted to an equivalent protocol in which the cut nodes come before the
choose nodes, so that, informally, the agents can first cut up the cake, and
then choose between various branches that lead to different allocations.

The main benefit of BC protocols is that they form a rather bare-bones model,
so that, for example, if the protocol reaches a given node, we can deduce the
execution history of the protocol (the relative order of the cuts, as well as
which branches the agents chose) just based on the path from the root to that
node, with no ambiguity about what decisions the agents might have made at
previous nodes. This makes it easier to reason about the protocols,
particularly after putting them into the special “cuts before choices” form
mentioned above, since in that case we also know a lot about the structure of
the tree.

This comes at no cost to the expressive power of the model, since the class of
protocols it covers is the same as generalised cut and choose protocols as
described by Brânzei et al. , [5], up to strong envy equivalence (which we
defined to mean that in both protocols, an agent can guarantee the same
simultaneous bounds on their envy against any subset of the other agents).

However, as we have seen both in some of our conversion algorithms and in the
case of representing some classic protocols as BC protocols, the simplicity of
the model comes with a trade-off in space complexity, and in some cases the
conversion seems to result in $\Theta(n!)$ or even worse blowups in the size
of the tree representation compared to the original protocol.

###  4.2 Future Work

#### Checking equivalence

Most of our results involve constructing protocols that are equivalent to a
given protocol. It would be interesting to look into the computational
complexity of checking whether two given BC protocols are equivalent under one
of the notions of equivalence we have defined, or the highly related question
of computing the value/envy bounds an agent can guarantee for themselves in a
given protocol. Note that the former question very easily reduces to the
latter.

#### Simplifying protocols

As we have seen above, explicitly representing a cake-cutting protocol as a
tree, whether in the GCC or the BC protocols model, often results in a blowup
in the size of the protocol, compared to its original statement. A natural
question to ask is whether we can simplify a given protocol, i.e. find a
strongly envy-equivalent protocol with a smaller tree representation. A brute-
force approach to this would involve finding all protocols whose tree
representation is smaller than the given one, and then checking, for each of
these protocols, whether it is equivalent to the original protocol (which
reduces to the question discussed previously).

#### Adding extra structure to the model

Another possible direction is to consider whether we can decrease the size of
the tree representation by adding some extra structure to the model, as we
already did informally in Algorithm 1 for the Selfridge-Conway protocol, where
on line 1, for example, we label the piece agent $2$ cut $A$ and the other two
pieces $B$ and $C$, instead of explicitly showing the three (virtually
identical) branches corresponding to each piece.

We propose two possible types of nodes to add:

  * •

_Piece permutation:_ agent $i$ permutes the order of the existing pieces of
cake. If there are currently $m$ cuts in the cake, then there are $m+1$
continuous pieces which we can number $1,...,m$ from left to right, and agent
$i$ can apply some permutation $\sigma\in S_{m+1}$ to reorder them. Note this
is functionally equivalent to the labelling used in the Selfridge-Conway
protocol, which we mentioned above, since agent $2$ could, for example,
reorder the pieces in increasing order of their value, and then cut the third
piece. This would reduce the size of the BC tree representation of the
Selfridge-Conway protocol in figure 1, since we would only need a single
branch at the topmost choose node instead of three. This leads us to believe
there is a class of protocols for which adding this type of node can be proven
to reduce the size of the protocol, possibly exponentially in the case where
this kind of node is used multiple times.

Adding piece permutation nodes to the BC protocols model is straightforward,
as long as we refer to the pieces by their position in the cake (e.g. “agent
$1$ cuts the second piece from the left”), rather than by their endpoints,
which in the case of BC protocols does not make any difference.

We can also add them to GCC protocols, provided we change the model to refer
to pieces by their position in the cake, but in this case we have to decide
whether we should account for pieces that agents have already taken from the
cake, e.g. if the cake is divided into three pieces $1,2,3$ and some agent
chooses piece $2$, should the remaining pieces now be $1$ and $3$ or can we
relabel them $1$ and $2$?

  * •

_Agent permutation:_ There are two types of action we can consider here:
either some agent $i$ permutes the order of the other agents, which would
allow them to choose, for example, which of the other agents they are envious
of in some situation, or we have a referee who can reorder the agents
according to some rule. The former option can be added to both GCC and BC
protocols, while the latter can more naturally be added to GCC protocols, as
an extension to the existing if-else node, and could be used, for example, in
the case of the Dubins-Spanier protocol, where we use an if-else node to
identify the agent who made the leftmost cut, in which case we can reorder the
agents so that agent is now the $n$-th one, and recurse on the first $n-1$
agents.

#### Converting other protocols to the BC model

We have already shown that some classic protocols (Selfridge-Conway, Dubins-
Spanier, Even-Paz) can be converted to BC protocols, but it would be
interesting to extend this result to other protocols in the literature. Of
particular interest would be the discrete bounded envy-free protocol for $n$
agents proposed by Aziz & Mackenzie, [1]. We suspect that it is possible to
convert this protocol to a BC protocol, since a lot of the additional
structure used in the protocol could be encoded into the BC tree
representation, or implicitly in the agents’ strategies to achieve envy-
freeness, but we have not checked this.

## Acknowledgements

We thank Simina Brânzei for helpful comments.

## References

  * Aziz & Mackenzie, [2016] Aziz, Haris, & Mackenzie, Simon. 2016.  A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents.  Pages 416–427 of: Dinur, Irit (ed), IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS.  IEEE Computer Society.
  * Brams & Taylor, [1996] Brams, Steven J., & Taylor, Alan D. 1996.  Fair Division: From Cake-Cutting to Dispute Resolution.  Cambridge University Press.
  * Brânzei, [2015] Brânzei, Simina. 2015.  Computational Fair Division.  Ph.D. thesis, Department of Computer Science, Aarhus University.  Main Supervisor: Peter Bro Miltersen.
  * Brânzei & Miltersen, [2015] Brânzei, Simina, & Miltersen, Peter Bro. 2015.  A Dictatorship Theorem for Cake Cutting.  Page 482–488 of: Proceedings of the 24th International Conference on Artificial Intelligence.  IJCAI’15.  AAAI Press.
  * Brânzei et al. , [2013] Brânzei, Simina, Caragiannis, Ioannis, Kurokawa, David, & Procaccia, Ariel D. 2013.  Equilibria of Generalized Cut and Choose Protocols.  CoRR, abs/1307.2225.
  * Brânzei et al. , [2016] Brânzei, Simina, Caragiannis, Ioannis, Kurokawa, David, & Procaccia, Ariel D. 2016.  An Algorithmic Framework for Strategic Fair Division.  Pages 418–424 of: Schuurmans, Dale, & Wellman, Michael P. (eds), Procs. of the 30th AAAI Conference on Artificial Intelligence.  AAAI Press.
  * Chen et al. , [2013] Chen, Yiling, Lai, John K., Parkes, David C., & Procaccia, Ariel D. 2013.  Truth, justice, and cake cutting.  Games and Economic Behavior, 77(1), 284–297.
  * Dubins & Spanier, [1961] Dubins, L. E., & Spanier, E. H. 1961.  How to Cut a Cake Fairly.  The American Mathematical Monthly, 68(1P1), 1–17.
  * Even & Paz, [1984] Even, S., & Paz, A. 1984.  A note on cake cutting.  Discrete Applied Mathematics, 7(3), 285–296.
  * Procaccia, [2013] Procaccia, Ariel D. 2013.  Cake cutting: not just child’s play.  Commun. ACM, 56(7), 78–87.
  * Robertson & Webb, [1998] Robertson, J., & Webb, W. 1998.  Cake-Cutting Algorithms: Be Fair if You Can.  A K Peters.
  * Steinhaus, [1949] Steinhaus, H. 1949.  Sur la division pragmatique.  Econometrica, 17, 315–319.
  * Tao, [2021] Tao, Biaoshuai. 2021.  On Existence of Truthful Fair Cake Cutting Mechanisms.  CoRR, abs/2104.07387.
  * Woeginger & Sgall, [2007] Woeginger, Gerhard J., & Sgall, Jiří. 2007.  On the complexity of cake cutting.  Discrete Optimization, 4(2), 213–220.


# Embedding Euclidean Distance Graphs in $\mathbb{R}^{n}$ and $\mathbb{Q}^{n}$

Matt Noble
Department of Mathematics and Statistics
Middle Georgia State University
<EMAIL_ADDRESS>
###### Abstract

For $S\subseteq\mathbb{R}$, positive integer $n$, and $d>0$, let $G(S^{n},d)$
be the graph whose vertex set is $S^{n}$ where any two vertices are adjacent
if and only if they are Euclidean distance $d$ apart. The primary question we
will consider in our work is as follows. Given $n$ and distance $d$ actually
realized as a distance between points of the rational space $\mathbb{Q}^{n}$,
does there exist a finite graph $G$ that appears as a subgraph of
$G(\mathbb{Q}^{n},d)$ but not as a subgraph of $G(\mathbb{R}^{n-1},1)$? We
answer this question affirmatively for $n\leq 5$, and along the way, resolve a
few related questions as well.

Keywords and phrases: Euclidean distance graph, graph dimension, graph
embedding, rational points

##  1 Definitions

Throughout, we will designate by $\mathbb{R}$, $\mathbb{Q}$, and $\mathbb{Z}$
the rings of real numbers, rational numbers, and integers, respectively, with
each of these spaces coming equipped with the standard Euclidean distance
metric. The structure most fundamental to our work will be that of the
Euclidean distance graph. For $S\subseteq\mathbb{R}$, positive integer $n$,
and $d>0$, let $G(S^{n},d)$ be the graph whose vertex set is $S^{n}$, with any
two vertices $x,y\in S^{n}$ being adjacent if and only if $x,y$ are distance
$d$ apart. If such a graph has vertex set $\mathbb{R}^{n}$, in all
circumstances, $d$ is taken to be 1, as $G(\mathbb{R}^{n},d)$ and
$G(\mathbb{R}^{n},1)$ are isomorphic by an obvious scaling argument. However,
when $S$ is a proper subset of $\mathbb{R}$, like say, $S=\mathbb{Q}$, the
selection of $d$ matters, as the graphs $G(\mathbb{Q}^{n},d_{1})$ and
$G(\mathbb{Q}^{n},d_{2})$ may not be isomorphic when $d_{1}$ and $d_{2}$ are
not rational multiples of each other.

If $f$ is any graph parameter that can be defined on $G(S^{n},d)$, we will
write $f(S^{n},d)$ instead of the unwieldy $f(G(S^{n},d))$. We make special
note of two parameters that will play a central role in our discussion. Let
$G$ be any graph. The clique number $\omega(G)$ is equal to the maximum $m$
such that the complete graph $K_{m}$ appears as a subgraph of $G$. Considered
in our current setting, $\omega(S^{n},d)$ is the largest possible number of
points of $S^{n}$ that comprise the vertices of a regular simplex of edge-
length $d$. Originally given in [5], the dimension of $G$, denoted $\dim(G)$,
is equal to the minimum $n$ such that $G$ appears as a subgraph of
$G(\mathbb{R}^{n},1)$. In the various literature on the subject (see [12] for
an expansive history), if $G$ is indeed a subgraph of $G(\mathbb{R}^{n},1)$,
$G$ is said to be a unit-distance graph in $\mathbb{R}^{n}$ or to have a unit-
distance representation or unit-distance embedding in $\mathbb{R}^{n}$. If the
value $n$ is not stipulated – that is, $G$ is just referred to as being a
“unit-distance graph” with no other specification given – it is assumed that
$\dim(G)\leq 2$.

##  2 Introduction (and a Brief Interlude)

We give in this section a brief (and perhaps amusing) digression detailing the
genesis of our current work. Those who desire to see only the main result of
the article may feel free to skip ahead to the next section.

In March of 2019, the author attended the SEICCGTC held at Florida Atlantic
University in Boca Raton, and between talks, chatted with Pete Johnson,
discussing mathematics, life, and the current goings-on at the author’s alma
mater, Auburn University. It came to knowledge that Allison Lab, a somewhat
outdated building on campus, had been slated for demolition. Pete had held the
same office in the bowels of Allison for many years, and had been given a few
months to relocate to a new building all the files, papers, and other sundries
that one accumulates over decades of mathematical activity. In attempting to
decide what to keep and what to throw away, Pete had unearthed a number of
problems, each of which at some nebulous point in the past had been quickly
jotted down on a stray scrap of paper. One of which was the following.

“Let $G$ be a unit-distance graph. Is $G$ guaranteed to be realized as a
subgraph of some regular unit-distance graph $H$?”

The author was able to supply an affirmative answer to this question, and it
is given as Theorem 2.1 below.

###### Theorem 2.1

Let $G$ be a unit-distance graph. There exists a regular unit-distance graph
$H$ such that $G$ is a subgraph of $H$.

###### Proof.

To begin, note that for any integer $r\geq 1$, there exists an $r$-regular
unit-distance graph $K$. This is easily seen by taking $K_{2}$ in the case of
$r=1$. For $r>2$, one can create an $r$-regular graph $K$ by starting with an
$(r-1)$-regular unit-distance graph $K^{\prime}$, and then translating each
point in the plane that is a vertex of $K^{\prime}$ by an appropriate unit
vector. The vertex set of $K$ will then be each of those points corresponding
to vertices of $K^{\prime}$ along with their translates.

Let $G$ be a unit-distance graph. Consider a unit-distance representation of
$G$ in $\mathbb{R}^{2}$, and suppose we have maximum degree $\Delta(G)=r$.
Form a new graph $G^{\prime}$ by way of the following procedure. For each
$v\in V(G)$ with $\deg(v)<r$, place $r-\deg(v)$ points on the unit circle
centered at $v$ along with edges making those newly-placed vertices adjacent
to $v$. Let $P=\\{v\in V(G^{\prime}):\deg(v)=1\\}$.

Suppose $K$ is an $r$-regular unit-distance graph. Let $K^{\prime}=K-uv$ for
any adjacent $u,v\in V(K)$. Select $a,b\in P$. Place a copy of $K^{\prime}$ in
the plane so that $a$ and $u$ coincide. Now place a new vertex at distance 1
from $v$. Repeat this procedure as many times as necessary, and do so in order
that the vertex $v$ in the final copy placed of $K^{\prime}$ coincides with
$b$.

If $|P|$ is even, the steps outlined above can be iteratively applied to pairs
of vertices $a,b\in P$ to construct an $r$-regular graph $H$ having $G$ as a
subgraph. If $|P|$ is odd, instead select $c\in P$, and then execute the same
procedure for pairs of vertices in $P\setminus\\{c\\}$ to eventually produce a
unit-distance graph $H^{\prime}$ such that $\deg(c)=1$ and all vertices in
$V(H^{\prime})\setminus\\{c\\}$ have degree $r$. Now take $r$ copies of
$H^{\prime}$, and orient them such that the vertices corresponding to $c$ in
each of those copies are placed at the same point in $\mathbb{R}^{2}$. This
can be done so that no other vertices coincide, and the resulting graph is our
desired $H$.∎∎

For an arbitrary graph $G$, a subgraph $K$ of $G$ is defined to be induced if
for any $u,v\in V(K)$ with $uv\not\in E(K)$, then $uv\not\in E(G)$ as well. If
$G$ is an induced subgraph of $G(\mathbb{R}^{n},1)$, there exists a drawing of
$G$ as a unit-distance graph in $\mathbb{R}^{n}$ in which it is forbidden that
non-adjacent vertices be placed at a unit-distance apart. Often in the
literature, such a drawing of $G$ is referred to as a faithful embedding (see
[1] or [6]). With this in mind, we may strengthen our answer to Johnson’s
question by showing that if the graph $G$ in the statement of the question is
an induced unit-distance graph, then $H$ can be constructed as an induced
unit-distance graph as well. To do this, all we need to do is replace the
graph $K$ which was used as a device in the proof of Theorem 2.1 with an
induced unit distance-graph $J$ having two non-adjacent $a,b\in V(J)$
satisfying $\deg(a)=\deg(b)=r-1$, and for all $v\in V(J)\setminus\\{a,b\\}$,
$\deg(v)=r$. We show the existence of such $J$ in the following theorem.

###### Theorem 2.2

Let $r\in\mathbb{Z}^{+}$ with $r\geq 2$. There exists an induced unit-distance
graph $J$ with two non-adjacent $a,b\in V(J)$ satisfying
$\deg(a)=\deg(b)=r-1$, and for all $v\in V(J)\setminus\\{a,b\\}$, $\deg(v)=r$.

###### Proof.

We proceed by way of induction. In the case of $r=2$, one need only let $J$ be
the path $P_{3}$. Now let $k\in\mathbb{Z}^{+}$ and suppose that $J$ is an
induced unit-distance graph such that there exist non-adjacent $a,b\in V(J)$
with $\deg(a)=\deg(b)=k-1$, and for all $v\in V(J)\setminus\\{a,b\\}$,
$\deg(v)=k$. Position $J$ so that $a,b$ both lie on the $x$-axis. For some
small $\epsilon>0$, define a unit vector
$\phi=\langle\sqrt{1-\epsilon^{2}},\epsilon\rangle$. Let
$f:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ translate the plane by $\phi$.
Note that $\epsilon$ can be chosen so that the induced graph $J^{\prime}$ on
vertex set $V(J)\cup f(V(J))$ has vertices $a$, $b$, $f(a)$, and $f(b)$ of
degree $k$ and all others of degree $k+1$.

Let line $\mathcal{L}$ be the perpendicular bisector of $a$ and $f(b)$.
Consider a point $P$ on $\mathcal{L}$. Let
$g:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ be a transformation that rotates
the plane about $P$ such that $|a-g(a)|=|f(b)-g(f(b))|=1$. Again, note that
$P$ can be selected so that the induced graph $J^{\prime\prime}$ on vertex set
$V(J^{\prime})\cup g(V(J^{\prime}))$ has vertices $f(a)$, $b$, $g(f(a))$ and
$g(b)$ of degree $k$ and all others of degree $k+1$. Denote by $C$ the circle
upon whose boundary lie $f(a)$, $b$, and $g(b)$. Let
$h:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ be a transformation that rotates
the plane about the center of $C$ such that
$|f(a)-h(f(a))|=|b-h(b)|=|g(b)-h(g(b))|=1$. Let $J^{\prime\prime\prime}$ be
the induced graph on vertex set $V(J^{\prime\prime})\cup
h(V(J^{\prime\prime}))$. Through careful selection of $\epsilon$ and $P$
(essentially, making $\epsilon$ sufficiently small and $P$ far enough away
from $a,f(b)$), we can guarantee that $J^{\prime\prime\prime}$ has $g(f(a))$
and $h(g(f(a)))$ being vertices of degree $k$ and all other vertices having
degree $k+1$. This completes the proof of the theorem.∎∎

As described above, Theorems 2.1 and 2.2 together give us Theorem 2.3 as a
corollary.

###### Theorem 2.3

Let $G$ be an induced unit-distance graph. There exists a regular induced
unit-distance graph $H$ such that $G$ is a subgraph of $H$.

Now, the above arguments are loosely in the same mathematical neighborhood as
the material of Section 3, but they do not serve as a direct lead-in. That
said, we choose to introduce our current work by way of this discussion
because Johnson’s question strikes us as a departure from the way problems
concerning Euclidean distance graphs are usually formulated. Typically, a
problem seen in this field will begin with a list of graph characteristics and
some predetermined $n$, and then ask if there exists a Euclidean distance
graph $G$ in $\mathbb{R}^{n}$ that satisfies those properties. A related
question may then ask for the minimum possible value of some property of $G$,
be it $|V(G)|$ or $|E(G)|$, or some other parameter. For a stunning success,
see de Grey’s construction [4] of a 5-chromatic unit-distance graph in the
plane, and the torrent of work that followed (see [7], [8], and numerous
others). Johnson’s question, however, begins with the a priori knowledge that
$G$ is a unit-distance graph, and then asks about the possible nature of its
embedding. This line of questioning feels (to the author, at least) as being
quite fresh, and easily lending to further investigation. In Section 3, we
will pose another question along these lines, where we ask among all graphs
$G$ having $\dim(G)=n$, if it is possible, for each distance $d$ realized
between points of $\mathbb{Q}^{n}$, that some of those graphs can be drawn
with their vertices being points of $\mathbb{Q}^{n}$ and edges of length $d$.
We ultimately answer this in the affirmative for $n\leq 5$. In Section 4, we
give a few additional thoughts on how a future attack on this question may
proceed, and along the way, resolve a related problem presented in [2]
concerning clique numbers of graphs $G(\mathbb{Q}^{n},d)$.

##  3 Embeddings in $\mathbb{Q}^{n}$

The primary question considered in this section is the following.

###### Question 1

Let $n$ be a positive integer and suppose $d>0$ is a distance realized between
points of $\mathbb{Q}^{n}$. Is there guaranteed to exist a finite subgraph of
$G(\mathbb{Q}^{n},d)$ that is not a subgraph of $G(\mathbb{R}^{n-1},1)$?

Note that an alternate formulation of Question 1 would be to ask if there
exists a finite subgraph $G$ of $G(\mathbb{Q}^{n},d)$ with $\dim(G)=n$. In
this section we will resolve Question 1 for $n\in\\{1,\ldots,5\\}$ and show
that in each of those cases, it has an affirmative answer. For $n=1$, this is
trivial, as by convention, the space $\mathbb{R}^{0}$ consists of a single
point. Also obvious is the case $n=2$, as the cycle $C_{4}$ has
$\dim(C_{4})=2$ and appears as a subgraph of $G(\mathbb{Q}^{2},d)$ for all
$d>0$ realized as a distance between rational points in the plane. In
considering Question 1 for $n\geq 3$, we will call upon a number of past
results, each of a geometric or number-theoretic sort.

Lemma 3.1 appears in many introductory number theory texts, for example [10].

###### Lemma 3.1

Consider a quadratic Diophantine equation of the form below, where
$a,\ldots,f\in\mathbb{Q}$.

$ax^{2}+bxy+cy^{2}+dx+ey+f=0$

If this equation has at least one non-trivial rational solution $(x,y)$, it
has infinitely many rational solutions.

We now utilize Lemma 3.1 to show that the complete bipartite graph $K_{2,3}$
is a subgraph of $G(\mathbb{Q}^{3},d)$ for all $d>0$ realized as a distance
between points of $\mathbb{Q}^{3}$. As $\dim(K_{2,3})=3$ (see [5] for
elaboration, or see Lemma 3.3 to follow), we have an affirmative answer for
Question 1.

###### Theorem 3.2

The graph $K_{2,3}$ is a subgraph of $G(\mathbb{Q}^{3},d)$ for every $d>0$
realized as a distance between points of $\mathbb{Q}^{3}$.

###### Proof.

Suppose that $K_{2,3}$ has bipartition $\\{a_{1},a_{2}\\}$ and
$\\{b_{1},b_{2},b_{3}\\}$. Assume $a_{1}$ is the origin and consider the
sphere $S$ having radius $d$ and centered at the origin. Let
$b_{1},b_{2},b_{3}$ be rational points on $S$ such that the plane determined
by $b_{1},b_{2},b_{3}$ does not contain the origin. Since $b_{1},b_{2},b_{3}$
cannot be collinear, we may let $C$ be the circumcenter of the triangle whose
vertices are $b_{1},b_{2},b_{3}$. We have $C\in\mathbb{Q}^{3}$ by the
following rationale. Letting $P$ be the plane defined by $b_{1},b_{2},b_{3}$,
note that $P$ is given by an equation of the form $n_{1}x+n_{2}y+n_{3}z=q$
where $n_{1},n_{2},n_{3},q$ are each rational. Furthermore, the line $L$
passing through the origin and $C$ is given by the parameterization
$x=n_{1}t$, $y=n_{2}t$, $z=n_{3}t$. The point $C$ is just the intersection of
$P$ and $L$, and in substituting the above parametric equations for $x$, $y$,
and $z$ into the equation for $P$, the obtained solution for $t$ is rational.
Thus $C\in\mathbb{Q}^{3}$. We may then place vertex $a_{2}$ at the point $2C$
to complete our embedding of $K_{2,3}$.∎∎

In [9], Maehara determines the Euclidean dimension of all complete
multipartite graphs. We remark that the Euclidean dimension of a graph $G$
(often notated $\dim_{E}(G)$) is defined similarly to the dimension of $G$,
except for the added stipulation that in any unit-distance representation of
$G$ in $\mathbb{R}^{n}$, non-adjacent vertices of $G$ are forbidden to be
placed at a unit-distance apart. Although he does not explicitly mention it,
the constructions Maehara gives in [9] show that for a complete multipartite
graph $G$, it is indeed the case that $\dim_{E}(G)=\dim(G)$. We then have
Lemma 3.3 as an immediate corollary of the main result of [9].

###### Lemma 3.3

Let $\alpha,\beta,\gamma$ be non-negative integers with
$\alpha+\beta+\gamma\geq 2$. Let $G$ be a complete
$(\alpha+\beta+\gamma)$-partite graph having exactly $\alpha$ parts of size 1,
exactly $\beta$ parts of size 2, and exactly $\gamma$ parts of size greater
than or equal to 3. If $\beta+\gamma\leq 1$, then
$\dim(G)=\alpha+\beta+2\gamma-1$. If $\beta+\gamma\geq 2$,
$\dim(G)=\alpha+\beta+2\gamma$.

We now show that for any $n\in\mathbb{Z}^{+}$, there is at least one value of
$d$ which results in Question 1 having an affirmative answer.

###### Theorem 3.4

Let $n\geq 2$. Let $G$ be the complete multipartite graph having $(n-1)$ parts
of size 1 and one part of size 3. Then $G$ is a subgraph of
$G(\mathbb{Q}^{n},\sqrt{2})$ but not a subgraph of $G(\mathbb{R}^{n-1},1)$.

###### Proof.

By Lemma 3.3, $\dim(G)=n$ so $G$ is not a subgraph of $G(\mathbb{R}^{n-1},1)$.
To see that $G$ is indeed a subgraph of $G(\mathbb{Q}^{n},\sqrt{2})$, begin by
labeling the partite sets of $G$ as
$\\{v_{1}\\},\ldots,\\{v_{n-1}\\},\\{b_{1},b_{2},b_{3}\\}$. Place
$v_{1},\ldots,v_{n-1}\in\mathbb{Q}^{n}$ where each $v_{i}$ has its $i^{th}$
coordinate being a 1 and all other coordinates being 0. Now consider points of
$\mathbb{R}^{n}$ of the form $(t,\ldots,t,w)$. Such a point is at distance
$\sqrt{2}$ simultaneously from each of $v_{1},\ldots,v_{n-1}$ if and only if
Equation 3.1 holds.

$(n-2)t^{2}+(t-1)^{2}+w^{2}=2$ (3.1)

We know this equation has solution $t=0,w=1$. By Lemma 3.1, it has infinitely
many rational solutions. Thus $b_{1},b_{2},b_{3}$ can all be placed at points
of $\mathbb{Q}^{n}$.∎∎

We give as Lemma 3.5 the main result of the recent [2]. Coupled with Theorem
3.4, it answers Question 1 affirmatively for all $n\equiv 0\pmod{4}$.

###### Lemma 3.5

A space $\mathbb{Q}^{n}$ has the property that the graphs
$G(\mathbb{Q}^{n},d_{1})$ and $G(\mathbb{Q}^{n},d_{2})$ are isomorphic for all
pairs of distances $d_{1},d_{2}>0$ realized between points of $\mathbb{Q}^{n}$
if and only if $n$ is equal to 1, 2, or a multiple of 4.

In [3], Beeson resolves the problem of deciding when a given triangle is
similar to one that can be drawn with its vertices being points of
$\mathbb{Z}^{n}$, with Lemma 3.6 being one of the main results. We will state
it exactly as it appears in [3], and then give a small amount of elaboration
afterward.

###### Lemma 3.6

A triangle is embeddable in $\mathbb{Z}^{4}$ if and only if all of its
tangents are rational multiples of $\sqrt{k}$, where $k$ is a positive integer
that can be represented as a sum of three squares.

Throughout [3], Beeson uses the word “embeddable” not to mean precisely that a
triangle $T$ can be drawn with its vertices being points of $\mathbb{Z}^{n}$,
but rather that some triangle similar to $T$ can be so drawn. This distinction
ends up mattering when the setting is $\mathbb{Z}^{4}$, as for example, an
equilateral triangle with edge-length 1 cannot be drawn with its vertices
being points of $\mathbb{Z}^{4}$, but an equilateral triangle with side length
$\sqrt{2}$ can. However, for our means this is not an issue when we shift the
setting to $\mathbb{Q}^{4}$. Fundamental to the proof of Lemma 3.5 in [2] is
the existence, for $n\equiv 0\pmod{4}$, of a bijective transformation
$\varphi:\mathbb{Q}^{n}\rightarrow\mathbb{Q}^{n}$ that scales distance by a
factor $\sqrt{q}$ for any $q\in\mathbb{Q}^{+}$. Thus Beeson’s notion of
“embeddability” can just be taken to mean that if a triangle $T$ (whose side
lengths are of the form $\sqrt{a},\sqrt{b},\sqrt{c}$ with $a,b,c$ rational)
fits the given hypotheses, then $T$ can be oriented so that its vertices are
points of $\mathbb{Q}^{4}$. We formalize this observation in Lemma 3.7.

###### Lemma 3.7

Let $T$ be a triangle with side lengths $\sqrt{a},\sqrt{b},\sqrt{c}$ with
$a,b,c\in\mathbb{Q}^{+}$. Then $T$ can be drawn with its vertices being points
of $\mathbb{Q}^{4}$ if and only if all of its tangents are rational multiples
of $\sqrt{k}$, where $k$ is a positive integer that can be represented as a
sum of three squares.

There are a few more things to note about Lemmas 3.6 and 3.7. In the
commentary in [3], Beeson makes an exception for $90^{\circ}$ angles, and says
to just consider $\infty$ (that is, $\tan 90^{\circ}$) as also being a
rational multiple of an appropriate $\sqrt{k}$. Also, the positive integers
$k$ representable as a sum of three integer squares are described by a well-
known result of Gauss, where it is shown that $k=x^{2}+y^{2}+z^{2}$ for
integers $x,y,z$ if and only if the square-free part of $k$ is not congruent
to $7\pmod{8}$.

We now prove that Question 1 has an affirmative answer for $n=5$. Note that
the dimension of the complete tripartite graph $K_{1,3,3}$ is 5 by Lemma 3.3,
and also that for every $r\in\mathbb{Q}^{+}$ and $n\geq 4$, $\sqrt{r}$ is
realized as a distance between points of $\mathbb{Q}^{n}$ as a consequence of
Lagrange’s four-square theorem.

###### Theorem 3.8

The complete tripartite graph $K_{1,3,3}$ is a subgraph of
$G(\mathbb{Q}^{5},\sqrt{r})$ for every $r\in\mathbb{Q}^{+}$.

###### Proof.

Without loss of generality, we may assume that $r$ is a positive integer. Let
$G=K_{1,3,3}$ and suppose that $G$ has partite sets $\\{a_{1},a_{2},a_{3}\\}$,
$\\{b_{1},b_{2},b_{3}\\}$, and $\\{c\\}$. To begin our embedding of $G$ in
$\mathbb{Q}^{5}$, place $c$ at the origin $O=(0,0,0,0,0)$. Let $T$ be the
right triangle in the diagram below.

Write $P_{1}=(x_{1},y_{1},z_{1},w_{1},0)$ and
$P_{2}=(x_{2},y_{2},z_{2},w_{2},0)$ and assume $P_{1},P_{2}\in\mathbb{Q}^{5}$.
For this assumption to be valid, by Lemma 3.7 we must have
$\sqrt{\frac{r-r_{1}}{r_{1}}}$ a rational multiple of $\sqrt{k}$ for some
integer $k$ representable as a sum of three squares. Note that
$\sqrt{\frac{r-r_{1}}{r_{1}}}$ satisfying this property implies
$\sqrt{\frac{r_{1}}{r-r_{1}}}$ does as well.

Now choose a point $P_{3}\in\mathbb{Q}^{5}$ such $P_{3}$ has 0 as its fifth
coordinate, and that the vector $\overrightarrow{P_{1}P_{3}}$ is orthogonal to
both $\overrightarrow{OP_{1}}$ and $\overrightarrow{P_{1}P_{2}}$. Let
$\mathcal{P}$ be the plane defined by vectors $u=\overrightarrow{P_{1}P_{2}}$
and $v=\overrightarrow{P_{1}P_{3}}$. Just to make sure we are clear in the
terminology being used, note that $\mathcal{P}$ is a 2-dimensional plane, not
a hyperplane. Letting $u=\langle u_{1},u_{2},u_{3},u_{4},0\rangle$ and
$v=\langle v_{1},v_{2},v_{3},v_{4},0\rangle$, we can parameterize points of
$\mathcal{P}$ as
$(su_{1}+tv_{1}+x_{1},su_{2}+tv_{2}+y_{1},su_{3}+tv_{3}+z_{1},su_{4}+tv_{4}+w_{1},0)$
for $s,t\in\mathbb{R}$. The set of points in $\mathcal{P}$ at distance
$\sqrt{r}$ from the origin are those satisfying Equation 3.2.

$(su_{1}+tv_{1}+x_{1})^{2}+(su_{2}+tv_{2}+y_{1})^{2}+(su_{3}+tv_{3}+z_{1})^{2}+(su_{4}+tv_{4}+w_{1})^{2}=r$
(3.2)

This Diophantine equation satisfies the hypotheses of Lemma 3.1, with the
existence of point $P_{2}$ implying that is has infinitely many rational
solutions. Three of these solutions can be used to place $a_{1},a_{2},a_{3}$.

Let $\mathcal{S}\subset\mathbb{R}^{5}$ be the set of all points simultaneously
equidistant to $a_{1},a_{2},a_{3},c$ and whose last coordinate is 0. Set
$\mathcal{S}$ consists of the intersection of three hyperplanes of
$\mathbb{R}^{4}$, each of which has rational coefficients. We have
$\mathcal{S}$ being a line which may be parameterized as
$(\alpha_{1}t+\beta_{1},\alpha_{2}t+\beta_{2},\alpha_{3}t+\beta_{3},\alpha_{4}t+\beta_{4},0)$
where the $\alpha_{i}$ are rational. We of course may use any point on the
line for $\beta=(\beta_{1},\beta_{2},\beta_{3},\beta_{4},0)$, however we will
specifically set $\beta=(qx_{1},qy_{1},qz_{1},qw_{1},0)$ where
$q=\frac{r}{2r_{1}}$. It is straightforward to verify that $\beta$ is
equidistant from each of $a_{1},a_{2},a_{3},c$.

Let $\mathcal{S}^{\prime}\subset\mathbb{R}^{5}$ be simply the set of all
points simultaneously equidistant to $a_{1},a_{2},a_{3},c$. Any point of
$\mathcal{S}^{\prime}$ can be expressed as
$(\alpha_{1}t+qx_{1},\alpha_{2}t+qy_{1},\alpha_{3}t+qz_{1},\alpha_{4}t+qw_{1},k)$,
and for such a point to be at distance $\sqrt{r}$ from each of
$a_{1},a_{2},a_{3},c$, it must satisfy the following Diophantine equation.

$(\alpha_{1}t+qx_{1})^{2}+(\alpha_{2}t+qy_{1})^{2}+(\alpha_{3}t+qz_{1})^{2}+(\alpha_{4}t+qw_{1})^{2}+k^{2}=r$
(3.3)

Setting $t=0$, we obtain $k^{2}=r-q^{2}r_{1}$. So, if $r-q^{2}r_{1}$ happens
to be a non-zero rational square, we have a non-trivial rational solution for
Equation 3.3, and Lemma 3.1 then indicates that there are infinitely many such
solutions. Just as before, we can use three of those solutions to place
$b_{1},b_{2},b_{3}$ and complete our embedding of $G$ in $\mathbb{Q}^{5}$.

All that needs to be done to ensure that this embedding process is successful
is to select $r_{1}\in\mathbb{Q}^{+}$ so that both of the following hold:

  1. $(i)$

$\sqrt{r-q^{2}r_{1}}\in\mathbb{Q}^{+}$.

  2. $(ii)$

$\frac{r-r_{1}}{r_{1}}$ is a sum of three rational squares.

Our plan is as follows. Let $r_{1}=(\frac{a}{b})r$ where
$a,b\in\mathbb{Z}^{+}$ and $a<b$. After some simplification, we have that
$(i)$ holds – that is, $r-q^{2}r_{1}$ is a rational square – if and only if
$r(\frac{4a-b}{a})$ is a rational square. Regarding $(ii)$, and after
simplifying and then applying Gauss’s condition concerning integers that are
the sum of three squares, we find that $\frac{r-r_{1}}{r_{1}}$ is a sum of
three rational squares if and only if $ab-a^{2}$ is a sum of three integer
squares. We now consider two cases.

If $r$ is even, let $a$ be some sufficiently large odd square and let
$4a-b=r$. Clearly, this selection of $a,b$ satisfies $(i)$. Since by
assumption $r$ is square-free, we have $b\equiv 2\pmod{4}$. As any odd square
is congruent to 1 modulo 4, we then have $ab-a^{2}\equiv 1\pmod{4}$. Thus
$(ii)$ holds as well.

Now suppose $r$ is odd. If $r\equiv 1\pmod{4}$, let $a=rd^{2}$ where $d$ is
some sufficiently large odd integer. Select $b$ so that $4a-b$ is an odd
square, and note that this gives $b\equiv 3\pmod{4}$. Clearly, $(i)$ holds.
Since $a\equiv 1\pmod{4}$, we then have $ab-a^{2}\equiv 2\pmod{4}$ and $(ii)$
holds. If $r\equiv 3\pmod{4}$, let $a=rd^{2}$ where $d$ is some sufficiently
large even integer. Again, select $b$ so that $4a-b$ is an odd square, which
allows $(i)$ to hold and results in $b\equiv 3\pmod{4}$. Here,
$ab-a^{2}=d^{2}(rb-r^{2}d^{2})$, and in accordance with Gauss’s condition, we
have $d^{2}(rb-r^{2}d^{2})$ being representable as a sum of three integer
squares if and only if $rb-r^{2}d^{2}$ is representable as a sum of three
integer squares. Since $r,b$ are both congruent to 3 modulo 4 and $d$ is even,
we have $rb-r^{2}d^{2}\equiv 1\pmod{4}$, and $(ii)$ holds.∎

∎

##  4 Concluding Thoughts

As a reader progresses through the previous section, it would be natural to
ask if the proof of Theorem 3.4 can be applied in a general setting.
Unfortunately, it cannot, as the proof was reliant on the existence of $K_{n}$
appearing as a subgraph of $G(\mathbb{Q}^{n},\sqrt{2})$. As it turns out,
there exist specific selections of $n,d$ in which the largest $m$ such that
$K_{m}$ is a subgraph of $G(\mathbb{Q}^{n},d)$ is only $m=n-3$. In this
section, we expound upon this observation, and along the way, resolve a
question posed in [2]. We then give a few thoughts on how a future resolution
of Question 1 may perhaps proceed.

As defined in Section 1, let $\omega(G)$ denote the clique number of $G$. For
$S^{n}\subseteq\mathbb{R}^{n}$, the clique number $C_{1}(S^{n})$ and lower
clique number $c_{1}(S^{n})$ are defined in [2], where
$C_{1}(S^{n})=\max\\{\omega(S^{n},d):d>0\\}$ and
$c_{1}(S^{n})=\min\\{\omega(S^{n},d):d>0\text{ and }d\text{ is actually
realized as a distance between points of }S^{n}\\}$. The proof of the “only
if” direction of Lemma 3.5 consisted of showing that for $n\in\mathbb{Z}^{+}$
with $n\geq 3$ and $n\not\equiv 0\pmod{4}$, it is the case that
$C_{1}(\mathbb{Q}^{n})\neq c_{1}(\mathbb{Q}^{n})$. The question was then posed
in [2] as to how far apart $C_{1}(\mathbb{Q}^{n})$ and $c_{1}(\mathbb{Q}^{n})$
can possibly be, with an example given where
$C_{1}(\mathbb{Q}^{n})-c_{1}(\mathbb{Q}^{n})=3$. A well-known result of
Schoenberg [11] determines, for each $n$, the largest regular simplex that can
be drawn with vertices in $\mathbb{Z}^{n}$. Since
$C_{1}(\mathbb{Z}^{n})=C_{1}(\mathbb{Q}^{n})$ due to a scaling argument, we
will present Schoenberg’s result using our current notation as Lemma 4.1.

###### Lemma 4.1

For a positive integer $n$, $C_{1}(\mathbb{Q}^{n})=n+1$ in the following
cases:

  1. (i)

$n$ is even and $n+1$ is a perfect square.

  2. (ii)

$n\equiv 3\pmod{4}$.

  3. (iii)

$n\equiv 1\pmod{4}$ and $n+1$ is the sum of two squares.

Otherwise, $C_{1}(\mathbb{Q}^{n})=n$.

With access to Lemma 4.1, determining the maximum possible difference
$C_{1}(\mathbb{Q}^{n})-c_{1}(\mathbb{Q}^{n})$ is just an exercise in bounding
$c_{1}(\mathbb{Q}^{n})$ alone. This seems particularly relevant to our current
work, as any graph $G$ we hope to use in answering Question 1 must have
$\omega(G)\leq c_{1}(G)$.

###### Theorem 4.2

For any positive integer $n$, $C_{1}(\mathbb{Q}^{n})-c_{1}(\mathbb{Q}^{n})\leq
3$.

###### Proof.

For $n\leq 3$, we have $C_{1}(\mathbb{Q}^{n})\leq 4$ and
$c_{1}(\mathbb{Q}^{n})\geq 2$, so we may assume $n\geq 4$. Write $n=4m+k$ for
some $k\in\\{0,1,2,3\\}$. In the case of $k=0$, Lemma 3.5 gives
$C_{1}(\mathbb{Q}^{n})=c_{1}(\mathbb{Q}^{n})$, and so by applying Lemma 4.1,
we see that $C_{1}(\mathbb{Q}^{n})-c_{1}(\mathbb{Q}^{n})\leq 4$ for all $n$,
and the only situation which could possibly result in
$C_{1}(\mathbb{Q}^{n})-c_{1}(\mathbb{Q}^{n})=4$ is when
$\omega(\mathbb{Q}^{4m+3},d)=4m$ for some $d>0$. Without loss of generality,
we may assume $d=\sqrt{r}$ for some square-free positive integer $r$.

Let $P_{1},\ldots,P_{4m}\in\mathbb{Q}^{4m}$ such that $|P_{i}-P_{j}|=\sqrt{r}$
for each $i\neq j$. In other words, the points $P_{1},\ldots,P_{4m}$ form the
vertices of a copy of the complete graph $K_{4m}$ appearing as a subgraph of
$G(\mathbb{Q}^{4m},\sqrt{r})$. For each $i\in\\{1,\ldots,4m\\}$, extend
$P_{i}$ to a point $P_{i}^{\prime}\in\mathbb{Q}^{4m+3}$ by placing zeroes as
its last three coordinate entries. Suppose $P\in\mathbb{Q}^{4m+3}$ is a point
simultaneously at a distance $\sqrt{r}$ from each of
$P_{1}^{\prime},\ldots,P_{4m}^{\prime}$. One can imagine, especially after
sampling the arguments in the previous section, that the existence or non-
existence of such a point $P$ can be determined through analysis of a
corresponding Diophantine equation. Indeed, that is the case, as it was shown
in [2] (specifically, Theorem 3.6 of [2]) that the existence or non-existence
of $P$ can be decided by determining the solvability or insolvability,
respectively, in rationals, of the Diophantine equation given below.

$\frac{r(4m-1)}{8m}+2rmx^{2}+y^{2}+z^{2}+w^{2}=r$ (4.1)

Unfortunately, the authors of [2] failed to realize that Equation 4.1 is
solvable for all selections of $r,m\in\mathbb{Z}^{+}$. We will show this by
first rewriting it as the following Equation 4.2.

$y^{2}+z^{2}+w^{2}=\left(\frac{4rm+r}{8m}\right)-2rmx^{2}$ (4.2)

We now move to homogeneous coordinates in Equation 4.3, which has a non-
trivial solution in integers if and only if Equation 4.2 is solvable in
rationals.

$y^{2}+z^{2}+w^{2}=\left(\frac{4rm+r}{8m}\right)t^{2}-2rmx^{2}$ (4.3)

Set $t=4mt_{0}$, and note that Equation 4.3 is solvable if and only if
Equation 4.4 is.

$y^{2}+z^{2}+w^{2}=2rm[(4m+1){t_{0}}^{2}-x^{2}]$ (4.4)

Write $2rm=s\alpha^{2}$ where $s$ is square-free and let
$t_{0}=\frac{t_{1}}{\alpha}$, $x=\frac{x_{1}}{\alpha}$, and note that Equation
4.4 is solvable if and only if Equation 4.5 is.

$y^{2}+z^{2}+w^{2}=s[(4m+1){t_{1}}^{2}-{x_{1}}^{2}]$ (4.5)

Denote by $\gamma$ the right-hand side of this equation. By Gauss’
characterization of integers representable as a sum of three squares, to
guarantee that Equation 4.5 is solvable, we just need to select integers
$t_{1},x_{1}$ so that $\gamma$ is not of the form $4^{k}(8a+7)$ for non-
negative integers $a,k$. This can be done as follows. If $s\equiv 3\pmod{4}$,
select $t_{1}\equiv 0\pmod{4}$ and $x_{1}\equiv 1\pmod{4}$. This implies
$\gamma\equiv 1\pmod{4}$. If $s\equiv 1\text{ or }2\pmod{4}$, select
$t_{1}\equiv 1\pmod{4}$ and $x_{1}\equiv 0\pmod{4}$. This results in
$\gamma\equiv 1\pmod{4}$ or $\gamma\equiv 2\pmod{4}$, respectively. In each of
these cases, $\gamma$ is representable as a sum of three squares, and we have
Equation 4.5 being solvable. This concludes the proof of the theorem.∎∎

So, in a future attack on Question 1, one could view Theorem 4.2 as a starting
guideline for separating those graphs $G$ which merit consideration as being a
subgraph of $G(\mathbb{Q}^{n},d)$ from graphs which can immediately be set
aside. We also are led to believe that Lemma 3.3 may ultimately point the way
for all $n>5$. For $n\geq 6$ with $n\equiv 2\pmod{4}$, the complete
multipartite graph $G$ having $\frac{n}{2}$ parts of size 3 has $\dim(G)=n$
and is not in conflict with Theorem 4.2. We leave it open as to whether $G$ is
a subgraph of $G(\mathbb{Q}^{n},d)$ for all relevant $d$. For $n>5$ with $n$
odd, perhaps a case could be made for the complete multipartite graph having
$\frac{n-1}{2}$ parts of size 3 and one part of size 1.

## References

  * [1] N. Alon and A. Kupavskii, Two notions of unit distance graphs, J. Combin. Theory Ser. A 125 (1) (2014), 1 – 17.
  * [2] Sheng Bau, Peter Johnson, and Matt Noble, On single-distance graphs on the rational points in Euclidean spaces, Can. Math. Bull. (2020), 1 – 12, doi:10.4153/S0008439520000181.
  * [3] M. J. Beeson, Triangles with vertices on lattice points, Amer. Math. Monthly 99 (1992), 243 – 252.
  * [4] A. D. N. J. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28 (1) (2018), 18 – 31.
  * [5] P. Erdős, F. Harary, and W. T. Tutte, On the dimension of a graph, Mathematika 12 (1965), 118 – 122.
  * [6] P. Erdős and M. Simonovits, On the chromatic number of geometric graphs, Ars Combin. 9 (1980), 229 – 246.
  * [7] G. Exoo and D. Ismailescu, The chromatic number of the plane is at least 5: A new proof, Discrete Comput. Geom. (2019), https://doi.org/10.1007/s00454-019-00058-1
  * [8] M. J. H. Heule, Computing small unit-distance graphs with chromatic number 5, Geombinatorics 28 (1) (2018), 32 – 50.
  * [9] H. Maehara, On Euclidean dimension of a complete multipartite graph, Discrete Math. 72 (1988), 285 – 289.
  * [10] T. Nagell, Introduction to Number Theory, John Wiley & Sons, Inc., New York, 1951.
  * [11] I. J. Schoenberg, Regular simplices and quadratic forms, J. London Math. Soc. 12 (1937), 48 – 55.
  * [12] A. Soifer, The Mathematical Coloring Book, Springer, 2009.