# New bounds on the maximum number of neighborly boxes in $\mathbb{R}^{d}$

Noga Alon  Department of Mathematics, Princeton University, Princeton, NJ
08544, USA and Schools of Mathematics and Computer Science, Tel Aviv
University, Tel Aviv 69978, Israel<EMAIL_ADDRESS>,  Jarosław
Grytczuk  Faculty of Mathematics and Information Science, Warsaw University of
Technology, 00-662 Warsaw, Poland<EMAIL_ADDRESS>,  Andrzej P.
Kisielewicz  Wydział Matematyki, Informatyki i Ekonometrii, Uniwersytet
Zielonogórski, ul. Podgórna 50, 65-246 Zielona Góra, Poland
<EMAIL_ADDRESS>and  Krzysztof Przesławski  Wydział Matematyki,
Informatyki i Ekonometrii, Uniwersytet Zielonogórski, ul. Podgórna 50, 65-246
Zielona Góra, Poland<EMAIL_ADDRESS>
###### Abstract.

A family of axis-aligned boxes in $\mathbb{R}^{d}$ is _$k$ -neighborly_ if the
intersection of every two of them has dimension at least $d-k$ and at most
$d-1$. Let $n(k,d)$ denote the maximum size of such a family. It is known that
$n(k,d)$ can be equivalently defined as the maximum number of vertices in a
complete graph whose edges can be covered by $d$ complete bipartite graphs,
with each edge covered at most $k$ times.

We derive a new upper bound on $n(k,d)$, which implies, in particular, that
$n(k,d)\leqslant(2-\delta)^{d}$ if $k\leqslant(1-\varepsilon)d$, where
$\delta>0$ depends on arbitrarily chosen $\varepsilon>0$. The proof applies a
classical result of Kleitman, concerning the maximum size of sets with a given
diameter in discrete hypercubes. By an explicit construction we obtain also a
new lower bound for $n(k,d)$, which implies that
$n(k,d)\geqslant(1-o(1))\frac{d^{k}}{k!}$. We also study $k$-neighborly
families of boxes with additional structural properties. Families called
_total laminations_ , that split in a tree-like fashion, turn out to be
particularly useful for explicit constructions. We pose a few conjectures
based on these constructions and some computational experiments.

The first author was supported in part by NSF grant DMS-2154082 and BSF grant
2018267.

The second author was supported in part by Narodowe Centrum Nauki, grant
2020/37/B/ST1/03298.

##  1\. Introduction

Let $k,d$ be two positive integers, with $k\leqslant d$. A standard box in
$\mathbb{R}^{d}$ is a set of the form $K=K_{1}\times\cdots\times K_{d}$, where
$K_{i}\subset\mathbb{R}$ is a closed interval, for each $i\in[d]$, where
$[d]=\\{1,2,\ldots,d\\}$. Two standard boxes $K,L\subset\mathbb{R}^{d}$ are
k-neighborly if $d-k\leqslant{\rm dim}(K\cap L)\leqslant d-1$. A family
$\mathscr{F}$ of standard boxes is k-neighborly if every two boxes in
$\mathscr{F}$ are $k$-neighborly.

Let $n(k,d)$ be the maximum possible cardinality of a family $\mathscr{F}$ of
$k$-neighborly standard boxes in $\mathbb{R}^{d}$. In 1985 Zaks [10] proved
that $n(1,d)=d+1$ by relating the problem to the well-known theorem of Graham
and Pollak [6] on bipartite decompositions of complete graphs. It is also not
hard to demonstrate that $n(d,d)=2^{d}$. More generally, as explained in [1],
$n(k,d)$ is the maximum possible number of vertices in a complete graph that
can be covered by $d$ complete bipartite subgraphs (_bicliques_) so that every
edge is covered at least once and at most $k$ times. Using this
interpretation, the following general bounds were proved in [1]:

(1.1)
$\left(\frac{d}{k}\right)^{k}\leqslant\prod_{i=0}^{k-1}\left(\left\lfloor\frac{d+i}{k}\right\rfloor+1\right)\leqslant
n(k,d)\leqslant\sum_{i=0}^{k}2^{i}\binom{d}{i}<2\cdot(2e)^{k}\cdot\left(\frac{d}{k}\right)^{k}.$

An improvement of the upper bound, namely, $n(k,d)\leqslant
1+\sum_{i=1}^{k}2^{i-1}\binom{d}{i}$, was obtained by Huang and Sudakov in [7]
(see also [5] for a generalization). These upper bounds are not very far from
the lower bound for $k$ much smaller than $d$. For large $k$, however, the gap
is very large. In particular, for $k>0.23d$ and large $d$ these bounds are
larger than the trivial $2^{d}$ upper bound which holds for every $k\leqslant
d$.

In the present paper we give a new upper bound on $n(k,d)$, which improves the
above estimate if $k$ is close enough to $d$. It is stated in the following
theorem, where an easy lower bound on $n(k,d)$ is also included, for
comparison.

######  Theorem 1.

For every $1\leqslant k\leqslant d-1$,

(1.2) $n(k,d)\geqslant\sum_{i=0}^{\lfloor k/2\rfloor}{d\choose i}.$

For every $1\leqslant k\leqslant k+2t-2\leqslant d-1$, where $t$ is an
arbitrary positive integer,

(1.3) $n(k,d)\leqslant 2^{d-t}+\sum_{i=0}^{\lceil(k+2t-2)/2\rceil}{d\choose
i}.$

Two simple corollaries of the result above are the following.

######  Corollary 1.

For any $\varepsilon>0$ there is $\delta>0$ so that for any
$k\leqslant(1-\varepsilon)d$,

(1.4) $n(k,d)\leqslant(2-\delta)^{d}.$

######  Corollary 2.

If $d,k$ tend to infinity so that $d-k\mapsto\infty$ and $d-k=o(d^{2/3})$,
then

(1.5) $n(k,d)=(1+o(1))\sum_{i=0}^{\lfloor k/2\rfloor}{d\choose i}.$

Note that a special case of Corollary 2 gives that for any $k=d-s$ with $s$
tending to infinity and satisfying $s=o(d^{1/2})$, $n(k,d)=(1+o(1))2^{d-1}.$

The proof of Theorem 1 is quite simple, however, it relies on a fundamental
result of Kleitman [8] (conjectured by Erdős) concerning the maximum size of
sets with given diameter in a discrete hypercube (see Section 2). Actually, by
a more detailed analysis one may derive slightly more precise upper bounds on
$n(k,d)$ (see Subsection 2.7).

In Section 3 we present further results on neighborly families of boxes and
some consequences for the related problem of biclique coverings of complete
graphs. We will use there some observations stemmed from the proof of the
following fact, giving another precise value of the function $n(k,d)$.

######  Proposition 1.

For every $d\geqslant 2$ we have

(1.6) $n(d-1,d)=3\cdot 2^{d-2}.$

Let us remark that following the application of Kleitman’s theorem in the
study of this problem described in the first arXiv version of the present
paper, Cheng, Wang, Xu, and Yip [4] also obtained new upper bounds on
$n(k,d)$. For some values of parameters $k$ and $d$ their bounds are better
than ours. Interestingly, for small values of $d$ and $k$, they determined
exact values of $n(k,d)$ (see Table 2 and tables in [4]).

We also provide a general construction of $k$-neighborly families of boxes
which gives a substantial improvement of the existing lower bounds on
$n(k,d)$, for every fixed $k\geqslant 2$ and sufficiently large $d$.

######  Theorem 2.

Let $2\leqslant k\leqslant m\leqslant d$ be given integers such that
$d\geqslant\binom{m}{k}-1+m$. Then

(1.7)
$n(k,d)\geqslant\left(d-\binom{m}{k}+1\right)^{k}\cdot\frac{\binom{m}{k}}{m^{k}}.$

In consequence,

(1.8) $n(k,d)\geqslant(1-o(1))\frac{d^{k}}{k!}.$

For instance, for $k=2$ we get $n(2,d)\geqslant(1-o(1))\frac{d^{2}}{2}$, which
improves the previous lower bound, $n(2,d)\geqslant\frac{d^{2}}{4}$. As
mentioned earlier by Alon [1] and Huang and Sudakov [7], determining the
precise asymptotic order of $n(2,d)$ seems to be a hard task. In the final
section we pose a general conjecture which, together with the above lower
bound would imply that

$\lim_{d\rightarrow\infty}\frac{n(2,d)}{d^{2}}=\frac{1}{2}.$

However, as yet we do not even know whether the limit above exists.

##  2\. Proofs of the main results

###  2.1. Sets of maximum size and given diameter in the Hamming cube

Let $H^{d}=\\{0,1\\}^{d}$ denote the _Hamming cube_ of dimension $d$, that is,
the set of binary _strings_ of length $d$ representing the vertices of the
cube, with the _Hamming distance_ between two vertices defined by
$h(x,y)=|\\{i\in[d]\colon x_{i}\neq y_{i}\\}|$. Two strings $x,y\in H^{d}$ are
called _complementary_ if $x_{i}\neq y_{i}$ for all $i\in[d]$. For a subset
$A\subseteq H^{d}$, let $D(A)=\max\\{h(x,y)\colon x,y\in A\\}$ denote the
_diameter_ of $A$. By $B_{t}(x)\subseteq H^{d}$ we denote the _ball_ of radius
$t$ centered at $x\in H^{d}$. Notice that the size of $B_{t}(x)$ is equal to
$\sum_{i=0}^{t}\binom{d}{i}$, while the diameter $D(B_{t}(x))$ equals $2t$,
for $t<d/2$.

In 1961 Erdős conjectured that no set of diameter $2t\leqslant d-1$ in $H^{d}$
can have more points than the ball $B_{t}(x)$. This was confirmed by Kleitman
[8] in 1966. As observed by Bezrukov [3], a similar assertion holds for sets
of odd diameters, with an extremal example being formed of two balls
$B_{t}(x)\cup B_{t}(y)$ centered at any two points $x,y\in H^{d}$, with
$h(x,y)=1$. Bezrukov [3] also proved that there are no other extremal sets as
long as $k<d-1$. If $k=d-1$, then, by elementary reasoning, every extremal set
consists of exactly one element from every complementary pair.

######  Theorem 3 (Kleitman [8], Bezrukov [3]).

Let $A\subseteq H^{d}$ be a set of diameter $k\leqslant d-1$ and maximum size.
If $k=2t$, then

(2.1) $|A|\leqslant\sum_{i=0}^{t}\binom{d}{i}.$

If $k=2t+1$, then

(2.2) $|A|\leqslant\binom{d-1}{t}+\sum_{i=0}^{t}\binom{d}{i}.$

###  2.2. Neighborly boxes, bipartite coverings, and squashed cubes

Let $S=\\{0,1,\ast\\}$ be a set of symbols and let $S^{d}$ be the set of all
strings of length $d$ over $S$. The elements of $S^{d}$ can be interpreted as
vertices of the Hamming cube $H^{d}$ with some positions replaced by the new
symbol $\ast$, called _joker_. In this way, any string $x\in S^{d}$ defines a
subcube $H(x)$ of $H^{d}$, where $H(x)$ consists of all strings obtained by
changing all the jokers in $x$ to $0$ or $1$ in all possible ways. The number
of jokers in $x$, denoted as $j(x)$ is the dimension of the subcube $H(x)$,
and its cardinality is $2^{j(x)}$.

For, $x,y\in S^{d}$, let $d(x,y)$ denote the number of positions in which one
string has $0$ and the other has $1$. Note that if $d(x,y)\geqslant 1$, then
the subcubes $H(x)$ and $H(y)$ are pairwise disjoint. Note also that if the
dimension of $H(x)$ is $i$ and that of $H(y)$ is $j$, then any two binary
strings, $u\in H(x)$ and $v\in H(y)$, differ in at most $d(x,y)+i+j$
coordinates.

Another interpretation of strings in $S^{d}$ is connected to a special family
$\mathscr{S}^{d}$ of standard boxes formed of just three different intervals,
$[-1,0]$, $[0,1]$, and $[-1,1]$. Given such a box $K=K_{1}\times\cdots\times
K_{d}$, with $K_{i}$ being one of those three intervals, we may assign to it a
unique string $v(K)=v_{1}\cdots v_{d}$ in $S^{d}$ by the formula:

$v_{i}=\begin{cases}0,&\text{if $K_{i}=[-1,0]$},\\\ 1,&\text{if
$K_{i}=[0,1]$},\\\ \ast,&\text{if $K_{i}=[-1,1]$.}\end{cases}$

It is not hard to verify that two boxes $K,L\in\mathscr{S}^{d}$ are
$k$-neighborly if and only if the corresponding strings, $v(K)$ and $v(L)$,
differ on at least one, and on at most $k$ non-joker positions (in both
strings). In other words, if we add up the two strings $v(K)$ and $v(L)$ as
vectors, with additional rule that $i+\ast=\ast$, for each $i\in S$, then the
resulting string $v(K)+v(L)$ should have its number of $1$’s in the interval
$[1,k]$.

Moreover, it can be easily demonstrated that for every family $\mathscr{F}$ of
$k$-neighborly standard boxes in $\mathbb{R}^{d}$ there is an equivalent
family of boxes in $\mathscr{S}^{d}$ (preserving dimensions of all
intersections of members of the family $\mathscr{F}$). A detailed argument can
be found in [1]. Hence, the problem of determining the function $n(k,d)$ can
be reduced to families of boxes in $\mathscr{S}^{d}$ and studied through their
representing strings in $S^{d}$.

A connection between $S^{d}$ and bipartite coverings is obtained by assigning
to each vertex $v$ of a complete graph covered by $d$ bicliques with vertex
classes $(L_{i},R_{i})$, $1\leqslant i\leqslant d$, a string in $S^{d}$, whose
$i$-th coordinate is $0$ if $v\in L_{i}$, it is $1$ if $v\in R_{i}$ and it is
$*$ if $v\not\in L_{i}\cup R_{i}$. Therefore, $n(k,d)$ is the maximum possible
number of strings in a family $F\subseteq S^{d}$ so that $1\leqslant
d(x,y)\leqslant k$ holds for any two distinct $x,y\in F$.

###  2.3. Proof of Proposition 1

Let $\mathscr{F}$ be a family of $k$-neighborly boxes in $\mathscr{S}^{d}$,
or, equivalently, a family $F$ of strings in $S^{d}$ such that $1\leqslant
d(x,y)\leqslant k$, for each pair $x,y\in F$. Assume that the size of $F$ is
as large as possible. Denote by $F^{\ast}$ the subset of $F$ consisting of all
strings with at least one joker, and set $F_{0}=F\setminus F^{\ast}$.

As explained above, every string $x\in F$ corresponds to a subcube $H(x)$ of
$H^{d}$ whose dimension is exactly the number of jokers in $x$. Since every
pair of strings in $F$ differs on at least one non-joker position, these
subcubes are pairwise disjoint. Hence, the number of strings in $F^{\ast}$
cannot be greater than half of the total number of vertices spanned by the
corresponding subcubes. Consequently,

(2.3) $|F^{\ast}|\leqslant\frac{1}{2}\cdot|H^{d}\setminus F_{0}|.$

So, we may write

(2.4)
$|F|=|F_{0}|+|F^{\ast}|\leqslant|F_{0}|+\frac{1}{2}\cdot(2^{d}-|F_{0}|)=2^{d-1}+\frac{1}{2}\cdot|F_{0}|.$

Suppose now that $k=d-1$ and $F$ is a $k$-neighborly family. Then $F_{0}$
cannot contain any complementary pair of strings from $H^{d}$, and therefore
$|F_{0}|\leqslant\frac{1}{2}\cdot|H^{d}|=2^{d-1}$. In this way we get

(2.5) $|F|\leqslant 2^{d-1}+2^{d-2}=3\cdot 2^{d-2}.$

On the other hand, one may easily produce a family $F$ matching this upper
bound. For instance, one may take $F_{0}=\\{v\in H^{d}:v_{1}=0\\}$ and
$F^{*}=\\{x\in S^{d}:x_{1}=1,x_{2}=\ast,x_{3}\cdots x_{d}\in H^{d-2}\\}$,
which completes the proof. $\square$

###  2.4. Proof of Theorem 1

The proof of inequality (1.2) is very simple. Indeed, the family $F$ of all
binary strings of length $d$ in a Hamming ball of radius $\lfloor k/2\rfloor$
is a collection of $\sum_{i=0}^{\lfloor k/2\rfloor}{d\choose i}$ binary
strings. These can be viewed as strings in $S^{d}$ (containing no jokers). For
any two distinct $x,y\in F$, we have $1\leqslant d(x,y)\leqslant 2\lfloor
k/2\rfloor\leqslant k$, which implies (1.2).

The proof of inequality (1.3) is also short, by using Theorem 3. Let
$F\subseteq S^{d}$ be a family of strings so that for any two distinct $x,y\in
F$, we have $1\leqslant d(x,y)\leqslant k$. For each $i$, $1\leqslant
i\leqslant d$, let $F_{i}$ be the subset of $F$ consisting of all strings in
$F$ whose number of jokers is exactly $i$. Let $f_{i}=|F_{i}|$ be the
cardinality of $F_{i}$.

Since every subcube $H(x)$, for $x\in F_{i}$, contains $2^{i}$ points, and all
these subcubes are pairwise disjoint, it follows that

(2.6) $\sum_{i=0}^{d}2^{i}f_{i}\leqslant 2^{d}~{}~{}\mbox{and therefore, for
every}~{}~{}t,~{}~{}\sum_{i=t}^{d}f_{i}\leqslant 2^{d-t}.$

Fix a positive integer $t$ so that $k+2t-2<d$. For each $i$, $0\leqslant
i\leqslant t-1$, and for each $x\in F_{i}$, let $x^{\prime}$ be an arbitrary
binary string in $H(x)$. (For example, one can define $x^{\prime}$ to be the
string obtained from $x$ by replacing each of its jokers by $0$.) Then all
these strings $x^{\prime}$ corresponding to members
$x\in\bigcup_{i=0}^{t-1}F_{i}$ are distinct, and every two of them differ in
at most $k+2t-2$ positions. It thus follows from Theorem 3 that

(2.7)
$f_{0}+f_{1}+\ldots+f_{t-1}\leqslant\sum_{i=0}^{\lceil(k+2t-2)/2\rceil}{d\choose
i}.$

By (2.6) and (2.7), we obtain

$|F|=\sum_{i=0}^{d}f_{i}=(f_{0}+f_{1}+\ldots
f_{t-1})+\sum_{i=t}^{d}f_{i}\leqslant\sum_{i=0}^{\lceil(k+2t-2)/2\rceil}{d\choose
i}+2^{d-t},$

which gives the inequality (1.3). The proof is complete. $\square$

###  2.5. Proof of Corollary 1

In (1.3) of Theorem 1 choose $t=\frac{\varepsilon d}{4}$ and apply the
standard estimates for binomial distributions (cf., e.g., [2], Theorem A.1.13)
to conclude that the assertion of the corollary holds with
$\delta=\Omega(\varepsilon^{2})$.

###  2.6. Proof of Corollary 2

Put $k=d-s$. By assumption $d$ and $s$ tend to infinity, and $s=o(d^{2/3})$.
If $s\leqslant 10\sqrt{d}$, apply inequality (1.3) of Theorem 1, with $t=2\log
s$ (in fact any $t$ tending to infinity and satisfying $t=o(s)$ will do) to
obtain the desired result.

If $s\geqslant 10\sqrt{d}$ (and $s=o(d^{2/3})$), apply (1.3) of Theorem 1 with
$t=10s^{2}/d$. By assumption $t=o(d/s)$ and it is not difficult to verify that
this implies that

$\sum_{i=0}^{\lceil(k+2t-2)/2\rceil}{d\choose
i}=(1+o(1))\cdot\sum_{i=0}^{\lfloor k/2\rfloor}{d\choose i}.$

It is also not too difficult to check that with this choice of $t$,

$2^{d-t}=o\left(\sum_{i=0}^{\lfloor k/2\rfloor}{d\choose i}\right).$

The desired result follows by plugging these two inequalities in (1.3) of
Theorem 1. $\Box$

###  2.7. An estimation of $n(k,d)$ by a combination of sizes of maximal sets

Suppose that $F$ is a family of $k$-neighborly subcubes of $H^{d}$. Again, let
$F_{i}$ be the subfamily of $F$ that consists of all subcubes of dimension $i$
or less. Let $f_{j}$ be the number of all subcubes of dimension $j$ belonging
to $F$. Then the number of elements of $H^{d}$ covered by $F_{i}$ is equal
$f_{0}+2f_{1}+\cdots+2^{i}f_{i}$. Moreover, the Hamming distance between any
two such elements does not exceed $k+2i$.

Let $\kappa(s,d)$ denotes the maximum size of sets whose diameter is not
greater than $s$. In particular, $\kappa(s,d)=2^{d}$, for $s\geqslant d$. Then

$None$ $f_{0}+2f_{1}+\cdots+2^{i}f_{i}\leqslant\kappa(k+2i,d).$

A trivial constraint

$None$ $f_{0}+2f_{1}+\cdots+2^{d-1}f_{d-1}\leqslant 2^{d}.$

is identical with $(\kappa_{i})$ for $i=d-1$ and $k\geqslant 2$.

We want to bound from above $|F|=f_{0}+f_{1}+\ldots+f_{d-1}$. It can be
achieved by considering an integer optimization problem where the objective is
to maximize $f_{0}+f_{1}+\ldots+f_{d-1}$ subject to the constraints given by
$(\kappa_{i})$. Among all the optimal solutions, let us choose the one, say
$f_{0}=a_{0},\ldots,f_{d-1}=a_{d-1}$, which is maximal with respect to the
lexicographical order. We claim that it satisfies the following inequalities:

$None$ $\kappa(k+2i,d)<f_{0}+2f_{1}+\cdots+2^{i}f_{i}+2^{i},$

If not, let us choose $i=s$ for which ($\kappa^{+}_{i}$) does not hold. Then,
we can define a new sequence $(b_{i}\colon i=1,\ldots,d-1)$ as follows.

  * •

Let us set $b_{s}=a_{s}+1$, and let $t>s$ be the first index, if there is any,
for which $a_{t}>0$.

  * •

Let us set $b_{t}=a_{t}-1$, and for all the remaining indices $u$, let
$b_{u}=a_{u}$.

It is rather clear that since $(\kappa(k+2i,d)\colon i\leqslant d-1)$ is
increasing and $2^{s}<2^{t}$, the resulting sequence satisfies all the
constraints. Moreover, it also has to be optimal. On the other hand, it is
larger with respect to the lexicographical order, which is a contradiction.

Observe now that if $d-k$ is divisible by $2$, then plugging $i=\frac{d-k}{2}$
into $(\kappa^{+}_{i})$ gives us

$2^{d}<f_{0}+2f_{1}+\cdots+2^{\frac{d-k}{2}}f_{\frac{d-k}{2}}+2^{\frac{d-k}{2}},$

which readily implies, that $a_{j}=0$ for $j>{\frac{d-k}{2}}$. If $d-k$ is not
divisible by $2$, then plugging $i=\left\lfloor\frac{d-k}{2}\right\rfloor$
into $(\kappa^{+}_{i})$ and $(\kappa_{i})$ yields

$f_{0}+2f_{1}+\cdots+2^{\left\lfloor\frac{d-k}{2}\right\rfloor}f_{\left\lfloor\frac{d-k}{2}\right\rfloor}\leqslant\kappa(d-1,d)=2^{d-1}<f_{0}+2f_{1}+\cdots+2^{\left\lfloor\frac{d-k}{2}\right\rfloor}f_{\left\lfloor\frac{d-k}{2}\right\rfloor}+2^{\left\lfloor\frac{d-k}{2}\right\rfloor}.$

Since the sequence $f_{i}=a_{i}$ is maximal with respect to the
lexicographical order, and satisfies the constraints including ($\tau$), we
deduce that

$None$
$a_{\left\lfloor\frac{d-k}{2}\right\rfloor+1}=2^{d-\left\lfloor\frac{d-k}{2}\right\rfloor-2},$

and $a_{j}=0$ for $j>\left\lfloor\frac{d-k}{2}\right\rfloor+1$.

Now we are ready to estimate the optimal value of the objective function.
Suppose that $0\leq i-1<i\leqslant\frac{d-k}{2}$. Then, by
($\kappa^{+}_{i-1}$) and ($\kappa_{i}$), we obtain

$\kappa(k+2i,d)-\kappa(k+2(i-1),d)\geqslant 2^{i}a_{i}-2^{i-1}.$

Consequently,

$a_{i}<\frac{1}{2^{i}}\kappa(k+2i,d)-\frac{1}{2^{i}}\kappa(k+2(i-1),d)+\frac{1}{2}$

For $x\in\mathbb{R}$, let us denote $\lfloor x\rceil=\lceil x-1\rceil$. Since
$a_{i}$ is an integer, we have

$a_{i}\leqslant\left\lfloor\frac{1}{2^{i}}\kappa(k+2i,d)-\frac{1}{2^{i}}\kappa(k+2(i-1),d)+\frac{1}{2}\right\rceil.$

Suppose first that $k$ is even. Since, by Theorem 3,
$\kappa(s,d)=\sum_{j=0}^{\frac{s}{2}}\binom{d}{j}$, whenever $s<d$ and $s$ is
even, we have

$\kappa(k+2i,d)-\kappa(k+2(i-1),d)=\binom{d}{\frac{k}{2}+i}.$

Therefore,

$None$
$a_{i}\leqslant\left\lfloor\frac{1}{2^{i}}\binom{d}{\frac{k}{2}+i}+\frac{1}{2}\right\rceil\leqslant\frac{1}{2^{i}}\binom{d}{\frac{k}{2}+i}+\frac{1}{2},$

whenever $1\leqslant i<\frac{d-k}{2}$. If $i=\frac{d-k}{2}$, that is, also $d$
is even, then

$\kappa(k+2i,d)-\kappa(k+2(i-1),d)=\kappa(d,d)-\kappa(d-2,d)=2^{d}-\sum_{s=0}^{\frac{d-2}{2}}\binom{d}{s}=2^{d-1}+\frac{1}{2}\binom{d}{\frac{d}{2}}.$

Thus,

$None$ $a_{\frac{d-k}{2}}\leqslant\left\lfloor
2^{\frac{d+k}{2}-1}+\frac{1}{2^{\frac{d-k}{2}+1}}\binom{d}{\frac{d}{2}}+\frac{1}{2}\right\rceil.$

Suppose now that $k$ is odd. Since, by Theorem 3,
$\kappa(s,d)=\binom{d-1}{\left\lfloor\frac{s}{2}\right\rfloor}+\sum_{j=0}^{\left\lfloor\frac{s}{2}\right\rfloor}\binom{d}{j}$,
whenever $s<d$ and $s$ is odd, we have

$\displaystyle\kappa(k+2i,d)-\kappa(k+2(i-1),d)$ $\displaystyle=$
$\displaystyle\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i}-\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i-1}+\binom{d}{\left\lfloor\frac{k}{2}\right\rfloor+i}$
$\displaystyle=$ $\displaystyle
2\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i},$

whenever $1\leqslant i<\frac{d-k}{2}$. Therefore,

$None$
$a_{i}\leqslant\left\lfloor\frac{1}{2^{i-1}}\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i}+\frac{1}{2}\right\rceil\leqslant\frac{1}{2^{i-1}}\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i}+\frac{1}{2},$

whenever $1\leqslant i<\frac{d-k}{2}$. If $i=\frac{d-k}{2}$, that is, also $d$
is odd

$\kappa(k+2i,d)-\kappa(k+2(i-1),d)=2^{d}-\binom{d-1}{\left\lfloor\frac{d-2}{2}\right\rfloor}-\sum_{s=0}^{\left\lfloor\frac{d-2}{2}\right\rfloor}\binom{d}{s}=2^{d-1}+\binom{d-1}{\frac{d-1}{2}}.$

Thus,

$None$ $a_{\frac{d-k}{2}}\leqslant\left\lfloor
2^{\frac{d+k}{2}-1}+\frac{1}{2^{\frac{d-k}{2}}}\binom{d-1}{\frac{d-1}{2}}+\frac{1}{2}\right\rceil.$

If $k$ and $d$ are even, then summing up $a_{i}$, with respect to
$i=1,\ldots,\frac{d-k}{2}$ and bearing in mind that
$a_{0}\leqslant\kappa(k,d)$ by $(\eta)$ and $(\eta^{\prime})$ we obtain

(2.8)
$\begin{split}n(k,d)\leqslant&\sum_{i}a_{i}\leq\sum_{s=0}^{\frac{k}{2}}\binom{d}{s}+\sum_{i=1}^{\frac{d-k}{2}-1}\left\lfloor\frac{1}{2^{i}}\binom{d}{\frac{k}{2}+i}+\frac{1}{2}\right\rceil+\left\lfloor
2^{\frac{d+k}{2}-1}+\frac{1}{2^{\frac{d-k}{2}+1}}\binom{d}{\frac{d}{2}}+\frac{1}{2}\right\rceil\\\
\leqslant&\frac{d-k}{4}+2^{\frac{d+k}{2}-1}+\frac{1}{2^{\frac{d-k}{2}+1}}\binom{d}{\frac{d}{2}}+\sum_{s=0}^{\frac{k}{2}}\binom{d}{s}+\sum_{i=1}^{\frac{d-k}{2}-1}\frac{1}{2^{i}}\binom{d}{\frac{k}{2}+i}.\end{split}$

If $k$ is even and $d$ is odd, then taking into account $(\lambda)$ we get

(2.9)
$\begin{split}n(k,d)\leqslant&2^{d-\left\lfloor\frac{d-k}{2}\right\rfloor-2}+\sum_{s=0}^{\frac{k}{2}}\binom{d}{s}+\sum_{i=1}^{\left\lfloor\frac{d-k}{2}\right\rfloor}\left\lfloor\frac{1}{2^{i}}\binom{d}{\frac{k}{2}+i}+\frac{1}{2}\right\rceil\\\
\leqslant&\frac{1}{2}\left\lfloor\frac{d-k}{2}\right\rfloor+2^{d-\left\lfloor\frac{d-k}{2}\right\rfloor-2}+\sum_{s=0}^{\frac{k}{2}}\binom{d}{s}+\sum_{i=1}^{\left\lfloor\frac{d-k}{2}\right\rfloor}\frac{1}{2^{i}}\binom{d}{\frac{k}{2}+i}.\end{split}$

If $k$ is odd and $d$ is even, then by $(\omega)$, $(\lambda)$ and the
expression on $\kappa(k,d)$ we get

(2.10)
$\begin{split}n(k,d)\leqslant&2^{d-\left\lfloor\frac{d-k}{2}\right\rfloor-2}+\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor}+\sum_{s=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\binom{d}{s}+\sum_{i=1}^{\left\lfloor\frac{d-k}{2}\right\rfloor}\left\lfloor\frac{1}{2^{i-1}}\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i}+\frac{1}{2}\right\rceil\\\
\leqslant&\frac{1}{2}\left\lfloor\frac{d-k}{2}\right\rfloor+2^{d-\left\lfloor\frac{d-k}{2}\right\rfloor-2}+\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor}+\sum_{s=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\binom{d}{s}+\sum_{i=1}^{\left\lfloor\frac{d-k}{2}\right\rfloor}\frac{1}{2^{i-1}}\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i}.\end{split}$

If both $k$ and $d$ are odd, then we proceed similarly to the case $k$ and $d$
are even, however, we have to apply $(\omega)$ and $(\omega^{\prime})$ instead
of $(\eta)$ and $(\eta^{\prime})$:

(2.11)
$\begin{split}n(k,d)\leqslant&\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor}+\sum_{s=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\binom{d}{s}+\sum_{i=1}^{\frac{d-k}{2}-1}\left\lfloor\frac{1}{2^{i-1}}\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i}+\frac{1}{2}\right\rceil+\left\lfloor
2^{\frac{d+k}{2}-1}+\frac{1}{2^{\frac{d-k}{2}}}\binom{d-1}{\frac{d-1}{2}}+\frac{1}{2}\right\rceil\\\
\leqslant&\frac{d-k}{4}+\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor}+2^{\frac{d+k}{2}-1}+\frac{1}{2^{\frac{d-k}{2}}}\binom{d-1}{\frac{d-1}{2}}+\sum_{s=0}^{\left\lfloor\frac{k}{2}\right\rfloor}\binom{d}{s}+\sum_{i=1}^{\frac{d-k}{2}}\frac{1}{2^{i-1}}\binom{d-1}{\left\lfloor\frac{k}{2}\right\rfloor+i}.\end{split}$

###  2.8. Another way of getting the lower bound in (1.1)

We will prove a general result, which immediately implies the lower bound for
$n(k,d)$ given in [1].

######  Proposition 1.

Let $1\leqslant k_{i}\leqslant d_{i}$, $i=1,\ldots,s$, be given integers. Then

(2.12) $n(k_{1},d_{1})n(k_{2},d_{2})\cdots n(k_{s},d_{s})\leqslant
n(k_{1}+\cdots+k_{s},d_{1}+\cdots+d_{s}).$

###### Proof.

For two families $F\subseteq S^{d}$ and $G\subseteq S^{m}$, let
$FG=\\{uv\colon u\in F,v\in G\\}$ be the family of strings in $S^{d+m}$
consisting of all possible _concatenations_ of strings from $F$ and $G$.
Clearly, we have $|FG|=|F|\cdot|G|$. In case of singleton families $\\{v\\}$
we will write simply $vF$ instead of $\\{v\\}F$, and also $v^{m}$ for a
concatenation of $m$ copies of a string $v$.

Let $F_{i}$ denote a $k_{i}$-neighborly family of maximum size in $S^{d_{i}}$,
for $i=1,\ldots,s$. It is not hard to see that $F=F_{1}F_{2}\cdots F_{s}$ is a
$k$-neighborly family in $S^{d}$, where $k=k_{1}+\cdots+k_{s}$ and
$d=d_{1}+\cdots+d_{s}$, which proves the assertion. ∎

The lower bound for $n(k,d)$ in (1.1) may be derived now easily by applying
the trivial inequality $n(1,d)\geqslant d+1$ (which actually is an equality by
the Graham-Pollak Theorem). Indeed, put in the above result $s=k$, $k_{i}=1$,
and $d=d_{1}+\cdots+d_{k}$. Then

(2.13) $n(k,d)\geqslant n(1,d_{1})\cdots n(1,d_{k})=(d_{1}+1)\cdots(d_{k}+1).$

The last product is maximized when $d$ is partitioned most evenly into
summands $d_{i}$, which coincides with the product
$\prod_{i=0}^{k-1}\left(\left\lfloor\frac{d+i}{k}\right\rfloor+1\right)$.

###  2.9. Proof of Theorem 2

Let $k\leqslant m\leqslant d$ be fixed. Suppose that
$d=a_{1}+\cdots+a_{m}+\binom{m}{k}-1$, where $a_{i}$ are positive integers.
Let $\binom{[m]}{k}$ denote the set of all $k$-element subsets of $[m]$. For a
subset $B\in\binom{[m]}{k}$, denote $p_{B}=\prod_{i\in B}(a_{i}+1)$. We will
describe an explicit construction of a $k$-neighborly family of strings in
$S^{d}$ with exactly $\sum_{B\in\binom{[m]}{k}}p_{B}$ members.

Let $A_{i}\subseteq S^{a_{i}}$ be any $1$-neighborly family of size $a_{i}+1$,
for $i=1,\ldots,m$. For a fixed subset $B\in\binom{[m]}{k}$, consider a set
$R_{B}$ of strings in $S^{a_{1}+\cdots+a_{m}}$ defined by $R_{B}=X_{1}\cdots
X_{m}$, where $X_{i}=A_{i}$ if $i\in B$ and $X_{i}=\\{*^{a_{i}}\\}$,
otherwise. This construction can be described in words as follows. Split the
set $[a_{1}+\cdots+a_{m}]$ into consecutive intervals $I_{1},\ldots,I_{m}$ of
lengths $a_{1},\ldots,a_{m}$, respectively. Next, for each $i\in B$, fill the
interval $I_{i}$ with any string from $A_{i}$, while every other interval
$I_{j}$, fill up with jokers. Clearly, we have $|R_{B}|=p_{B}$. Moreover,
denoting $R=\bigcup_{B\in\binom{[m]}{k}}R_{B}$, we have
$|R|=\sum_{B\in\binom{[m]}{k}}p_{B}$, since no two constructed strings are the
same.

It is not hard to see that any two strings $u,v\in R_{B}$ satisfy $1\leqslant
d(u,v)\leqslant k$. Also, it is not hard to check that for any two different
subsets $B^{\prime}$ and $B^{\prime\prime}$ in $\binom{[m]}{k}$, and any
strings $u\in B^{\prime}$ and $v\in B^{\prime\prime}$, we must have
$d(u,v)\leqslant k-1$, though sometimes we may have $d(u,v)=0$. This last
obstacle may be easily fixed as follows.

Let $A$ be any $1$-neighborly family in $S^{\binom{m}{k}-1}$ of size
$\binom{m}{k}$. So, the elements of $A$ may be indexed by subsets $B$ in
$\binom{[m]}{k}$ as $v_{B}$. For each $B\in\binom{[m]}{k}$, we may now form a
new family $R^{\prime}_{B}=v_{B}R_{B}=\\{v_{B}x:x\in R_{B}\\}$ by appending
the string $v_{B}$ at the beginning of every string $x$ in $R_{B}$. Now, every
pair of strings $u,v\in R^{\prime}=\bigcup_{B\in\binom{[m]}{k}}R^{\prime}_{B}$
satisfies $1\leqslant d(u,v)\leqslant k$, which means that $R^{\prime}$ is
$k$-neighborly. This completes construction of a $k$-neighborly family with
the aforementioned size, as $|R^{\prime}|=|R|$.

It remains to demonstrate that choosing appropriate numbers
$a_{1},\ldots,a_{m}$, summing up to $t=d-\binom{m}{k}+1$, gives the asserted
lower bound. It is not hard to see that the product $p_{B}=\prod_{i\in
B}(a_{i}+1)$ becomes maximal when its terms are equal as possible. So, we may
assume that each $a_{i}$ satisfies $a_{i}\geqslant\lfloor t/m\rfloor$, which
implies that $a_{i}+1>t/m$, for all $i=1,\ldots,m$. In consequence, the
maximum value of $p_{B}$ is at least $(t/m)^{k}$. Hence, the maximal size of
the family $R^{\prime}$ is at least $\binom{m}{k}(t/m)^{k}$, which completes
the proof of the first part of the theorem.

The second part follows immediately by considering $m$ and $d$ tending to
infinity so that $\binom{m}{k}/d$ tends to zero. $\Box$

##  3\. Constructions and other results

###  3.1. Exemplary constructions

Let us illustrate the construction from the proof of Theorem 2 by a concrete
example. Our building blocks are $1$-neighborly families of strings of the
following basic form:

(3.1)
$C_{1}=\\{0,1\\},C_{2}=\\{00,01,1*\\},C_{3}=\\{000,001,01*,1**\\},\ldots.$

In general, $C_{d}$ arises from $C_{d-1}$ by appending $0$ at the beginning of
every existing string and adding $1**\cdots*$ to the collection. Clearly,
$C_{d}$ has size $d+1$ and is a maximal $1$-neighborly family in $S^{d}$.

Let us compute the lower bound for $n(2,7)$. By applying Proposition 1 (or
directly the lower bound from (1.1)), we find that $n(2,7)\geqslant
n(1,3)\cdot n(1,4)=4\cdot 5=20$. An explicit family of strings of that size is
$C_{3}C_{4}$.

However, we may get a better bound by the method from the proof of Theorem 2.
Indeed, taking $m=3$, we have $7-\binom{3}{2}+1=5$, which leads to $a_{1}=2$,
$a_{2}=2$, and $a_{3}=1$. The corresponding families of strings may be written
as

(3.2) $(00)(C_{2}C_{2}*),(01)(C_{2}**C_{1}),(1*)(**C_{2}C_{1}),$

while particular strings are obtained by substituting each symbol $C_{i}$ with
an arbitrary string from $C_{i}$. Thus, the sizes of these families are,
respectively, $3\cdot 3=9$, $3\cdot 2=6$, and $3\cdot 2=6$, which makes the
total size of their union equal to $9+6+6=21>20$.

Though this “fragmented” construction gives better results for $k=2$ than a
more direct one form Proposition 1, for bigger $k$ an opposite situation may
happen. Consider, for instance, the case of $n(3,10)$. Using the former
method, an optimal value for the lower bound is obtained by taking $m=4$ and
$a_{1}=a_{2}=a_{3}=2$, $a_{4}=1$, which gives four families of strings

(3.3)
$(000)(C_{2}C_{2}C_{2}*),(001)(C_{2}C_{2}**C_{1}),(01*)C_{2}**C_{2}C_{1},(1**)(**C_{2}C_{2}C_{1}),$

whose union has total size $3\cdot 3\cdot 3+(3\cdot 3\cdot 2)\cdot
3=27+54=81$. However, using Proposition 1 and the just computed lower bound
$n(2,7)\geqslant 21$, we get $n(3,10)\geqslant n(2,7)\cdot n(1,3)\geqslant
21\cdot 4=84>81$. This leads to the following definition.

Let $m(k,d)$ denote the maximum size of a $k$-neighborly family in $S^{d}$
that can be constructed as in the proof of Theorem 2. More explicitly,
$m(k,d)$ is the maximum value of the expression
$\sum_{B\in\binom{[m]}{k}}\prod_{i\in B}(a_{i}+1)$ over all $m$ and
$a_{1},\ldots,a_{m}$ such that $\binom{m}{k}+m-1\leqslant d$ and
$a_{1}+\cdots+a_{m}\leqslant d-\binom{m}{k}-1$. For instance, $m(3,10)=81$.
Clearly, we have $m(k,d)\leqslant n(k,d)$.

However, to take the advantage of construction from Proposition 1 that we have
seen, we define $\overline{m}(k,d)=\max\\{\prod_{i=1}^{s}m(k_{i},d_{i})\\}$,
where the maximum is taken over all pairs of partitions,
$k=k_{1}+\cdots+k_{s}$ and $d=d_{1}+\cdots+d_{s}$, with $1\leqslant
k_{i}\leqslant d_{i}$. For instance, we have $\overline{m}(3,10)=84$. Clearly,
we always have

$m(k,d)\leqslant\overline{m}(k,d)\leqslant n(k,d).$

We shall discuss some properties of these functions in the final section.

###  3.2. Partitions and laminations

In this subsection we present further observations on $k$-neighborly families
of boxes with additional structural properties. Staying in string terminology,
we shall somewhat rely on geometric intuitions.

For a given family $F\subseteq S^{d}$, let us define the quantity
$\operatorname{vol}(F)=\sum_{x\in F}2^{j(x)}$, where $j(x)$ is the number of
jokers in $x$. If $F$ is a $k$-neighborly family, then $\operatorname{vol}(F)$
is just the total number of elements of $H^{d}$ contained in the family of
subcubes $H(x)$, with $x\in F$. Clearly, we have then
$\operatorname{vol}(F)\leqslant 2^{d}$. Also notice that $2^{j(x)}$ is a real
geometric volume of the standard box in $\mathscr{S}^{d}$ corresponding to $x$
and $\operatorname{vol}(F)$ is the total sum of volumes of all standard boxes
corresponding to members in the family $F$.

We are interested below in those $k$-neighborly families $F$ having the
maximum possible volume, namely $\operatorname{vol}(F)=2^{d}$. They are simply
called _partitions_. We start with the following simple lemma.

######  Lemma 1.

Let $F\subseteq S^{d}$ be a $k$-neighborly family of maximum size. Then each
string in $F$ may have at most $d-k$ jokers.

###### Proof.

Suppose that there is a string $x\in F$ with $d-k+1$ jokers. Let $x^{(0)}$ and
$x^{(1)}$ be two strings obtained from $x$ by changing one chosen joker into
$0$ and $1$, respectively. Clearly, $d(x^{(0)},x^{(1)})=1$, and for every
$y\in F$, $y\neq x$, we still have $1\leqslant d(x^{(i)},y)\leqslant k$, for
both $i=0,1$. Hence, $F\setminus\\{x\\}\cup\\{x^{(0)},x^{(1)}\\}$ is a
strictly larger $k$-neighborly family, contrary to our assumption. ∎

######  Proposition 2.

Every $(d-1)$-neighborly family $F\subseteq S^{d}$ of maximum size is a
partition.

###### Proof.

Let $F_{0}$ and $F^{*}$ be as in the proof of Proposition 1. From this proof
we know that $|F_{0}|\leqslant 2^{d-1}$ and $|F_{0}|+|F^{*}|=2^{d-1}+2^{d-2}$.
By Lemma 1 we know that each string in $F^{*}$ has exactly one joker. It
follows that $|F_{0}|=2^{d-1}$ and $|F^{*}|=2^{d-2}$, and consequently,
$\operatorname{vol}(F)=2^{d}$. ∎

Our next results will have consequences for the opposite side of the scene,
namely, for at most $2$-neighborly families $F$. In order to state it we need
to introduce some notation and terminology.

For a given family of strings $F\subseteq S^{d}$, denote by $F^{i,s}$ a
subfamily having symbol $s\in S$ on the $i$-th position. A family $F\subseteq
S^{d}$ is called a _lamination_ if it is a partition
($\operatorname{vol}(F)=2^{d}$) and $F=F^{i,0}\cup F^{i,1}$, for some
$i\in[d]$. For $x\in S^{d}$, let ${\rm prop}(x)=\\{i\in[d]\colon
x_{i}\in\\{0,1\\}\\}$ be the set of non-joker positions in $x$. Also, let
$\operatorname{sgn}(x)=(-1)^{|\\{i\in[d]\colon x_{i}=1\\}|}$.

The following lemma is a special case of a more general result given in [9]
(Corollary 6.2).

######  Lemma 2.

Let $F\subseteq S^{d}$ be a partition and let $v\in F$ be a string with the
least number of jokers. Then, denoting $P_{v}=\\{x\in F\colon{\rm
prop}(x)={\rm prop}(v)\\}$, we have

(3.4) $\sum_{x\in P_{v}}{\rm sgn}(x)=0.$

###### Proof.

If ${\rm prop}(v)=[d]$, then the set of strings $F\setminus P_{v}$ can be
partitioned into edges of $\\{0,1\\}^{d}$ (strings with one joker). Thus, a
half of strings in $P_{v}$ contains an odd number of $1$’s, and the other half
an even number of $1$’s.

Let now $|{\rm prop}(v)|=k<d$. We may assume that $v=v_{1}\cdots
v_{k}*\cdots*$, where $v_{i}\in\\{0,1\\}$ for $i\in[k]$. Note that the set of
strings

$G=\\{w\in F:w_{i}\in\\{0,*\\}\;\;{\rm for}\;\;i\geqslant k+1\\}$

is a partition in dimension $k$. Moreover, the set
$P^{\prime}_{v}=\\{w_{1}\cdots w_{k}\colon w\in P_{v}\\}$ consists of all
strings in $G$ which do not contain jokers. Thus, by the first part of the
proof, the equality (3.4) holds. ∎

A pair of strings $x,y\in S^{d}$ is a _twin_ pair if $x_{i}+y_{i}=1$ for
precisely one $i\in[d]$ and $x_{j}=y_{j}$ for all $j\in[d]\setminus\\{i\\}$. A
_union_ $x\cup y$ of a twin pair $x,y$ is the string $z\in S^{d}$ such that
$z_{i}=*$ if $x_{i}+y_{i}=1$ and $z_{j}=x_{j}$ for all
$j\in[d]\setminus\\{i\\}$. In our geometric interpretation, a box
corresponding to $z$ is the union of boxes corresponding to $x$ and $y$.

Using the above lemma we prove that among $k$-neighborly families, with
$k\leqslant 2$, every partition is a lamination.

######  Proposition 3.

Let $F\subseteq S^{d}$ be a $k$-neighborly family, with $k\leqslant 2$. If $F$
is a partition, then $F$ is a lamination.

###### Proof.

Let $x\in F$ be a string with the least number of jokers. Since $k\leqslant
2$, by Lemma 2 there is $y\in F\setminus\\{x\\}$ such that $x,y$ is a twin
pair. Let $G=(F\setminus\\{x,y\\})\cup\\{x\cup y\\}$. Obviously, the partition
$G$ is still at most 2-neighborly and $|G|=|F|-1$. Continuing this process we
obtain the partition $P=\\{*\cdots*0*\cdots*,*\cdots*1*\cdots*\\}$, where
$0,1$ stand at some $i$th position. Then $F=F^{i,0}\cup F^{i,1}$. ∎

Let $v\in S^{d}$ be a string of length $d$. For $i\in[d]$, let
$v_{-i}=v_{1}\cdots v_{i-1}v_{i+1}\cdots v_{d}$ denote the result of deletion
of the $i$-th letter form $v$. More generally, for $F\subseteq S^{d}$ we write
$F_{-i}=\\{v_{-i}:v\in F\\}$. A _total lamination_ is defined recursively as
follows. For every $d\geqslant 1$, the $1$-element family consisting of a
string with only jokers, as well as the full Hamming cube $H^{d}$, are total
laminations. Next suppose that total laminations of dimensions up to $d-1$
have been already defined. Then a lamination $F\subseteq S^{d}$ is _total_ if
there is $i\in[d]$ such that $F=F^{i,0}\cup F^{i,1}$ and both families,
$F^{i,0}_{-i}$ and $F^{i,1}_{-i}$ are total laminations, too (see Fig. 1).

It is clear that the proof of Proposition 3 gives actually the following
stonger statement.

######  Corollary 3.

Every at most $2$-neighborly partition in $S^{d}$ is a total lamination.

A model example of a total lamination is a canonical $1$-neighborly family
$C_{d}$. Indeed, the family $C_{d}$ splits along the first coordinate into
$C_{d-1}$ and $\\{**\cdots*\\}$, which are both total laminations. For
example, $C_{3}=\\{000,001,01*,1**\\}$ splits into $C_{2}=\\{00,01,1\ast\\}$
and $\\{**\\}$. This implies that all neighborly families obtained by the
method based on Proposition 1 and Theorem 2 are total laminations, too.

Figure 1. Total laminations in dimension 3, $F=\\{001,101,\ast 11,\ast\ast
0\\}$ and $G=\\{0\ast 1,1\ast 1,\ast 00,\ast 10\\}$, with $|F|=|G|=n(1,3)$.

##  4\. Final comments

Let us conclude the paper with some open problems and suggestions for future
studies of the function $n(k,d)$.

######  Conjecture 1.

For every $1\leqslant k\leqslant d$, there exists a $k$-neighborly total
lamination $F$ in $S^{d}$ of size $n(k,d)$.

As mentioned above, the conjecture is trivially true for $k=1$ and $k=d$. By
the proof of Proposition 1 it is also true for $k=d-1$. The statement holds
also in all cases for which the exact value of $n(k,d)$ is known, except for
$n(6,8)=150$, where the only construction known to us is not a total
lamination. In Table 1 we collected initial lower bounds for $l(2,d)$ obtained
by computer experiments that improve upon the values of $m(2,d)$ (defined in
Subsection 3.1), for some initial dimensions $d$.

$d$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$m(2,d)=$ | 6 | 9 | 12 | 16 | 21 | 27 | 33 | 40 | 48 | 56 | 65 | 75 | 85 | 96 | 108 | 120
$l(2,d)\geqslant$ | 6 | 9 | 12 | 16 | 21 | 27 | 33 | 40 | 48 | 57 | 67 | 78 | 90 | 102 | 115 | 129
Table 1. The lower bounds for $l(2,d)\leqslant n(2,d)$ obtained by
constructions of total laminations compared to the function $m(k,d)\leqslant
n(2,d)$ arising from Theorem 2.

Total laminations have many nice structural properties. For instance, one may
produce out of any $k$-neighborly total lamination $F$ of dimension $d$ a
sequence of similar families with all possible sizes from $|F|$ down to $1$.
For example, to make a smaller family from $C_{3}$, take a twin pair
$(000,001)$ and substitute it by their union $000\cup 001=00*$. This gives a
new family $\\{00*,01*,1**\\}$, which is still a $1$-neighborly total
lamination. Repeating this step for the last family with a twin pair
$(00*,01*)$ gives $\\{0**,1**\\}$, which again is a $1$-neighborly total
lamination. In the same way we get $\\{***\\}$ in the final step. Thus, if
Conjecture 1 is true, then for every $(k,d)$ and every $1\leqslant p\leqslant
n(k,d)$ there is a $k$-neighborly total lamination of size $p$.

Though a general behavior of the function $n(k,d)$ is quite mysterious, even
for fixed $k$, we propose the following conjecture stating that the numbers
$n(k,d)$ satisfy a kind of “Pascal Triangle” property.

######  Conjecture 2.

For every $2\leqslant k\leqslant d$,

(4.1) $n(k,d)\leqslant n(k-1,d-1)+n(k,d-1).$

The conjecture is supported by the results of some computational experiments
performed on Gurobi solver, which are included in Table 2. One may also
consult a table with bounds for $n(k,d)$ in a recent paper [4]. A more
theoretical argument in favor of the conjecture stems from the following
proposition (whose simple proof is left to the reader).

######  Proposition 4.

For every $2\leqslant k\leqslant d$,

$\overline{m}(k,d)\leqslant\overline{m}(k-1,d-1)+\overline{m}(k,d-1).$

$d$ | 5 | 5 | 6 | 6 | 6 | 7 | 7 | 7 | 7 | 8 | 8 | 8 | 8 | 8
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$k$ | 2 | 3 | 2 | 3 | 4 | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 6
Alon | 12 | 18 | 16 | 27 | 36 | 20 | 36 | 54 | 72 | 25 | 48 | 81 | 108 | 144
Gurobi | 12 | 18 | 16 | 27 | 37 | 21* | 37* | 54 | 74 | 27** | 48* | 81* | 114 | 150
Table 2. Lower bounds for $n(k,d)$ computed by Gurobi solver (compared to the
lower bounds implied by (1.1)). The numbers marked with an asterisk may be
suboptimal solutions to the corresponding MIP problems, as computations have
not been successfully completed. The number marked with a double asterisk has
been determined separately. Bold numbers are exact values of $n(k,d)$, as
proved in [4].

Let us remark that Conjecture 2 has some consequences for the presumed
asymptotic properties of $n(k,d)$. In general, it seems plausible that the
following conjecture is true.

######  Conjecture 3.

For every fixed $k$, there exists a real number $g_{k}$ such that

(4.2) $\lim_{d\rightarrow\infty}\frac{n(k,d)}{d^{k}}=g_{k}.$

We know that $g_{1}=1$ by the Graham-Pollak Theorem. For $k\geqslant 2$ even
the existence of the limit is not known. However, from our Theorem 2 it
follows that $g_{k}\geqslant\frac{1}{k!}$ (assuming that $g_{k}$ exists). In
particular, $g_{2}\geqslant\frac{1}{2}$. Now, using the hypothetical Pascal-
Triangle inequality, we get that $g_{2}=\frac{1}{2}$. Indeed, by this
inequality we have $n(2,j)-n(2,j-1)\leqslant j$, for any $j\geqslant 3$.
Summing up these inequalities for $j=3,4,\ldots d$, we get that
$n(2,d)\leqslant 4+(3+4+\cdots+d)=(d+1)+\binom{d}{2}$. So,
${n(2,d)}/d^{2}\leqslant\frac{1}{2}+o(1)$.

## References

  * [1] N. Alon, Neighborly families of boxes and bipartite coverings, In: R. L. Graham at al. (eds.), The Mathematics of Paul Erdös II, pp 27–31, Springer-Verlag, Berlin Heidelberg, 1997.
  * [2] N. Alon and J. H. Spencer, The Probabilistic Method, Fourth Edition, Wiley, 2016, xiv+375 pp.
  * [3] S. L. Bezrukov, Specification of all maximal subsets of the unit cube with respect to given diameter, (in Russian), Problemy Peredachi Informatsii 23 (1987), 106–109.
  * [4] X. Cheng, M. Wang, Z. Xu, C. H. Yip, Exact values and improved bounds on $k$-neighborly families of boxes, arXiv:2301.06485.
  * [5] S. M. Cioabă, M. Tait, Variations on a theme of Graham and Pollak, Discrete Mathematics 313 (2013), 665–676.
  * [6] R. L. Graham and H. O. Pollak, On embedding graphs in squashed cubes, In: Lecture Notes in Mathematics 303, pp 99–110, Springer Verlag, New York-Berlin-Heidelberg, 1973.
  * [7] H. Huang and B. Sudakov, A counterexample to Alon-Saks-Seymour conjecture and related problems, Combinatorica 32 (2012), 205–219.
  * [8] D.J. Kleitman, On a Combinatorial Conjecture of Erdős, Journal of Combinatorial Theory 1 (1966), 209–214.
  * [9] A. P. Kisielewicz and K. Przesławski, Polyboxes, cube tilings and rigidity, Discrete Comput. Geom. 40 (2008), 1–30.
  * [10] J. Zaks, How Does a Complete Graph Split into Bipartite Graphs and How Are Neighborly Cubes Arranged?, Amer. Math. Monthly 92 (1985), 568–571.


# An Annotation Scheme for Reichenbach’s Verbal Tense Structure

Leon Derczynski  Robert Gaizauskas
Department of Computer Science
University of Sheffield, UK
<EMAIL_ADDRESS>
###### Abstract

In this paper we present RTMML, a markup language for the tenses of verbs and
temporal relations between verbs. There is a richness to tense in language
that is not fully captured by existing temporal annotation schemata. Following
Reichenbach we present an analysis of tense in terms of abstract time points,
with the aim of supporting automated processing of tense and temporal
relations in language. This allows for precise reasoning about tense in
documents, and the deduction of temporal relations between the times and
verbal events in a discourse. We define the syntax of RTMML, and demonstrate
the markup in a range of situations.

##  1 Introduction

In his 1947 account, Reichenbach offered an analysis of the tenses of verbs,
in terms of abstract time points. Reichenbach details nine tenses (see Table
1). The tenses detailed by Reichenbach are past, present or future, and may
take a simple, anterior or posterior form. In English, these apply to single
verbs and to verbal groups (e.g. _will have run_ , where the main verb is
_run_).

To describe a tense, Reichenbach introduces three abstract time points.
Firstly, there is the speech time, $S$. This represents the point at which the
verb is uttered or written. Secondly, event time $E$ is the time that the
event introduced by the verb occurs. Thirdly, there is reference time $R$;
this is an abstract point, from which events are viewed. In Example 1, speech
time $S$ is when the author created the discourse (or perhaps when the reader
interpreted it). Reference time $R$ is _then_ – an abstract point, before
speech time, but after the event time $E$, which is the leaving of the
building. In this sentence, one views events from a point in time later than
they occurred.

_By then, she had left the building._

While we have rich annotation languages for time in discourse, such as
TimeML111http://www.timeml.org; ?). and TCNL222See ?)., none can mark the time
points in this model, or the relations between them. Though some may provide a
means for identifying speech and event times in specific situations, there is
nothing similar for reference times. All three points from Reichenbach’s model
are sometimes necessary to calculate the information used in these rich
annotation languages; for example, they can help determine the nature of a
temporal relation, or a calendrical reference for a time. We will illustrate
this with two brief examples.

_By April 26 ${}^{\textrm{th}}$, it was all over._

In Example 1, there is an anaphoric temporal expression describing a date. The
expression is ambiguous because we cannot position it absolutely without an
agreed calendar and a particular year. This type of temporal expression is
interpreted not with respect to speech time, but with respect to reference
time [Ahn et al., 2005]. Without a time frame for the sentence (presumably
provided earlier in the discourse), we cannot determine which year the date is
in. If we are able to set bounds for $R$ in this case, the time in Example 1
will be the April $26^{th}$ adjacent to or contained in $R$; as the word _by_
is used, we know that the time is the April $26^{th}$ following $R$, and can
normalise the temporal expression, associating it with a time on an absolute
scale.

Temporal link labelling is the classification of relations between events or
times. We might say an event of _the airport closed_ occurred after another
event of _the aeroplane landed_ ; in this case, we have specified the type of
temporal relation between two events. This task is difficult to automate
[Verhagen et al., 2010]. There are clues in discourse that human readers use
to temporally relate events or times. One of these clues is tense. For
example:

_John told me the news, but I had already sent the letter._

Example 1 shows a sentence with two verb events – _told_ and _had sent_. Using
Reichenbach’s model, these share their speech time $S$ (the time of the
sentence’s creation) and reference time $R$, but have different event times.
In the first verb, reference and event time have the same position. In the
second, viewed from when John told the news, the letter sending had already
happened – that is, event time is before reference time. As reference time $R$
is the same throughout the sentence, we know that the letter was sent before
John mentioned the news. Describing $S$, $E$ and $R$ for verbs in a discourse
and linking these points with each other (and with times) is the only way to
ensure correct normalisation of all anaphoric and deictic temporal
expressions, as well as enabling high-accuracy labelling of some temporal
links.

Some existing temporal expression normalisation systems heuristically
approximate reference time. GUTime [Mani and Wilson, 2000] interprets the
reference point as “the time currently being talked about”, defaulting to
document creation date. Over 10% of errors in this system were directly
attributed to having an incorrect reference time, and correctly tracking
reference time is the only way to resolve them. TEA [Han et al., 2006]
approximates reference time with the most recent time temporally before the
expression being evaluated, excluding noun-modifying temporal expressions;
this heuristic yields improved performance in TEA when enabled, showing that
modelling reference time helps normalisation. HeidelTime [Strötgen and Gertz,
2010] uses a similar approach to TEA but does not exclude noun-modifying
expressions.

The recently created WikiWars corpus of TIMEX2 annotated text prompted the
comment that there is a “need to develop sophisticated methods for temporal
focus tracking if we are to extend current time-stamping technologies” [Mazur
and Dale, 2010]. Resources that explicitly annotate reference time will be
direct contributions to the completion of this task.

?) describe how to relate events based on a “perspective” which is calculated
from the reference and event times of an event pair. They construct a natural
language generation system that requires accurate reference times in order to
correctly write stories. ?) also found reference point management critical to
medical summary generation.

These observations suggest that the ability to automatically determine
reference time for verbal expressions is useful for a number of computational
language processing tasks. Our work in this area – in which we propose an
annotation scheme including reference time – is a first step in this
direction.

In Section 2 we describe some crucial points of Reichenbach’s model and the
requirements of an annotation schema for tense in natural language. We also
show how to reason about speech, event and reference times. Then, in Section
3, we present an overview of our markup. In Section 4 we give examples of
annotated text (fictional prose and newswire text that we already have another
temporal annotation for), event ordering and temporal expression
normalisation. Finally we conclude in Section 5 and discuss future work.

##  2 Exploring Reichenbach’s model

Each tensed verb can be described with three points; speech time, event time
and reference time. We refer to these as $S$, $E$ and $R$ respectively. Speech
time is when the verb is uttered. Event time is when the action described by
the verb occurs. Reference time is a viewpoint from where the event is
perceived. A summary of the relative positions of these points is given in
Table 1.

While each tensed verb involves a speech, event and reference time, multiple
verbs may share one or more of these points. For example, all narrative in a
news article usually has the same speech time (that of document creation).
Further, two events linked by a temporal conjunction (e.g. _after_) are very
likely to share the same reference time.

_Relation_ | _Reichenbach’s Tense Name_ | _English Tense Name_ | _Example_
---|---|---|---
E$<$R$<$S | Anterior past | Past perfect | _I had slept_
E=R$<$S | Simple past | Simple past | _I slept_
R$<$E$<$S | Posterior past |  | _I expected that .._
R$<$S=E |  |  | _I would sleep_
R$<$S$<$E |  |  |
E$<$S=R | Anterior present | Present perfect | _I have slept_
S=R=E | Simple present | Simple present | _I sleep_
S=R$<$E | Posterior present | Simple future | _I will sleep (Je vais dormir)_
S$<$E$<$R | Anterior future | Future perfect | _I will have slept_
S=E$<$R |  |  |
E$<$S$<$R |  |  |
S$<$R=E | Simple future | Simple future | _I will sleep (Je dormirai)_
S$<$R$<$E | Posterior future |  | _I shall be going to sleep_
Table 1: Reichenbach’s tenses; from ?)

From Table 1, we can see that conventionally English only distinguishes six
tenses. Therefore, some English tenses will suggest more than one arrangement
of $S$, $E$ and $R$. Reichenbach’s tense names suffer from this ambiguity too,
but to a much lesser degree. When following Reichenbach’s tense names, it is
the case that for past tenses, $R$ always occurs before $S$; in the future,
$R$ is always after $S$; and in the present, $S$ and $R$ are simultaneous.
Further, “anterior” suggests $E$ before $R$, “simple” that $R$ and $E$ are
simultaneous, and “posterior” that $E$ is after $R$. The flexibility of this
model permits the full set of available tenses [Song and Cohen, 1988], and
this is sufficient to account for the observed tenses in many languages.

Our goal is to define an annotation that can describe $S$, $E$ and $R$
(speech, event and reference time) throughout a discourse. The lexical
entities that these times are attached to are verbal events and temporal
expressions. Therefore, our annotation needs to locate these entities in
discourse, and make the associated time points available.

###  2.1 Special properties of the reference point

The reference point $R$ has two special uses. When sentences or clauses are
combined, grammatical rules require tenses to be adjusted. These rules operate
in such a way that the reference point is the same in all cases in the
sequence. Reichenbach names this principle permanence of the reference point.

Secondly, when temporal expressions (such as a TimeML TIMEX3 of type DATE, but
not DURATION) occur in the same clause as a verbal event, the temporal
expression does not (as one might expect) specify event time $E$, but instead
is used to position reference time $R$. This principle is named positional use
of the reference point.

###  2.2 Context and the time points

In the linear order that events and times occur in discourse, speech and
reference points persist until changed by a new event or time. That is, the
reference time from one sentence will roll over to the next sentence, until it
is repositioned explicitly by a tensed verb or time. To cater for subordinate
clauses in cases such as reported speech, we add a caveat – $S$ and $R$
persist as a discourse is read in textual order, for each context. We can
define a context as an environment in which events occur, such as the main
body of the document, reported speech, or the conditional world of an _if_
clause [Hornstein, 1990]. For example:

_Emmanuel had said “This will explode!”, but changed his mind._

Here, _said_ and _changed_ share speech and reference points. Emmanuel’s
statement occurs in a separate context, which the opening quote instantiates,
ended by the closing quote (unless we continue his reported speech later), and
begins with an $S$ that occurs at the same time as _said_ ’s $E$. This
persistence must be explicitly stated in RTMML.

###  2.3 Capturing the time points with TimeML

TimeML is a rich, developed standard for temporal annotation. There exist
valuable resources annotated with TimeML that have withstood significant
scrutiny. However TimeML does not address the issue of annotating
Reichenbach’s tense model with the goal of understanding reference time or
creating resources that enable detailed examination of the links between
verbal events in discourse.

Although TimeML permits the annotation of tense for <EVENT>s, it is not
possible to unambiguously map its tenses to Reichenbach’s model. This
restricts how well we can reason about verbal events using TimeML-annotated
documents. Of the usable information for mapping TimeML annotations to
Reichenbach’s time points, TimeML’s tense attribute describes the relation
between $S$ and $E$, and its aspect attribute can distinguish between
PERFECTIVE and NONE – that is, between $E<R$ and a conflated class of
$(E=R)\vee(R<E)$. Cases where $R<E$ are often awkward in English (as in Table
1), and may even lack a distinct syntax; the French _Je vais dormir_ and _Je
dormirai_ both have the same TimeML representation and both translate to _I
will sleep_ in English, despite having different time point arrangements.

It is not possible to describe or build relations to reference points at all
in TimeML. It may be possible to derive the information about $S$, $E$ and $R$
directly represented in our scheme from a TimeML annotation, though there are
cases – especially outside of English – where it is not possible to capture
the full nuance of Reichenbach’s model using TimeML. An RTMML annotation
permits simple reasoning about reference time, and assist the labelling of
temporal links between verb events in cases where TimeML’s tense and aspect
annotation is insufficient. This is why we propose an annotation, and not a
technique for deriving $S$, $E$, and $R$ from TimeML.

##  3 Overview of RTMML

The annotation schema RTMML is intended to describe the verbal event structure
detailed in ?), in order to permit the relative temporal positioning of
reference, event, and speech times. A simple approach is to define a markup
that only describes the information that we are interested in, and can be
integrated with TimeML. For expositional clarity we use our own tags but it is
possible (with minor modifications) to integrate them with TimeML as an
extension to the standard.

Our procedure is as follows. Mark all times and verbal events (e.g. TimeML
TIMEX3s and those EVENTs whose lexical realisation is a verb) in a discourse,
as $T_{1}..T_{n}$ and $V_{1}..V_{n}$ respectively. We mark times in order to
resolve positional uses of the reference point. For each verbal event $V_{i}$,
we may describe or assign three time points $S_{i}$, $E_{i}$, and $R_{i}$.
Further, we will relate $T$, $S$, $E$ and $R$ points using disjunctions of the
operators $<$, $=$ and $>$. It is not necessary to define a unique set of
these points for each verb – in fact, linking them across a discourse helps us
temporally order events and track reference time. We can also define a
“discourse creation time,” and call this $S_{D}$.

_John said, “Yes, we have left”._ If we let _said_ be $V_{1}$ and _left_ be
$V_{2}$:

$S_{1}=S_{D}$

From the tense of $V_{1}$ (simple past), we can say:

$R_{1}=S_{1}$

$E_{1}<R_{1}$

As $V_{2}$ is reported speech, it is true that:

$S_{2}=E_{1}$

Further, as $V_{2}$ is anterior present:

$R_{2}=S_{2}$

$E_{2}<R_{2}$

As the $=$ and $<$ relations are transitive, we can deduce an event ordering
$E_{2}<E_{1}$.

###  3.1 Annotation schema

The annotation language we propose is called RTMML, for Reichenbach Tense
Model Markup Language. We use standoff annotation. This keeps the text
uncluttered, in the spirit of _ISO LAF_ and _ISO SemAF-Time_. Annotations
reference tokens by index in the text, as can be seen in the examples below.
Token indices begin from zero. We explicitly state the segmentation plan with
the <seg> element, as described in ?) and _ISO DIS 24614-1 WordSeg-1_.

The general speech time of a document is defined with the <doc> element, which
has one or two attributes: an ID, and (optionally) @time. The latter may have
a normalised value, formatted according to TIMEX3 [Boguraev et al., 2005] or
TIDES [Ferro et al., 2005], or simply be the string now.

Each <verb> element describes a tensed verbal group in a discourse. The
@target attribute references token offsets; it has the form target="#token0"
or target="#range(#token7,#token10)" for a 4-token sequence. Comma-separated
lists of offsets are valid, for situations where verb groups are non-
contiguous. Every verb has a unique value in its @id attribute. The tense of a
verb group is described using the attributes @view (with values _simple_ ,
_anterior_ or _posterior_) and @tense (_past_ , _present_ or _future_).

The <verb> element has optional @s, @e and @r attributes; these are used for
directly linking a verb’s speech, event or reference time to a time point
specified elsewhere in the annotation. One can reference document creation
time with a value of doc or a temporal expression with its id (for example,
t1). To reference the speech, event or reference time of other verbs, we use
hash references to the event followed by a dot and then the character s, e or
r; e.g., v1’s reference time is referred to as #v1.r.

As every tensed verb always has exactly one $S$, $E$ and $R$, and these points
do not hold specific values or have a position on an absolute scale, we do not
attempt to directly annotate them or place them on an absolute scale. One
might think that the relations should be expressed in XML links; however this
requires reifying time points when the information is stored in the relations
between time points, so we focus on the relations between these points for
each <verb>. To capture these internal relations (as opposed to relations
between the $S$, $E$ and $R$ of different verbs), we use the attributes se, er
and sr. These attributes take a value that is a disjunction of $<$, $=$ and
$>$.

Time-referring expressions are annotated using the <timerefx> element. This
has an @id attribute with a unique value, and a @target, as well as an
optional @value which works in the same was as the <doc> element’s @time
attribute.

Relation name | Interpretation
---|---
positions | $T_{a}=R_{b}$
same_timeframe | $R_{a}=R_{b}[,R_{c},..R_{x}]$
reports | $E_{a}=S_{b}$
Table 2: The meaning of a certain link type between verbs or times a and b.

    <rtmml>
    Yesterday, John ate well.
     <seg type="token" />
     <doc time="now" />
     <timerefx xml:id="t1" target="
           #token0" />
     <verb xml:id="v1" target="#token3"
           view="simple" tense="past"
           sr=">" er="=" se=">"
           r="t1" s="doc" />
     </rtmml>

In this example, we have defined a time _Yesterday_ as t1 and a verbal event
_ate_ as v1. We have categorised the tense of v1 within Reichenbach’s
nomenclature, using the verb element’s @view and @tense attributes.

Next, we directly describe the reference point of v1, as being the same as the
time t1. Finally, we say that this verb is uttered at the same time as the
whole discourse – that is, $S_{v1}=S_{D}$. In RTMML, if the speech time of a
verb is not otherwise defined (directly or indirectly) then it is $S_{D}$. In
cases of multiple voices with distinct speech times, if a speech time is not
defined elsewhere, a new one may be instantiated with a string label; we
recommend the formatting _s_ , _e_ or _r_ followed by the verb’s ID.

This sentence includes a positional use of the reference point, annotated in
v1 when we say r="t1". To simplify the annotation task, and to verbosely
capture a use of the reference point, RTMML permits an alternative annotation
with the <rtmlink> element. This element takes as arguments a relation and a
set of times and/or verbs. Possible relation types are positions,
same_timeframe (annotating permanence of the reference point) and reports for
reported speech; the meanings of these are given in Table 2. In the above
markup, we could replace the <verb> element with the following:

    <verb xml:id="v1" target="#token3"
          view="simple" tense="past"
          sr=">" er="=" se=">" s="doc" />
    <rtmlink xml:id="l1" type="POSITIONS">
      <link source="#t1" />
      <link target="#v1" />
    </rtmlink>

When more than two entities are listed as targets, the relation is taken as
being between an optional source entity and each of the target entities.
Moving inter-verbal links to the <rtmlink> element helps fulfil _TEI p5_ and
the _LAF_ requirements that referencing and content structures are separated.
Use of the <rtmlink> element is not compulsory, as not all instances of
positional use or permanence of the reference point can be annotated using it;
Reichenbach’s original account gives an example in German.

###  3.2 Reasoning and inference rules

Our three relations $<$, $=$ and $>$ are all transitive. A minimal annotation
is acceptable. The $S$, $E$ and $R$ points of all verbs, $S_{D}$ and all $T$s
can represent nodes on a graph, connected by edges labelled with the relation
between nodes.

To position all times in a document with maximal accuracy, that is, to label
as many edges in such a graph as possible, one can generate a closure by means
of deducing relations. An agenda-based algorithm is suitable for this, such as
the one given in ?).

###  3.3 Integration with TimeML

To use RTMML as an ISO-TimeML extension, we recommend that instead of
annotating and referring to <timerefx>s, one refers to <TIMEX3> elements using
their tid attribute; references to <doc> will instead refer to a <TIMEX3> that
describes document creation time. The attributes of <verb> elements (except
xml:id and target) may be be added to <MAKEINSTANCE> or <EVENT> elements, and
<rtmlink>s will refer to event or event instance IDs.

##  4 Examples

In this section we will give developed examples of the RTMML notation, and
show how it can be used to order events and position events on an external
temporal scale.

###  4.1 Annotation example

Here we demonstrate RTMML annotation of two short pieces of text.

####  4.1.1 Fiction

From _David Copperfield_ by Charles Dickens: _When he had put up his things
for the night he took out his flute, and blew at it, until I almost thought he
would gradually blow his whole being into the large hole at the top, and ooze
away at the keys._

     <doc time="1850" mod="BEFORE" />
     <!-- had put -->
     <verb xml:id="v1"
       target="#range(#token2,#token3)"
       view="anterior" tense="past" />
     <!-- took -->
     <verb xml:id="v2" target="#token11"
       view="simple" tense="past" />
     <!-- blew -->
     <verb xml:id="v3" target="#token17"
       view="simple" tense="past" />
     <!-- thought -->
     <verb xml:id="v4" target="#token24"
       view="simple" tense="past" />
     <!-- would gradually blow -->
     <verb xml:id="v5"
       target="#range(#token26,#token28)"
       view="posterior" tense="past"
       se="=" er=">" sr=">"
       r="#v4.e" />
     <!-- ooze -->
     <verb xml:id="v6"
       target="#range(#token26,#token28)"
       view="posterior" tense="past"
       se="=" er=">" sr=">" />
     <rtmlink xml:id="l1"
       type="SAME_TIMEFRAME">
       <link target="#v1" />
       <link target="#v2" />
       <link target="#v3" />
       <link target="#v4" />
     </rtmlink>
     <rtmlink xml:id="l2"
       type="SAME_TIMEFRAME">
       <link target="#v5" />
       <link target="#v6" />
     </rtmlink>

Figure 1: RTMML for a passage from David Copperfield.

We give RTMML for the first five verbal events from Example 4.1.1 RTMML in
Figure 1. The fifth, v5, exists in a context that is instantiated by v4; its
reference time is defined as such. We can use one link element to show that
v2, v3 and v4 all use the same reference time as v1. The temporal relation
between event times of v1 and v2 can be inferred from their shared reference
time and their tenses; that is, given that v1 is anterior past and v2 simple
past, we know $E_{v1}<R_{v1}$ and $E_{v2}=R_{v2}$. As our <rtmlink> states
$R_{v1}=R_{v2}$, then $E_{v1}<E_{v2}$. Finally, v5 and v6 happen in the same
context, described with a second same_timeframe link.

####  4.1.2 Editorial news

From an editorial piece in TimeBank [Pustejovsky et al., 2003]
(AP900815-0044.tml): _Saddam appeared to accept a border demarcation treaty he
had rejected in peace talks following the August 1988 cease-fire of the eight-
year war with Iran._

     <doc time="1990-08-15T00:44" />
     <!-- appeared -->
     <verb xml:id="v1" target="#token1"
       view="simple" tense="past" />
     <!-- had rejected -->
     <verb xml:id="v2"
       target="#range(#token9,#token10)"
       view="anterior" tense="past" />
     <rtmlink xml:id="l1"
       type="SAME_TIMEFRAME">
       <link target="#v1" />
       <link target="#v2" />
     </rtmlink>

Here, we relate the simple past verb _appeared_ with the anterior past (past
perfect) verb _had rejected_ , permitting the inference that the first verb
occurs temporally after the second. The corresponding TimeML (edited for
conciseness) is:

    Saddam <EVENT eid="e74" class="I_STATE">
    appeared</EVENT> to accept a border
    demarcation treaty he had <EVENT eid="e77"
    class="OCCURRENCE">rejected</EVENT>

    <MAKEINSTANCE eventID="e74" eiid="ei1568"
     tense="PAST" aspect="NONE" polarity="POS"
     pos="VERB"/>
    <MAKEINSTANCE eventID="e77" eiid="ei1571"
     tense="PAST" aspect="PERFECTIVE"
     polarity="POS" pos="VERB"/>

In this example, we can see that the TimeML annotation includes the same
information, but a significant amount of other annotation detail is present,
cluttering the information we are trying to see. Further, these two <EVENT>
elements are not directly linked, requiring transitive closure of the network
described in a later set of <TLINK> elements, which are omitted here for
brevity.

###  4.2 Linking events to calendrical references

RTMML makes it possible to precisely describe the nature of links between
verbal events and times, via positional use of the reference point. We will
link an event to a temporal expression, and suggest a calendrical reference
for that expression, allowing the events to be placed on a calendar. Consider
the below text, from wsj_0533.tml in TimeBank.

_At the close of business Thursday, 5,745,188 shares of Connaught and C$44.3
million face amount of debentures, convertible into 1,826,596 common shares,
had been tendered to its offer._

     <doc time="1989-10-30" />
     <!-- close of business Thursday -->
     <timerefx xml:id="t1"
       target="#range(#token2,#token5)" />
     <!-- had been tendered -->
     <verb xml:id="v1"
       target="#range(#token25,#token27)"
       view="anterior" tense="past" />
     <rtmlink xml:id="l1" target="#t1 #v1">
       <link target="#t1" />
       <link target="#v1" />
     </rtmlink>

This shows that the reference time of v1 is t1. As v1 is anterior, we know
that the event mentioned occurred before _close of business Thursday_.
Normalisation is not a task that RTMML addresses, but there are existing
methods for deciding which Thursday is being referenced given the document
creation date [Mazur and Dale, 2008]; a time of day for _close of business_
may be found in a gazetteer.

###  4.3 Comments on annotation

As can be seen in Table 1, there is not a one-to-one mapping from English
tenses to the nine specified by Reichenbach. In some annotation cases, it is
possible to see how to resolve such ambiguities. Even if view and tense are
not clearly determinable, it is possible to define relations between $S$, $E$
and $R$; for example, for arrangements corresponding to the simple future,
$S<E$. In cases where ambiguities cannot be resolved, one may annotate a
disjunction of relation types; in this example, we might say “$S<R$ or $S=R$”
with sr="<=".

Contexts seem to have a shared speech time, and the $S-R$ relationship seems
to be the same throughout a context. Sentences which contravene this (e.g.
_“By the time I ran, John will have arrived”_) are rather awkward.

RTMML annotation is not bound to a particular language. As long as a
segmentation scheme (e.g. WordSeg-1) is agreed and there is a compatible
system of tense and aspect, the model can be applied and an annotation
created.

##  5 Conclusion and Future Development

Being able to recognise and represent reference time in discourse can help in
disambiguating temporal reference, determining temporal relations between
events and in generating appropriately tensed utterances. A first step in
creating computational tools to do this is to develop an annotation schema for
recording the relevant temporal information in discourse. To this end we have
presented RTMML, our annotation for Reichenbach’s model of tense in natural
language.

We do not intend to compete with existing languages that are well-equipped to
annotate temporal information in documents; RTMML may be integrated with
TimeML. What is novel in RTMML is the ability to capture the abstract parts of
tense in language. We can now annotate Reichenbach’s time points in a document
and then process them, for example, to observe interactions between temporal
expressions and events, or to track reference time through discourse. This is
not directly possible with existing annotation languages.

There are some extensions to Reichenbach’s model of the tenses of verbs, which
RTMML does not yet cater for. These include the introduction of a reference
interval, as opposed to a reference point, from ?), and Comrie’s suggestion of
a second reference point in some circumstances [Comrie, 1985]. RTMML should
cater for these extensions.

Further, we have preliminary annotation tools and have begun to create a
corpus of annotated texts that are also in TimeML corpora. This will allow a
direct evaluation of how well TimeML can represent Reichenbach’s time points
and their relations. To make use of Reichenbach’s model in automatic
annotation, given a corpus, we would like to apply machine learning techniques
to the RTMML annotation task. Work in this direction should enable us to label
temporal links and to anchor time expressions with complete accuracy where
other systems have not succeeded.

##  6 Acknowledgements

The authors would like to thank David Elson for his valuable comments. The
first author would also like to acknowledge the UK Engineering and Physical
Science Research Council’s support in the form of a doctoral studentship.

## References

  * [Ahn et al., 2005]  D. Ahn, S.F. Adafre, and MD Rijke.  2005\.  Towards task-based temporal extraction and recognition.  In Dagstuhl Seminar Proceedings, volume 5151.
  * [Boguraev et al., 2005]  B. Boguraev, J. Castano, R. Gaizauskas, B. Ingria, G. Katz, B. Knippen, J. Littman, I. Mani, J. Pustejovsky, A. Sanfilippo, et al.  2005\.  TimeML 1.2. 1: A Formal Specification Language for Events and Temporal Expressions.
  * [Comrie, 1985]  B. Comrie.  1985\.  Tense.  Cambridge University Press.
  * [Dowty, 1979]  D.R. Dowty.  1979\.  Word meaning and Montague grammar.  Kluwer.
  * [Elson and McKeown, 2010]  D. Elson and K. McKeown.  2010\.  Tense and Aspect Assignment in Narrative Discourse.  In Proceedings of the Sixth International Conference in Natural Language Generation.
  * [Ferro et al., 2005]  L. Ferro, L. Gerber, I. Mani, B. Sundheim, and G. Wilson.  2005\.  TIDES 2005 standard for the annotation of temporal expressions.  Technical report, MITRE.
  * [for Standardization, 2009a]  International Organization for Standardization.  2009a.  ISO DIS 24612 LRM - Language Annotation Framework (LAF).  ISO/TC 37/SC 4/WG 2.
  * [for Standardization, 2009b]  International Organization for Standardization.  2009b.  ISO DIS 24614-1 LRM - Word Segmentation of Text - Part 1: Basic Concepts and General Principles (WordSeg-1).  ISO/TC 37/SC 4/WG 2.
  * [for Standardization, 2009c]  International Organization for Standardization.  2009c.  ISO DIS 24617-1 LRM - Semantic Annotation Framework - Part 1: Time and Events (SemAF-Time).  ISO/TC 37/SC 4/WG 2.
  * [Han et al., 2006]  B. Han, D. Gates, and L. Levin.  2006\.  From language to time: A temporal expression anchorer.  In Temporal Representation and Reasoning (TIME), pages 196–203.
  * [Hornstein, 1990]  N. Hornstein.  1990\.  As time goes by: Tense and universal grammar.  MIT Press.
  * [Lee and Romary, 2010]  K. Lee and L. Romary.  2010\.  Towards Interoperability of ISO Standards for Language Resource Management.  In International Conference on Global Interoperability for Language Resources.
  * [Mani and Wilson, 2000]  I. Mani and G. Wilson.  2000\.  Robust temporal processing of news.  In Proceedings of the 38th Annual Meeting on ACL, pages 69–76. ACL.
  * [Mani et al., 2005]  I. Mani, J. Pustejovsky, and R. Gaizauskas.  2005\.  The language of time: a reader.  Oxford University Press, USA.
  * [Mazur and Dale, 2008]  P. Mazur and R. Dale.  2008\.  What’s the date?: high accuracy interpretation of weekday names.  In Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1, pages 553–560. ACL.
  * [Mazur and Dale, 2010]  P. Mazur and R. Dale.  2010\.  WikiWars: A New Corpus for Research on Temporal Expressions.  In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 913–922. ACL.
  * [Portet et al., 2009]  F. Portet, E. Reiter, A. Gatt, J. Hunter, S. Sripada, Y. Freer, and C. Sykes.  2009\.  Automatic generation of textual summaries from neonatal intensive care data.  Artificial Intelligence, 173(7-8):789–816.
  * [Pustejovsky et al., 2003]  J. Pustejovsky, P. Hanks, et al.  2003\.  The TimeBank corpus.  In Corpus Linguistics, volume 2003, page 40.
  * [Reichenbach, 1947]  H. Reichenbach.  1947\.  The Tenses of Verbs.  Elements of Symbolic Logic, pages 287–98.
  * [Setzer et al., 2005]  A. Setzer, R. Gaizauskas, and M. Hepple.  2005\.  The role of inference in the temporal annotation and analysis of text.  Language Resources and Evaluation, 39(2):243–265.
  * [Song and Cohen, 1988]  F. Song and R. Cohen.  1988\.  The interpretation of temporal relations in narrative.  In Proceedings of the 7th National Conference of AAAI.
  * [Strötgen and Gertz, 2010]  J. Strötgen and M. Gertz.  2010\.  HeidelTime: High quality rule-based extraction and normalization of temporal expressions.  In Proceedings of the 5th Workshop on Semantic Evaluation, pages 321–324. ACL.
  * [Verhagen et al., 2010]  M. Verhagen, R. Saurí, T. Caselli, and J. Pustejovsky.  2010\.  SemEval-2010 task 13: TempEval-2.  In Proceedings of the 5th Workshop on Semantic Evaluation, pages 57–62. ACL.