# Finding Relevant Points for Nearest-Neighbor Classification

David Eppstein Department of Computer Science, University of California,
Irvine. This research was performed in part through the 1st and 2nd Virtual
Workshops on Computational Geometry, organized in 2020 and 2021 by Erik
Demaine. We thank Erik and the other workshop participants for hosting these
events and for bringing our attention to these problems.

###### Abstract

In nearest-neighbor classification problems, a set of $d$-dimensional training
points are given, each with a known classification, and are used to infer
unknown classifications of other points by using the same classification as
the nearest training point. A training point is _relevant_ if its omission
from the training set would change the outcome of some of these inferences. We
provide a simple algorithm for thinning a training set down to its subset of
relevant points, using as subroutines algorithms for finding the minimum
spanning tree of a set of points and for finding the extreme points (convex
hull vertices) of a set of points. The time bounds for our algorithm, in any
constant dimension $d\geq 3$, improve on a previous algorithm for the same
problem by Clarkson (FOCS 1994).

##  1 Introduction

Nearest-neighbor classification is a widely-used supervised learning technique
in which, from training data consisting of geometric points with discrete
classifications, one infers the classification of new points as equal to the
classification of the nearest training point [18]. This technique has
motivated many important developments in exact and approximate nearest-
neighbor searching, including the construction of Voronoi diagrams [6, 13, 21,
27, 42], the development of point-location data structures for performing
queries in these diagrams [27, 38], quadtree-based data structures for
approximate nearest neighbors in spaces of moderate dimension [5, 4, 11, 24],
and locality-sensitive hashing for higher-dimensional data [29, 25, 19, 3].

Voronoi diagrams have high worst-case complexity even for spaces of moderate
dimensions: for $n$ points in $d$ dimensions, the Voronoi diagram can have
complexity $\Theta(n^{\lceil d/2\rceil})$ [20, 32, 39]. Approximate nearest-
neighbor searching data structures are better-behaved, but high-dimensional
classification problems using them still have a complexity only a small factor
faster than a naive scan of all training data for each new input point. To
speed up these methods, it is natural to consider a preprocessing stage that
reduces the training set to a smaller subset, its _relevant points_ , before
building these data structures [15, 7]. Here, we define a point to be relevant
if it is needed for correct nearest-neighbor classification: removing it would
change the nearest-neighbor classification of some points of $\mathbb{R}^{d}$.
Removing all points that are not relevant leaves all nearest-neighbor
classifications unchanged (see Theorem 1). Although this has no benefit in the
worst case, it is reasonable to expect that on average for smooth-enough input
distributions and smooth-enough decision boundaries (we leave those terms
deliberately vague and non-rigorous) a training set of $n$ points in $d$
dimensions may be reduced to a smaller subset of $O(n^{(d-1)/d})$ relevant
points, which could in some cases be a significant savings.

In this work we investigate a simple algorithm for quickly identifying which
points of a training set are relevant and which are not. Our algorithm is
_output-sensitive_ : it is faster when there are few relevant points, and
slower when there are many. It is based on the solutions to two previously-
studied geometric problems: the construction of Euclidean minimum spanning
trees, spanning trees for the complete graph on a given set of points,
weighted by the Euclidean distances between pairs of points, and the
identification of extreme points, the vertices of the convex hull of a given
set of points.

###  1.1 New results

Given a set of training points with discrete classifications (not assumed to
be binary nor in general position), our algorithm performs the following
steps, using a single Euclidean minimum spanning tree construction followed by
an extreme-point computation per relevant point. As we prove, it finds exactly
the set of relevant points.

######  Algorithm 1 (relevant points of a training set).

  1. 1.

Find a Euclidean minimum spanning tree $T$ of the training set.

  2. 2.

Find the edges in $T$ whose two endpoints have different classifications, and
initialize the set $R$ of relevant points to consist of the endpoints of these
edges.

  3. 3.

For each relevant point $r$ added to $R$ (either initially or within this
loop), perform the following steps:

    1. (a)

Invert through a unit sphere centered at $r$ all of the training points whose
classification differs from $r$, producing a point set $S_{r}$, including also
$r$ itself in $S_{r}$.

    2. (b)

Identify the extreme points of $S_{r}$.

    3. (c)

Add to $R$ the training points corresponding to extreme points of $S_{r}$.

Figure 1: The steps of Algorithm 1. Left: A training set in $\mathbb{R}^{2}$
with points classified as red, blue, and yellow, and its minimum spanning
tree, with the eight highlighted points identified as relevant because they
are endpoints of bichromatic edges. Right: The same training set, showing one
of the previously-identified relevant points $r$ (the single dark blue point),
the set $S_{r}$ (all dark points), the cell for $r$ in the Voronoi diagram of
$S_{r}$ (light blue shaded region), and the five Voronoi neighbors of $r$.
Three of those neighbors were already identified as relevant from the minimum
spanning tree; the other two neighbors, identified as relevant in the second
part of the algorithm, are highlighted.

The steps of the algorithm are illustrated in Fig. 1. The intuition behind
Algorithm 1 is that the minimum spanning tree phase of the algorithm finds a
piece of each component of the decision boundary, a wall between the Voronoi
cells of two relevant points. The extreme point phase finds the neighbors of
each relevant point in the Voronoi diagram of $S_{r}$, including the relevant
points that define neighboring walls of the decision boundary. In this way, it
expands each piece of boundary to the full component of the boundary, from
each wall to its adjacent walls in the component, without finding any false
positives, and without needing to know anything about the topology of the
boundary. The algorithm’s efficiency comes from output-sensitivity both in the
number of calls to the extreme-point subproblem and within the algorithms for
this subproblem. Both the Euclidean minimum spanning tree and the extreme-
point subproblem admit either simple and dimension-independent algorithms or
asymptotically faster but more dimension-specific and more complex algorithms,
but unfortunately we do not know of algorithms that are both simple and
optimally efficient. We analyze the same overall algorithm both ways, using
both kinds of algorithm for the subproblems. This analysis gives us the
following results:

  * •

Using simple algorithms, for an input of bounded dimension with $k$ relevant
points, we can identify the relevant points in time $O(n^{2}+k^{2}n)$. For an
input of unbounded dimension, we can identify the relevant points using
$O(kn)$ linear programs.

  * •

Using more complex subroutines for the Euclidean minimum spanning tree and
extreme points, we can identify the relevant points in randomized expected
time $O\bigl{(}(n\log n)^{4/3}+kn\log k\bigr{)}$ for three-dimensional points,
and in time

$O\left(n^{2-\frac{2}{\lceil
d/2\rceil+1}+\varepsilon}+k(nk)^{1-\frac{1}{\lfloor d/2\rfloor+1}}(\log
n)^{O(1)}\right).$

for $d$-dimensional points, for any $\varepsilon>0$. For instance, for $d=4$
this bound is $O(n^{4/3+\varepsilon}+k^{5/3}n^{2/3}\log^{O(1)}n)$, and for
$d=5$ it is $O(n^{3/2+\varepsilon}+k^{5/3}n^{2/3}\log^{O(1)}n)$.

The nearest-neighbor decision boundary, and not just the set of relevant
points, can be constructed as a sub-complex of the Voronoi diagram of the
relevant points, consisting of the $(d-1)$-dimensional faces of the diagram
that separate cells of opposite classifications. This construction can be
performed using standard Voronoi diagram construction algorithms [13] in an
additional time of $O(k\log k+k^{\lceil d/2\rceil})$, independently of $n$.
For all dimensions greater than two these time bounds are significantly faster
than the $O(n^{\lceil d/2\rceil})$ time that could be obtained by constructing
the Voronoi diagram directly and then using its faces to identify the
classification decision boundary.

We note that the set of relevant points found by Algorithm 1 is not
necessarily the smallest set of points that would have the same decision
boundary, or the smallest subset of the given points that would have the same
decision boundary. It is, rather, the set of all training points whose
omission from the whole data set (or from the resulting subset of relevant
points) would change the decision boundary. Finding the smallest set of points
with the same decision boundary, in high dimensions, seems likely to be a much
more difficult task.

###  1.2 Related work

The problem of constructing nearest-neighbor decision boundaries, in an
output-sensitive way, was considered by Bremner et al. [7], for the special
case of two-dimensional training data. They showed that, for training sets of
this dimension, the relevant points and their resulting nearest-neighbor
decision boundary can be found in time $O(n\log k)$.

In higher dimensions, the only work we are aware of for this problem is that
of Clarkson [15], who (in our terms) gave a simple algorithm for finding the
relevant points whose running time is $O\bigl{(}\min(n^{3},kn^{2}\log
n)\bigr{)}$ whenever the dimension is bounded. Our time bounds are
significantly faster than Clarkson’s in the cases for which this sort of
thinning is particularly useful, when $k$ is much smaller than $n$.

We will survey algorithms for the two subroutines we use, for Euclidean
minimum spanning trees and extreme points, in our discussion of these problems
in the next section.

##  2 Preliminaries

###  2.1 Voronoi diagrams and Delaunay graphs

The Voronoi diagram of a finite set $S$ of points in $\mathbb{R}^{d}$ (called
_sites_ in this context) is a collection of convex polyhedra (possibly
unbounded), one for each site site $s$, consisting of the points in
$\mathbb{R}^{d}$ for which $s$ is a nearest site, one with minimum Euclidean
distance to the point [6]. We call such a polyhedron the _cell_ of $s$. It is
an intersection of a finite system of halfspaces, the halfspaces that contain
$s$ and have as their boundaries the hyperplanes halfway between $s$ and each
other site. These hyperplanes are the perpendicular bisectors of line segments
connecting $s$ to each other site. For our purposes it is convenient to think
of the cells as closed sets, containing their boundaries, and intersecting
each other at shared boundary points. Their interiors, however, are disjoint.
The union of all the cells equals $\mathbb{R}^{d}$.

The Voronoi diagram has finitely many _faces_ , the intersections of finite
sets of cells. The dimension of a face is the dimension of its affine hull. We
define a _wall_ of the Voronoi diagram to be a face of dimension $d-1$, and a
_junction_ of the diagram to be a face of dimension $d-2$. The affine hull of
a junction, a $(d-2)$-dimensional subspace of $\mathbb{R}^{d}$, is
perpendicular to a family of two-dimensional planes. If we choose a plane in
this family that intersects the junction in its relative interior, a point
that is not part of any lower-dimensional face, then the junction will appear
in this intersection as a point, and in a neighborhood of this point the walls
that include the junction will appear as rays and the cells that include the
junction will appear as convex wedges between these rays. The geometry of this
structure of rays and wedges does not depend on the choice of intersecting
plane. It is called the _link_ of the junction. If the sites are in general
position (no $d+2$ of them belonging to a common sphere) then the link of a
junction will only have three rays and three wedges, but we do not wish to
assume general position.

We define the _Delaunay graph_ of a set of sites to be a graph having the
sites as vertices, with edges connecting pairs of sites when their cells
intersect in a wall. We do not include edges for pairs of sites whose cells
have a lower-dimensional or empty intersection. For sites in general position,
this graph forms the set of edges of a simplicial complex, the _Delaunay
triangulation_ , but again we do not wish to make this general position
assumption.

###  2.2 Euclidean minimum spanning trees

A Euclidean minimum spanning tree of a set $S$ of point sites is just a
minimum spanning tree of a complete graph, having $S$ as its vertices, with
edges weighted by Euclidean distance. We allow equal distances, in which case
there may be more than one possible minimum spanning tree. If there are $n$
sites, a minimum spanning tree can be constructed easily by naive algorithms
in time $O(n^{2})$ [23]: simply construct the weighted complete graph, and
apply either Borůvka’s algorithm or Jarník’s algorithm (with an unordered list
as priority queue), both of which take time $O(n^{2})$ for dense graphs.

For points in $\mathbb{R}^{2}$, a standard and more efficient method of
constructing a Euclidean minimum spanning tree is to construct the Delaunay
triangulation of the points (perturbed if necessary to be in general
position), which is guaranteed to contain a minimum spanning tree as a
subgraph [41], and then apply a planar graph minimum spanning tree algorithm
to the resulting graph. This method provides no advantage for worst-case
analysis in higher dimensions, as the Delaunay graph can be complete [42], but
we need the following related lemma for the correctness of Algorithm 1:

######  Lemma 1.

For an arbitrary finite set $S$ of sites in $\mathbb{R}^{d}$, any Euclidean
minimum spanning tree of the sites is a subgraph of the Delaunay graph of the
sites.

###### Proof.

Consider any minimum spanning tree edge $pq$, and let $r$ be the midpoint of
the edge between sites $p$ and $q$. Then $r$ is equidistant from $p$ and $q$.
If any other site $s$ were not strictly farther than $r$, then (by the
triangle inequality) $ps$ and $qs$ would both be shorter than $pr$, allowing
the tree to be made shorter by replacing edge $pq$ by $ps$ or $qs$ (whichever
is not already in the tree). Because we are assuming the tree to be minimum,
shortening it is not possible, so all other sites must be strictly farther
from $r$.

Let $r^{\prime}$ be obtained by perturbing $r$ by a small amount in any
direction perpendicular to $pq$; this perturbation preserves the property that
$r^{\prime}$ is equidistant from $p$ and $q$ and farther from all other sites.
Therefore, $r^{\prime}$ lies on a wall between the cells for $p$ and $q$, and
edge $pq$ is also an edge of the Delaunay graph. ∎

Instead, specialized higher-dimensional Euclidean minimum spanning tree
algorithms proceed by reducing the problem to a collection of bichromatic
closest pair problems, in which one must find the closest red–blue pair among
a collection of red and blue points, combining the resulting pairs into a
graph, and applying a graph minimum spanning tree algorithm to this graph.
Several reductions from Euclidean minimum spanning trees to bichromatic
closest pairs have been given but for the known time bounds for bichromatic
closest pairs these reductions all have the same efficiency [1, 8, 33]. Based
on this approach, the following results are known [1]:111Agarwal et al. [1]
state the time bound for high-dimensional Euclidean minimum spanning trees as
a randomized expected time bound, but in later related work such as [2] they
observe that the need for randomness can be eliminated using techniques from
[34].

######  Lemma 2.

A 3-dimensional Euclidean minimum spanning tree of $n$ points can be computed
in randomized expected time $O\bigl{(}(n\log n)^{4/3}\bigr{)}$. A
$d$-dimensional Euclidean minimum spanning tree can be computed by a
deterministic algorithm in time

$O\left(n^{2-\frac{2}{\lceil d/2\rceil+1}+\varepsilon}\right)$

for any $\varepsilon>0$.

When the dimension is not constant, these methods fail to improve on the
quadratic time of the naive algorithms. More strongly, for any
$\varepsilon>0$, the strong exponential time hypothesis implies that closest
pairs and therefore also Euclidean minimum spanning trees of dimension
polylogarithmic in $n$ (with the polylogarithm depending on $\varepsilon$)
cannot be found in time $O(n^{2-\varepsilon})$ [30].

###  2.3 Extreme points

The _extreme points_ of a finite set $S$ of points are the vertices of its
convex hull, or equivalently the points that are on the boundary of a
halfspace in which all other points of $S$ are interior.222See, for instance,
[26], p. 35, where this equivalence is stated in the form that the extreme
points and exposed points of a convex polytope coincide. Testing whether a
given point $p$ is extreme can be formulated as a linear programming
feasibility problem in which we seek a vector $v$ for which $v\cdot p>v\cdot
q$ for all other points $q$ in $S$. The point $p$ is extreme if and only if
such a vector $v$ exists.

The dimension $d$ equals the number of variables in this linear program.
Therefore, when $d$ is bounded, we can apply algorithms for low-dimensional
linear programming, which are strongly polynomial and take linear time when
the dimension is bounded, with exponential or subexponential dependence on the
dimension [36, 22, 40, 16, 35, 12]. One particularly simple choice here is
Seidel’s algorithm, which considers the constraints of the given program in a
random order, maintaining the optimal solution for the constraints seen so
far, and when finding a violated constraint recurses within the subspace of
one lower dimension in which that constraint is tight [40].

Thus, one simple way of finding all of the extreme points is to apply this
linear programming approach to each point individually. However, this can be
improved by the following method:

######  Algorithm 2 (simple algorithm for extreme points [15, 9, 37]).

  1. 1.

Initialize the set $E$ of extreme points to the empty set.

  2. 2.

For each input point $p$, in an arbitrary order, perform the following steps:

    1. (a)

Use the linear program outlined above to test to test whether $p$ is extreme
for $E\cup\\{p\\}$ and find a vector $v$ whose dot product with $v$ exceeds
the dot product with any point in $E$.

    2. (b)

If $p$ is not extreme for $E\cup\\{p\\}$ ($v$ does not exist) go on to the
next point in the outer loop.

    3. (c)

Otherwise, find the training point $p^{\prime}$ that maximizes $v\cdot
p^{\prime}$, breaking ties lexicographically by the coordinates of the
training points, and add $p^{\prime}$ to $E$.

Each iteration of the outer loop that reaches step (c) identifies a new
extreme point. Thus, all extreme points are identified using $n$ linear
programs of size $O(k)$, plus $k$ extreme-point searches of size $n$, in total
time $O(kn)$ in bounded dimensions. We omit some details and any proof of
correctness, for which see the references for this algorithm [15, 9, 37]. This
$O(kn)$ time bound can be further improved at the cost of greater algorithmic
complexity. When the dimension is two or three, and $k$ of the $n$ given
points are extreme, one can find all the extreme points in time $O(n\log k)$
using an output-sensitive algorithm for the convex hull, as (by Euler’s
polyhedral formula) the number of extreme points and convex hull complexity
are always within a constant factor of each other [31, 17, 14, 10]. In higher
dimensions, Chan [10] gives a time bound for this problem of

$O\left(n(\log k)^{O(1)}+(nk)^{1-\frac{1}{\lfloor d/2\rfloor+1}}(\log
n)^{O(1)}\right).$

###  2.4 Inversion and polar duality

An _inversion_ through a sphere $S$ in Euclidean space $\mathbb{R}^{d}$ is a
transformation that maps points (other than the center of the circle) to other
points. Each point and its transformed image lie on a common ray from the
center of the circle, and the product of their distances from the center
equals the squared radius of the circle. These transformations preserve
cocircularity of the transformed points, but not other properties such as
distances. _Polarity_ is a different kind of transformation, again defined by
a sphere in $\mathbb{R}^{d}$, that associates points (other than the center of
the sphere) with hyperplanes (not through the center of the sphere) and vice
versa. The point associated with a hyperplane $H$ can be found by finding the
point $p$ that belongs to $H$ and is nearest to the center of the sphere, and
then inverting $p$ through the sphere. Reversing these steps, the hyperplane
associated with a point $p$ is the hyperplane through the inverted image of
$p$, perpendicular to the line through $p$ and the center of the sphere. Both
inversion and polarity are illustrated in Fig. 2.

Figure 2: Inverse pairs of points with respect to a circle (left), and polar
pairs of points and lines with respect to a circle (right).

We can choose a Cartesian coordinate system for which the given sphere is the
unit sphere centered at the origin. Under these coordinates, if $p$ is a point
and $q$ is the polar image of a hyperplane $H$, then $p$ lies on $H$ if and
only if $p\cdot q=1$. If the dot product is less than one, $p$ lies on the
same side of $H$ as the origin, and if the dot product is greater than one,
$p$ lies on the far side of $H$ from the origin. Because the dot product is a
commutative operation, the operation of polarity (taking $p$ to a hyperplane
and $H$ to the point $q$) preserves incidence and sidedness.

The inversions performed in our algorithm for finding relevant points can
alternatively be thought of as polarities, with the inverted image of each
site representing the polar image of the hyperplane equidistant between it and
the chosen relevant point $r$. We can formalize this intuition in the
following lemma:

######  Lemma 3.

Let $P=\\{p_{1},p_{2},\dots\\}$ be a set of points, let $r$ be a point not
belonging to $P$, and let $Q=\\{q_{1},q_{2},\dots\\}$ be the set of points
obtained by inverting $P$ through a sphere centered at $r$, with corresponding
indexes. Then $q_{i}$ is extreme in $Q\cup\\{r\\}$ if and only if the cells
for $p_{i}$ and $r$ share a wall in the Voronoi diagram of $P\cup\\{r\\}$.

###### Proof.

Consider any particular point $q_{i}$, for which we wish to prove the
statement of the lemma. Scaling the radius of the sphere of inversion scales
$Q\cup\\{r\\}$ but does not change the property of being extreme, so the
choice of radius is irrelevant to the truth of the lemma. Therefore, without
loss of generality, we may assume that the radius is such that the polar
hyperplane of $q_{i}$ (for a different sphere of unit radius centered at $r$)
is exactly the wall $W_{i}$ of the two-point Voronoi diagram of
$\\{r,p_{i}\\}$.

If $q_{i}$ is extreme, there is a hyperplane $H$ passing through it, with all
of the other points in $Q\cup\\{r\\}$ on a single side of $H$. Let $h$ be the
polar of $H$; then $h$ lies on $W_{i}$, so it is equidistant from $r$ and
$p_{i}$. By the preservation of sidedness of polarity, $h$ lies on the same
side as $r$ of each wall $W_{j}$ for $j\neq i$, so it is farther from all the
other points $p_{j}$ than it is from $r$ and from $p_{i}$. Because it is
equidistant from $r$ and $p_{i}$ and farther from all the other sites of the
Voronoi diagram, it witnesses the existence of a Voronoi wall between $r$ and
$p_{i}$ in the full Voronoi diagram.

In the opposite direction, if the cells for $p_{i}$ and $r$ share a wall in
the Voronoi diagram of $P\cup\\{r\\}$, let $h$ be a point in the relative
interior of that wall, and let $H$ by the hyperplane polar to $h$. Because $h$
is equidistant from $r$ and $p_{i}$, and farther from all of the other points
$p_{j}$, $h$ is on the same side as $r$ of each wall $W_{j}$. By the
preservation of sidedness of polarity, point $q_{i}$ lies on $H$, with all
other points $q_{j}$ on the same side as $r$ of $H$, so $H$ witnesses the fact
that $q_{i}$ is extreme in $Q\cup\\{r\\}$. ∎

###  2.5 Binary homology

Figure 3: The Voronoi diagram of a training set in the form of a $5\times 10$
grid, with its six decision components (R1, R2, R3, R4, B1, and B2) labeled in
their upper left Voronoi cells. Decision component B1 has two decision
boundary components: the one highlighted, between B1, R1, R2, and R4, and a
second boundary component between B1 and R3. The highlighted decision boundary
component is itself a boundary, of B1${}\cup{}$R3 or of its complement.

Although Algorithm 1 itself is ignorant of topology, we need some basics for
its correctness proof. Specifically, we use mod-2 homology, as described e.g.
by [28]. This theory applies to a wide class of cell complexes, but we do not
need to define this class carefully, because we will only apply this form of
homology to the finite convex subdivisions of $\mathbb{R}^{d}$ obtained as
Voronoi diagrams of finite point sets.

If $S$ is any set, the family of all subsets of $S$ forms a
$\mathbb{Z}_{2}$-vector space with the symmetric difference of sets as its
vector addition operation. Subsets of the $k$-dimensional faces of a
polyhedral decomposition of space (such as a Voronoi diagram) are called
$k$-chains. For each $k$, the $k$-chains can be mapped to $(k-1)$-chains by
the _boundary map_ $\partial_{k}$, which takes a single $k$-face to the
$(k-1)$-faces on its boundary, and acts linearly on $k$-chains: if $C$ is a
$k$-chain, $\partial_{k}(C)$ is the $(k-1)$-chain consisting of $(k-1)$-faces
that occur an odd number of times on the boundary of $k$-faces in $C$. It
follows directly from its action on convex polytopes that, for any $C$,
$\partial_{k-1}\bigl{(}\partial_{k}(C)\bigr{)}=\emptyset$: the boundary of a
boundary is empty. Conversely, if $B$ is a $(k-1)$-chain with empty boundary –
that is, if $\partial_{k-1}(B)=\emptyset$ – then $B$ is itself a boundary:
there exists $C$ such that $B=\partial_{k}(C)$. In other spaces than
$\mathbb{R}^{d}$, there can exist chains with empty boundary that are not
themselves boundaries, corresponding to nontrivial elements of the homology
groups of the space, but $\mathbb{R}^{d}$ has trivial homology so such chains
do not exist.

For a set of $d$-dimensional training points with classifications, we consider
a subgraph of the Delaunay graph consisting of the edges connecting cells with
the same classification as each other, and we define a _decision component_ to
be a connected component of this subgraph; see Fig. 3. As a set of
$d$-dimensional Voronoi cells, it can be considered as a $k$-chain. If $C$ is
a decision component, form a graph $B_{C}$ whose vertices are the Voronoi
walls of $\partial_{k}(C)$, with two vertices adjacent when the two walls they
represent meet in a junction. We define a _decision boundary component_ to be
a connected component of $B_{C}$ for any decision component $C$. Because it
represents a set of Voronoi walls, it can be considered as a $(k-1)$-chain.

######  Lemma 4.

Every decision boundary component is the boundary of a set of Voronoi cells.

###### Proof.

Because $\partial_{k-1}\bigl{(}\partial_{k}(C)\bigr{)}=\emptyset$, and a set
of walls has an empty boundary if and only if they touch each junction an even
number of times, it follows that all vertices in $B_{C}$ have even degree, and
therefore that the same thing is true in every decision boundary component.
Therefore, if $D$ is a decision boundary component,
$\partial_{k-1}(D)=\emptyset$. It follows from the triviality of the homology
of $\mathbb{R}^{d}$ that there exists a $k$-chain $E$ such that
$\partial_{k}(E)=D$. ∎

If $D$ is a decision boundary component, we define a _side_ of $D$ to be a set
of Voronoi cells having $D$ as its boundary. By Lemma 4, every decision
boundary component has at least one side. (Actually, at least two, because the
complement of a side is another side.)

##  3 Correctness

###  3.1 Only relevant points are found

Algorithm 1 adds points to its set $R$ of relevant points in two ways: by
finding endpoints of minimum spanning tree edges and by finding extreme points
of inverted point sets. We prove in this section that in both cases the points
that are found are truly relevant: there is a nearest-neighbor classification
query that would be answered incorrectly if any one of these points were
omitted.

######  Lemma 5.

If $p$ is an endpoint of an edge of a minimum spanning tree for which the
other endpoint $p^{\prime}$ has a different classification, then $p$ is
relevant with respect to the whole data set, and also relevant with respect to
any subset of the data set that includes both $p$ and $p^{\prime}$.

###### Proof.

By Lemma 1, there is a Voronoi wall between the cells for $p$ and
$p^{\prime}$. Let $q$ be any point interior to that wall, and perturb $q$ to a
point $q^{\prime}$ closer to $p$ than to $p^{\prime}$, by a perturbation
sufficiently small that it does not touch or cross any other Voronoi walls.
Then the correct nearest neighbor classification of $q^{\prime}$ is the same
as that for $p$, but if $p$ were omitted then the classification would become
the same as for $p^{\prime}$, a different value. Therefore $p$ is relevant. ∎

######  Lemma 6.

If $r$ is relevant for the whole data set, $p$ has a different classification
than $r$, and $p$ corresponds to one of the extreme points of the set $S_{r}$
constructed by Algorithm 1, then $p$ is relevant with respect to the whole
data set, and also relevant with respect to any subset of the data set that
includes both $r$ and $p$.

###### Proof.

By Lemma 3, $r$ and $p$ share a wall in the Voronoi diagram of $S_{r}$. Let
$w$ be a point in the relative interior of this wall, chosen in general
position so that, in the Voronoi diagram of the whole training set, line
segment $pw$ does not cross any faces of lower dimension than a wall. With
this choice, $w$ is equidistant from $r$ and $p$, and farther from all other
points of different classification to $r$.

Within line segment $pw$, each point of the line segment has $p$ as the
nearest neighbor among points with a different classification to $r$; however,
some points of the line segment may have an even closer neighbor that has the
same classification as $r$. (For instance, this happens for the leftmost red
Voronoi neighbor of $r$ in Fig. 1.) Let $x$ be a point of line segment $pw$
that is equidistant from $p$ and from the nearest training point to $x$ with
the same classification as $r$. The existence of $x$ can be seen from the
intermediate value theorem, noting that at one endpoint of this segment, $p$,
$p$ is closer than any other training point, while at the other endpoint, $w$,
the nearest training point with the same classification as $r$ is at equal or
closer distance than $p$. Because of our choice of $w$ as being in general
position, no other training point can be as close to $x$ as these two points.
Then $x$ lies on a Voronoi wall between $p$ and a point with the same
classification as $r$, so $p$ is relevant by the same perturbation argument as
in the proof of Lemma 5. ∎

######  Lemma 7.

All points identified as relevant by Algorithm 1 are relevant, both with
respect to the whole data set and with respect to the subset of points
identified by the algorithm.

###### Proof.

This follows by induction on the number of iterations of the outer loop of
Algorithm 1, using Lemma 5 as the base case and Lemma 6 for the induction
step. ∎

###  3.2 All relevant points are found

If $D$ is a decision boundary component, and $w$ is a wall in $D$, between the
Voronoi cells for points $p$ and $q$, we say that $p$ and $q$ are _defining
points_ of $D$.

######  Lemma 8.

For every decision boundary component $D$, Algorithm 1 identifies at least one
defining point of $D$ as relevant.

###### Proof.

By Lemma 4, $D$ has a side $E$. Because the minimum spanning tree connects all
the Voronoi cells, it includes at least one edge $e$ that connects a cell in
$E$ to another cell not in $E$. The wall between these two cells is part of
the boundary of $E$, so it belongs to $D$, and its endpoints are defining
points of $D$. Because this wall belongs to a decision boundary component, it
separates two cells of different classifications, so the endpoints of $e$ will
be identified as relevant by the phase of Algorithm 1 that finds endpoints of
minimum spanning tree edges whose endpoints have different classifications. ∎

Once we have identified at least one defining point of a decision boundary
component, the second phase of Algorithm 1 finds all of them, as the following
lemmas show.

######  Lemma 9.

If Algorithm 1 identifies one of the two defining points of a wall of a
decision boundary component as relevant, it identifies the other defining
point of the same wall.

###### Proof.

Let $p$ be the first of the two defining points to be identified, and $q$ be
the other defining point for the same wall. Because they are separated by a
decision boundary component, they have different classifications. Then $q$ is
a neighbor of $p$ in the Delaunay graph of all of the training points, and
therefore also in the Delaunay graph of $p$ and the subset of training points
with different classifications to $p$. Therefore, by Lemma 3, $q$ will be
found as the inverted image of one of the extreme points in $S_{p}$. ∎

######  Lemma 10.

Let $w$ and $w^{\prime}$ be walls sharing a junction, such that both $w$ and
$w^{\prime}$ separate cells with different classifications and such that all
cells between them (within one of the two angles that they form at their
shared junction) have a single classification. Suppose also that Algorithm 1
identifies one of the defining points of $w$ as relevant. Then it also
identifies one of the defining points of $w^{\prime}$ as relevant.

###### Proof.

By Lemma 9, Algorithm 1 identifies the defining point $p$ of $w$ that lies
within the angle between $w$ and $w^{\prime}$. Let $q$ be the defining point
of $w^{\prime}$ that lies outside this angle, let $J$ be the junction of $w$
and $w^{\prime}$, and consider the link of this junction, within a plane
perpendicular to $J$. Within this link, the Voronoi cells incident to $J$
divide the plane into wedges, meeting at the point where $J$ crosses the plane
of the link. The defining sites of these cells are all closer to this point
than any other training points. For any subset of the training points that
includes at least one of the defining sites of a cell incident to $J$, the
cross-section of the Voronoi diagram in the plane of the link will still have
the structure of a set of wedges for the remaining sites, in the same circular
ordering. In particular, in the Voronoi diagram of $S_{p}$, the wedges of $p$
and $q$ will be consecutive. Therefore, these two cells are separated by a
wall in the Voronoi diagram of $S_{p}$, and by Lemma 3, $q$ will be found as
the inverted image of one of the extreme points in $S_{p}$. ∎

######  Lemma 11.

Algorithm 1 identifies all relevant points with respect to the whole training
set, and with respect to the set of points that it identies.

###### Proof.

Let $r$ be a training point that is relevant with respect to the whole
training set, and let $q$ be a query point that would get the wrong
classification if $r$ is removed from the training set (witnessing the
relevance of $r$). Then $r$ must be the nearest training point to $q$, and the
second-nearest training point $p$ to $q$ must have a different classification
than $r$. Because $p$ and $r$ are the nearest and second-nearest points to
$q$, they must share a Voronoi wall $w$, which belongs to a decision boundary
component $D$ of the decision component of $r$. By Lemma 8, Algorithm 1
identifies at least one defining point of $D$, and by Lemma 10 the defining
points that it identifies extend from any wall to any other wall of $D$ that
is consecutive at a junction, and therefore also to any other wall of $D$ that
is adjacent at a junction, and to any other wall that is connected through a
sequence of adjacencies at junctions. But $D$ was defined as a set of walls
that are adjacent in this way, so Algorithm 1 identifies at least one defining
point of $w$. By Lemma 9 it identifies both defining points, and therefore it
identifies $w$.

Removing an irrelevant point does not change the decision boundary components
or the defining points of their walls, so it does not create new relevant
points. Therefore, the relevant points with respect to the whole training set
identified by Algorithm 1 are also all of the relevant points with respect to
the set of points that it identifies. ∎

######  Theorem 1.

The nearest-neighbor classifications obtained from the set of relevant points
identified by Algorithm 1 equal the nearest-neighbor classifications obtained
from the whole training set.

###### Proof.

The classification of any point $p$ of $\mathbb{R}^{d}$, for a given set of
labeled points, may be obtained from the label of its nearest relevant point
$r$ for the given set; all Voronoi walls that separate $p$ from $r$ must have
the same label on both sides, for otherwise the two points defining the wall
would be relevant and at least one would be nearer to $p$ than to $r$, from
which it follows that the nearest neighbor to $p$ has the same label as $r$.
By Lemma 11 the identity of the relevant points does not change between the
whole training points and the subset of points identified by the algorithm,
and therefore the identity of the nearest relevant point cannot change. ∎

##  4 Analysis

We are now ready to prove our main results on the time bounds for finding
relevant points.

######  Theorem 2.

Algorithm 1, implemented using Jarník’s or Borůvka’s algorithm for its minimum
spanning trees, Algorithm 2 for extreme points, and Seidel’s algorithm [40]
for the linear programming steps of Algorithm 2, finds all relevant points of
a given training set of size $n$, having $k$ relevant points, in any constant
dimension $d$, in total time $O(n^{2}+k^{2}n)$.

###### Proof.

The correctness of the algorithm is shown by Lemma 7 and Lemma 11. By Lemma 7,
there are $k$ extreme-point computations, each of which identifies at most $k$
extreme points. The time bounds for the overall algorithm are obtained simply
by plugging in the time bounds for its subroutines. ∎

######  Theorem 3.

Algorithm 1, implemented using the algorithm of Agarwal, Edelsbrunner,
Schwarzkopf, and Welzl [1] for its minimum spanning trees, and the algorithm
of Chan [10] for its extreme points, finds all relevant points of a given
training set of size $n$, having $k$ relevant points, in randomized expected
time $O\bigl{(}(n\log n)^{4/3}+kn\log k\bigr{)}$ for $d=3$ and in time

$O\left(n^{2-\frac{2}{\lceil
d/2\rceil+1}+\varepsilon}+k(nk)^{1-\frac{1}{\lfloor d/2\rfloor+1}}(\log
n)^{O(1)}\right).$

for all constant dimensions $d>3$.

The proof is the same as for Theorem 2.

######  Theorem 4.

Algorithm 1, implemented using Jarník’s or Borůvka’s algorithm for its minimum
spanning trees, Algorithm 2 for extreme points, and an arbitrary linear
programming algorithm for the linear programming steps of Algorithm 2, finds
all relevant points of a given training set of size $n$, having $k$ relevant
points, in any constant dimension $d$, in time
$O\bigl{(}n^{2}+k^{2}n+knL(d,k)\bigr{)}$, where $L(x,y)$ denotes the time to
solve a linear program of dimension (number of variables) $x$ and size (number
of constraints) $y$.

Again, the proof is the same.

## References

  * [1] Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl.  Euclidean minimum spanning trees and bichromatic closest pairs.  Discrete Comput. Geom., 6(5):407–422, 1991.  doi:10.1007/BF02574698.
  * [2] Pankaj K. Agarwal and Jiří Matoušek.  Dynamic half-space range reporting and its applications.  Algorithmica, 13(4):325–345, 1995.  doi:10.1007/BF01293483.
  * [3] Alexandr Andoni and Piotr Indyk.  Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.  Commun. ACM, 51(1):117–122, 2008.  doi:10.1145/1327452.1327494.
  * [4] Sunil Arya, Theocharis Malamatos, and David M. Mount.  Space-time tradeoffs for approximate nearest neighbor searching.  J. ACM, 57(1):A1:1–A1:54, 2010.  doi:10.1145/1613676.1613677.
  * [5] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu.  An optimal algorithm for approximate nearest neighbor searching in fixed dimensions.  J. ACM, 45(6):891–923, 1998.  doi:10.1145/293347.293348.
  * [6] Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee.  Voronoi Diagrams and Delaunay Triangulations.  World Scientific, 2013.  doi:10.1142/8685.
  * [7] David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint.  Output-sensitive algorithms for computing nearest-neighbour decision boundaries.  Discrete Comput. Geom., 33(4):593–604, 2005.  doi:10.1007/s00454-004-1152-0.
  * [8] Paul B. Callahan and S. Rao Kosaraju.  Faster algorithms for some geometric graph problems in higher dimensions.  In Proc. 4th Symp. Discrete Algorithms (SODA 1993), pages 291–300. ACM, 1993.
  * [9] Timothy M. Chan.  Optimal output-sensitive convex hull algorithms in two and three dimensions.  Discrete Comput. Geom., 16(4):361–368, 1996.  doi:10.1007/BF02712873.
  * [10] Timothy M. Chan.  Output-sensitive results on convex hulls, extreme points, and related problems.  Discrete Comput. Geom., 16(4):369–387, 1996.  doi:10.1007/BF02712874.
  * [11] Timothy M. Chan.  Approximate nearest neighbor queries revisited.  Discrete Comput. Geom., 20(3):359–373, 1998.  doi:10.1007/PL00009390.
  * [12] Timothy M. Chan.  Improved deterministic algorithms for linear programming in low dimensions.  ACM Trans. Algorithms, 14(3):A30:1–A30:10, 2018.  doi:10.1145/3155312.
  * [13] Bernard Chazelle.  An optimal convex hull algorithm in any fixed dimension.  Discrete Comput. Geom., 10(4):377–409, 1993.  doi:10.1007/BF02573985.
  * [14] Bernard Chazelle and Jiří Matoušek.  Derandomizing an output-sensitive convex hull algorithm in three dimensions.  Comput. Geom., 5(1):27–32, 1995.  doi:10.1016/0925-7721(94)00018-Q.
  * [15] Kenneth L. Clarkson.  More output-sensitive geometric algorithms.  In Proc. 35th Symp. Foundations of Computer Science (FOCS 1994), pages 695–702. IEEE Computer Society, 1994.  doi:10.1109/SFCS.1994.365723.
  * [16] Kenneth L. Clarkson.  Las Vegas algorithms for linear and integer programming when the dimension is small.  J. ACM, 42(2):488–499, 1995.  doi:10.1145/201019.201036.
  * [17] Kenneth L. Clarkson and Peter W. Shor.  Applications of random sampling in computational geometry. II.  Discrete Comput. Geom., 4(5):387–421, 1989.  doi:10.1007/BF02187740.
  * [18] T. Cover and P. Hart.  Nearest neighbor pattern classification.  IEEE Transactions on Information Theory, 13(1):21–27, 1967.  doi:10.1109/tit.1967.1053964.
  * [19] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni.  Locality-sensitive hashing scheme based on $p$-stable distributions.  In Jack Snoeyink and Jean-Daniel Boissonnat, editors, Proc. 20th Symp. Computational Geometry (SoCG 2004), pages 253–262. ACM, 2004.  doi:10.1145/997817.997857.
  * [20] A. K. Dewdney and J. K. Vranch.  A convex partition of $\mathbb{R}^{3}$ with applications to Crum’s problem and Knuth’s post-office problem.  Utilitas Math., 12:193–199, 1977.
  * [21] Rex A. Dwyer.  Higher-dimensional Voronoi diagrams in linear expected time.  Discrete Comput. Geom., 6(4):343–367, 1991.  doi:10.1007/BF02574694.
  * [22] Martin E. Dyer and Alan M. Frieze.  A randomized algorithm for fixed-dimensional linear programming.  Math. Programming, 44(2, (Ser. A)):203–212, 1989.  doi:10.1007/BF01587088.
  * [23] David Eppstein.  Spanning trees and spanners.  In Jörg-Rudiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425–461. Elsevier, 2000.  doi:10.1016/B978-044482537-7/50010-3.
  * [24] David Eppstein, Michael T. Goodrich, and Jonathan Z. Sun.  Skip quadtrees: dynamic data structures for multidimensional point sets.  Internat. J. Comput. Geom. Appl., 18(1-2):131–160, 2008.  doi:10.1142/S0218195908002568.
  * [25] Aristides Gionis, Piotr Indyk, and Rajeev Motwani.  Similarity search in high dimensions via hashing.  In Malcolm P. Atkinson, Maria E. Orłowska, Patrick Valduriez, Stanley B. Zdonik, and Michael L. Brodie, editors, Proc. 25th Int. Conf. Very Large Data Bases (VLDB 1999), pages 518–529. Morgan Kaufmann, 1999.  URL: https://www.vldb.org/conf/1999/P49.pdf.
  * [26] Branko Grünbaum.  Convex Polytopes, volume 221 of Graduate Texts in Mathematics.  Springer, 2nd edition, 2003.  See in particular Grünbaum’s discussion of the Perles configuration on pp. 93–94.
  * [27] Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir.  Randomized incremental construction of Delaunay and Voronoi diagrams.  Algorithmica, 7(4):381–413, 1992.  doi:10.1007/BF01758770.
  * [28] Michael Henle.  A Combinatorial Introduction to Topology.  Dover Publications, 1994.
  * [29] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: towards removing the curse of dimensionality.  In Jeffrey Scott Vitter, editor, Proc. 30th Symp. Theory of Computing (STOC 1998), pages 604–613. ACM, 1998.  doi:10.1145/276698.276876.
  * [30] C. S. Karthik and Pasin Manurangsi.  On closest pair in Euclidean metric: monochromatic is as hard as bichromatic.  Combinatorica, 40(4):539–573, 2020.  doi:10.1007/s00493-019-4113-1.
  * [31] David G. Kirkpatrick and Raimund Seidel.  The ultimate planar convex hull algorithm?  SIAM J. Comput., 15(1):287–299, 1986.  doi:10.1137/0215021.
  * [32] Victor Klee.  On the complexity of $d$-dimensional Voronoi diagrams.  Arch. Math., 34(1):75–80, 1980.  doi:10.1007/BF01224932.
  * [33] Drago Krznaric, Christos Levcopoulos, and Bengt J. Nilsson.  Minimum spanning trees in $d$ dimensions.  Nordic J. Comput., 6(4):446–461, 1999.
  * [34] Jiří Matoušek.  Approximations and optimal geometric divide-and-conquer.  J. Comput. System Sci., 50(2):203–208, 1995.  doi:10.1006/jcss.1995.1018.
  * [35] Jiří Matoušek, Micha Sharir, and Emo Welzl.  A subexponential bound for linear programming.  Algorithmica, 16(4-5):498–516, 1996.  doi:10.1007/BF01940877.
  * [36] Nimrod Megiddo.  Linear programming in linear time when the dimension is fixed.  J. ACM, 31(1):114–127, 1984.  doi:10.1145/2422.322418.
  * [37] Thomas Ottmann, Sven Schuierer, and Subbiah Soundaralakshmi.  Enumerating extreme points in higher dimensions.  Nordic J. Comput., 8(2):179–192, 2001.
  * [38] Franco P. Preparata and Roberto Tamassia.  Efficient point location in a convex spatial cell-complex.  SIAM J. Comput., 21(2):267–280, 1992.  doi:10.1137/0221020.
  * [39] Raimund Seidel.  Exact upper bounds for the number of faces in $d$-dimensional Voronoi diagrams.  In Applied Geometry and Discrete Mathematics, volume 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 517–529. Amer. Math. Soc., 1991.
  * [40] Raimund Seidel.  Small-dimensional linear programming and convex hulls made easy.  Discrete Comput. Geom., 6(5):423–434, 1991.  doi:10.1007/BF02574699.
  * [41] Michael Ian Shamos and Dan Hoey.  Closest-point problems.  In Proc. 16th Symp. Foundations of Computer Science (FOCS 1975), pages 151–162. IEEE Computer Society, 1975.  doi:10.1109/SFCS.1975.8.
  * [42] D. F. Watson.  Computing the $n$-dimensional Delaunay tessellation with application to Voronoi polytopes.  Comput. J., 24(2):167–172, 1981.  doi:10.1093/comjnl/24.2.167.


# Some enumerative properties of a class of Fibonacci-like cubes††thanks: This
work was supported by NSFC (Grant No. 11761064).

Xuxu Zhao , Xu Wang and Haiyuan Yao111Corresponding author.
College of Mathematics and Statistics, Northwest Normal University, Lanzhou,
Gansu 730070, PR China
e-mail addresses<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A filter lattice is a distributive lattice formed by all filters of a poset in
the anti-inclusion order. We study the combinatorial properties of the Hasse
diagrams of filter lattices of certain posets, so called Fibonacci-like cubes,
in this paper. Several enumerative polynomials, e.g. rank generating function,
cube polynomials and degree sequence polynomials are obtained. Some of these
results relate to Fibonacci sequence and Padovan sequence.

Key words: finite distributive lattice, matchable cube, rank generating
functions, cube polynomials, maximal cube polynomials, degree sequence
polynomials , indegree polynomials.

##  1 Introduction

Fibonacci cubes are introduced by Hsu [2] as a interconnection topology. Lucas
cubes is a class of graphs with close similarity with Fibonacci cubes [5].
Many enumerative properties [8] such as cube polynomials, maximal cube
polynomials and degree sequence polynomials of Fibonacci cubes and Lucas cubes
are obtained by Klavžar & Mollard [4], Saygı & Eğecioğlu [9], Mollard [6] and
Klavžar et al. [3]. Munarini and Zagaglia Salvi [7] found the undirected Hasse
diagrams of filter lattices of fences [11] are isomorphic to Fibonacci cubes
and gave the the rank polynomials of the filter lattices. Using a convex
expansion, Wang et al. [12] considered indegree sequences of Hasse diagrams of
finite distributive lattices and gave the relation of indegree sequence
polynomials between cube polynomials.

Let $P=(P,\leq)\,(p\neq\emptyset)$ is a partially ordered set(poset for
short). The _dual_ $P^{*}$ of $P$ by defining $x\leq y$ to hold in $P^{*}$ if
and only if $y\leq x$ holds in $P$. Let $x\prec y$ denote $x$ is covered by
$y$, if $x<y$ and $x\leq z<y$ implies $z=x$. Let $Q$ be a subset of $P$, then
$Q$ has an induced order relation from $P$: given $x,y\in Q$, $x\leq y$ in $Q$
if and only if $x\leq y$ in $P$. The subset $Q$ of the poset $P$ is called
convex if $a,b\in Q$, $c\in P$, and $a\leq c\leq b$ imply that $c\in Q$. A
subset $Y$ is a filter (up-set) of $P$ if $y\in Y$ and $y\leq z$ then $z\in
Y$. The set $\mathcal{F}(P)$ of all filters of $P$ forms a distributive
lattice reordered by anti-inclusion: $Y^{\prime}\leq Y$ if and only if
$Y^{\prime}\supseteq Y$, namely the filter lattice
$\mathcal{F}(P):=(\mathcal{F}(P),\supseteq)$.

A filter lattice is a distributive lattice formed by filter of a poset in the
anti-inclusion order. We study the combinatorial properties of a class of
specitial cubes in this paper. These cubes are induced by the Hasse diagram of
filter lattices of certain poset, contain Fibonacci cubes as its sub-cubes and
have similar properties with Fibonacci cubes, so called Fibonacci-like cubes.
We obtained some structural and enumerative properties of the cubes and the
distributive lattices, including rank generating functions, cube polynomials,
maximal cube polynomials, degree sequence polynomials and indegree sequence
polynomials.

##  2 Fibonacci-like cubes

The fence or “zigzag poset” $Z_{n}$[11] is an interesting poset, with element
$\\{x_{1},\ldots,x_{n}\\}$ and cover relation $x_{2i-1}<x_{2i}$ and
$x_{2i}>x_{2i+1}$, and the underlying graph of the Hasse diagram of
$\mathcal{F}(Z_{n})$ is a Fibonacci cube $\Gamma_{n}$. Now we have a new poset
modified from fence.

######  Definition 2.1.

The $S$-fence, denoted by $\phi_{n}$, is a fence-like poset, with element
$\\{x_{1},\ldots,x_{n}\\}$ and cover relations $x_{1}>x_{2}>x_{3}$,
$x_{2}<x_{4}$ and $x_{4}>x_{5}$, for $i\geq 3$, $x_{2i-1}<x_{2i}$ and
$x_{2i}>x_{2i+1}$.

$x_{1}$$x_{2}$$x_{3}$$x_{5}$$x_{4}$$x_{6}$$\cdots$$x_{7}$$\cdots$$x_{n}$(a)
$n$ is odd

$x_{1}$$x_{2}$$x_{3}$$x_{5}$$x_{4}$$x_{6}$$\cdots$$x_{7}$$\cdots$$x_{n}$(b)
$n$ is even

Figure 1: S-fence $\phi_{n}$

The Hasse diagram of the filter lattice $\mathcal{F}(\phi_{n})$ can be
considered as a directed graph (namely (x,y) is an arc if and only if $y\prec
x$). The underlying graph of the Hasse diagram of $\mathcal{F}(\phi_{n})$ is a
Fibonacci-like cube (FLC for shorter). For convenience, both the Hasse diagram
(as a diricted graph) and its underlying graph are denoted by $\Phi_{n}$ too.
Note that $\Phi_{0}$ is the trivial graph with only one vertex.

Figure 2: The first eight Fibonacci-like cubes $\Phi_{0}$, $\Phi_{1}$, …,
$\Phi_{7}$

Let $L$ be a distributive lattice. A convex sublattice (interval) $K$ of $L$
is called a cutting if any maximal chain of $L$ must contain some elements of
$K$. The convex expansion $L\boxplus K$ of $L$ with respect to $K$ is a
distributive lattice on the set $L\cup K^{\prime}$ ($K^{{}^{\prime}}\cong K$ a
copy of $K$) with the induced order:

$\displaystyle x\leq y,$ if $x\leq y$ in $L$, $\displaystyle
x^{{}^{\prime}}<y,$ if $x\leq y$ in $L$ with $x\in K$, $\displaystyle
x<y^{{}^{\prime}},$ if $x<y$ in $L$ with $y\in K$, $\displaystyle
x^{{}^{\prime}}\leq y^{{}^{\prime}},$ if $x\leq y$ in $K$.

As show in Figure 3, where $\hat{1}_{K}$ and $\hat{0}_{K}$ denote the maximum
element and minimum element of the distributive lattice $K$, respectively
(see[12]).

$K$$\hat{0}_{K}$$\hat{1}_{K}$$K$$K^{\prime}(\cong K)$$L\boxplus K$$L$ Figure
3: The finite distributive lattices $L$ and $L\boxplus K$

######  Lemma 2.1.

The filter lattice $\mathcal{F}(P)$ is considered as a convex expansion, that
is for every $x\in P$,

$\mathcal{F}(P)\cong\mathcal{F}(P-x)\boxplus\mathcal{F}(P*x),$

where $P-x$ and $P*x$ the induced subposets on $P\setminus\\{x\\}$ and
$P\setminus\\{y\in P|y\leq x\text{ or }x\leq y\\}$, respectively.

It is known that
$\Gamma_{n}\cong\Gamma_{n-1}\boxplus\Gamma_{n-2}\cong(\Gamma_{n-2}\boxplus\Gamma_{n-2})\boxplus\Gamma_{n-3}\;(n\geq
4)$ [8]. FLC $\Phi_{n}$ has similar structure with the Fibonacci cube and
matchable Lucas cubes [12], as shown in Figure 4 and Figure 5.

######  Lemma 2.2.

Let $\Phi_{n}$ be the $n$-th FLC defined above. Then

$\Phi_{n}\cong\Gamma_{n-1}^{*}\boxplus\Gamma_{n-4}^{*}\cong\left((\Gamma_{n-3}^{*}\boxplus\Gamma_{n-3}^{*})\boxplus\Gamma_{n-4}^{*}\right)\boxplus\Gamma_{n-4}^{*}\;(n\geq
5).$

or

$\Phi_{n}\cong\Phi_{n-1}\boxplus\Phi_{n-2}\cong(\Phi_{n-2}\boxplus\Phi_{n-2})\boxplus\Phi_{n-3}\;(n\geq
6).$

######  Proof..

By definition of $\Phi_{n}$, the result is easily obtained by putting
$x=x_{n}$ and $x=x_{3}$ in Lemma 2.1, respectively. $\square$

$\Gamma_{n-1}^{*}$$\Gamma_{n-2}^{*}$$\Gamma_{n-3}^{*}$$\Gamma_{n-3}^{*}$$\Gamma_{n-4}^{*}$$\Gamma_{n-4}^{*}$$\Gamma_{n-4}^{*}$$\Gamma_{n-4}^{*}$
Figure 4: The structure of $\Phi_{n}$ given by $\Gamma_{n}$

$\Phi_{n-1}$$\Phi_{n-2}$$\Phi_{n-2}$$\Phi_{n-3}$$\Phi_{n-3}$$\Phi_{n-3}$(a)
$n$ is even

$\Phi_{n-1}$$\Phi_{n-2}$$\Phi_{n-2}$$\Phi_{n-3}$$\Phi_{n-3}$$\Phi_{n-3}$(b)
$n$ is odd

Figure 5: The recursive structure of $\Phi_{n}$

By Lemma 2.2 and the fact that $|V(\Gamma_{n})|=F_{n+2}$, we have folloing
relation.

######  Corollary 2.3.

The number of vertices of $\Phi_{n}$ is $2F_{n}$.

##  3 Enumerative properties

Let $F_{n}$ be the $n$-th Fibonacci number defined by: $F_{0}=0$, $F_{1}=1$,
$F_{n}=F_{n-1}+F_{n-2}$, for $n\geq 2$. The generating function of the
sequence $\\{F_{n}\\}_{n=0}^{\infty}$ is

$\sum_{n\geq 0}F_{n}x^{n}=\frac{x}{1-x-x^{2}}.$

There is an interesting relation between Fibonaci numbers and binomial
coefficients:

$\sum_{k=0}^{\frac{n}{2}}\binom{n-k}{k}=F_{n+1}.$

The enumerative properties of Fibonacci cubes and Lucas cubes has been
extensively studied $[3\text{-}9]$. In this section, we obtain some
enumerative properties of $\Phi_{n}$, such as rank generating functions i.e.
rank polynomials, cube polynomials, maximal cube polynomial, degree sequences
polynomial, indegree and outdegree polynomials. Some results are related to
Fibonacci sequences since the number of vertices of $\Phi_{n}$ equals to
$2F_{n}$. The number of the maximal $k$-dimensional cubes in $\Phi_{n}$ is a
Padovan number.

Note that hereafter set $\binom{n}{k}=0$ whenever the condition $0\leq k\leq
n$ is invalid for any integers $n$ and $k$.

The proof of the conclusion about the generating function is similar to the
proof of Theorem 3.4,and the proof of Propositions 3.12, 3.28 are similar to
the proof of Proposition 3.18 (see [4], [11]).

###  3.1 Rank generating functions

The rank generating function of $\Phi_{n}$ is
$R_{n}(x):=R(\Phi_{n},x)=\sum_{k\geq 0}r_{n,k}x^{k}$, where
$r_{n,k}:=r_{k}(\Phi_{n})$ denoted the number of the elements of rank $k$ in
$\Phi_{n}$. The first few of $R_{n}(x)$ are listed.

$\displaystyle R_{0}(x)$ $\displaystyle=1$ $\displaystyle R_{1}(x)$
$\displaystyle=1+x$ $\displaystyle R_{2}(x)$ $\displaystyle=1+x+x^{2}$
$\displaystyle R_{3}(x)$ $\displaystyle=1+x+x^{2}+x^{3}$ $\displaystyle
R_{4}(x)$ $\displaystyle=1+x+x^{2}+2x^{3}+x^{4}$ $\displaystyle R_{5}(x)$
$\displaystyle=1+2x+2x^{2}+2x^{3}+2x^{4}+x^{5}$ $\displaystyle R_{6}(x)$
$\displaystyle=1+2x+3x^{2}+3x^{3}+3x^{4}+3x^{5}+x^{6}$ $\displaystyle
R_{7}(x)$ $\displaystyle=1+3x+4x^{2}+5x^{3}+5x^{4}+4x^{5}+3x^{6}+x^{7}$
$\displaystyle R_{8}(x)$
$\displaystyle=1+3x+5x^{2}+7x^{3}+8x^{4}+7x^{5}+6x^{6}+4x^{7}+x^{8}$
$\displaystyle R_{9}(x)$
$\displaystyle=1+4x+7x^{2}+10x^{3}+12x^{4}+12x^{5}+10x^{6}+7x^{7}+4x^{8}+x^{9}.$

######  Lemma 3.1 ([12]).

Let $L$ be a finite distributive lattice and $K$ is a cutting of $L$. The rank
generating function of $L\boxplus K$ is

$R(L\boxplus K,x)=\begin{cases}R(L,x)+x^{h_{L}(\hat{0}_{K})+1}R(K,x),&\text{if
}\hat{1}_{K}=\hat{1}_{L};\\\ R(K,x)+xR(L,x),&\text{if
}\hat{0}_{K}=\hat{0}_{L}.\end{cases}$

where $h_{L}(x)$ denote the height of $x$ in $L$ for $x\in L$.

By the Lemma 3.1 we have

######  Proposition 3.2.

For $n\geq 5$

$R_{n}(x)=\begin{cases}xR_{n-1}(x)+R_{n-2}(x),&\mbox{if }2\nmid n,\\\
R_{n-1}(x)+x^{2}R_{n-2}(x),&\mbox{if }2\mid n.\end{cases}$

Let $A_{m}(x)=R_{2m}(x)$ and $B_{m}(x)=R_{2m+1}(x)$, we have

$\displaystyle\begin{cases}A_{m}(x)=B_{m-1}(x)+x^{2}A_{m-1}(x),&(m\geq 3),\\\
B_{m}(x)=xA_{m}(x)+B_{m-1}(x),&(m\geq 2).\end{cases}$

$A_{m}(x)$ and $B_{m}(x)$ have the recurrence relations:

######  Proposition 3.3.

$\begin{cases}A_{m}(x)=(1+x+x^{2})A_{m-1}(x)-x^{2}A_{m-2}(x),&(m\geq 4),\\\
B_{m}(x)=(1+x+x^{2})B_{m-1}(x)-x^{2}B_{m-2}(x),&(m\geq 2).\end{cases}$

######  Proof..

By Proposition 3.2, for $m\geq 4$,

$\displaystyle A_{m}(x)$ $\displaystyle=B_{m-1}(x)+x^{2}A_{m-1}(x)$
$\displaystyle=xA_{m-1}(x)+B_{m-2}(x)+x^{2}A_{m-1}(x)$
$\displaystyle=xA_{m-1}(x)+A_{m-1}(x)-x^{2}A_{m-2}(x)+x^{2}A_{m-1}(x)$
$\displaystyle=(1+x+x^{2})A_{m-1}(x)-x^{2}A_{m-2}(x).$

For $B_{2}(x)$, the conclusion is also ture. Samilarily, the recurrence
relation of $B_{m}(x)$ can be obtained. $\square$

Then, we can derive the generating functions of $A_{m}(x)$ and $B_{m}(x)$ by
Proposition 3.3, respectively.

######  Theorem 3.4.

The generating functions of $A_{m}(x)$ and $B_{m}(x)$ are

$\sum_{m\geq 0}A_{m}(x)z^{m}=z+\frac{1-z+z^{2}}{1-(1+x+x^{2})z+x^{2}z^{2}}$

and

$\sum_{m\geq
0}B_{m}(x)z^{m}=\frac{1+x-(x+x^{2})z}{1-(1+x+x^{2})z+x^{2}z^{2}},$

respectively.

######  Proof..

By the Proposition 3.3,

$\displaystyle\sum_{m\geq 0}A_{m}(x)z^{m}$ $\displaystyle=\sum_{m\geq
4}A_{m}(x)z^{m}+A_{3}(x)z^{3}+A_{2}(x)z^{2}+A_{1}(x)y+A_{0}(x)$
$\displaystyle=\sum_{m\geq
4}((1+x+x^{2})A_{m-1}-x^{2}A_{m-2})z^{m}+A_{3}(x)z^{3}+A_{2}(x)z^{2}+A_{1}(x)z+A_{0}(x)$
$\displaystyle=(1+x+x^{2})z\sum_{m\geq 3}A_{m}(x)z^{m}-x^{2}z^{2}\sum_{m\geq
2}A_{m}(x)z^{m}A_{3}(x)z^{3}+A_{2}(x)z^{2}+A_{1}(x)z+A_{0}(x)$
$\displaystyle=(1+x+x^{2})z\sum_{m\geq 0}A_{m}(x)z^{m}-x^{2}z^{2}\sum_{m\geq
0}A_{m}(x)z^{m}+1+x^{2}z^{3}-xz^{2}-x^{2}z^{2}.$

Similarly, the generating function of $B_{m}$ are obtained. $\square$

In addition, $A_{m}(x)$ and $B_{m}(x)$ can be obtained by Theorem 3.4.

Let $\binom{n;3}{k}$ denote the coefficient of $x^{k}$ in
$(1+x+x^{2})^{n}$(see [1]), which is

$\binom{n;3}{k}=\sum_{i=0}^{\lfloor k/2\rfloor}\binom{n}{k-i}\binom{k-i}{i}.$

See also the sequence A027907 in the OEIS [10]. Using Kronecker delta function
$\delta$, we have the formula of the coefficient $r_{n,k}$.

######  Theorem 3.5.

$r_{2m,k}=\delta_{1,m}\delta_{0,k}+\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}(-1)^{i}\binom{m-i}{i}\binom{m-2i;3}{k-2i}-\sum_{i=0}^{\lfloor\frac{m-1}{2}\rfloor}(-1)^{i}\binom{m-i-1}{i}\binom{m-2i-1;3}{k-2i}\\\
+\sum_{i=0}^{\lfloor\frac{m-2}{2}\rfloor}(-1)^{i}\binom{m-i-2}{i}\binom{m-2i-2;3}{k-2i}.$

and

$r_{2m+1,k}=\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}(-1)^{i}\binom{m-i}{i}\left(\binom{m-2i;3}{k-2i}+\binom{m-2i;3}{k-2i-1}\right)\\\
-\sum_{i=0}^{\lfloor\frac{m-1}{2}\rfloor}(-1)^{i}\binom{m-i-1}{i}\left(\binom{m-2i-1;3}{k-2i-1}+\binom{m-2i-1;3}{k-2i-2}\right).$

######  Proof..

Consider the polynomials $g_{n}(x)$ defined by

$\sum_{n\geq 0}g_{n}(x)z^{n}=\frac{1}{1-(1+x+x^{2})z+x^{2}z^{2}}$

such that

$g_{n}(x)=\sum_{i=0}^{\lfloor
n/2\rfloor}(-1)^{i}\binom{n-i}{i}x^{2i}(1+x+x^{2})^{n-2i}.$

In addition, the coefficient of $x^{k}$ in $g_{n}(x)$ can be given by

$[x^{k}]g_{n}(x)=\sum_{i=0}^{\lfloor
n/2\rfloor}(-1)^{i}\binom{n-i}{i}x^{2i}(1+x+x^{2})^{n-2i}=\sum_{i=0}^{\lfloor
n/2\rfloor}(-1)^{i}\binom{n-i}{i}\binom{n-2i;3}{k-2i}.$

Then, since $A_{m}(x)=z+g_{m}(x)-g_{m-1}(x)+g_{m-2}(x)$, we have

$\displaystyle r_{2m,k}$
$\displaystyle=[x^{k}]A_{m}(x)=[x^{k}]z+[x^{k}]g_{m}(x)-[x^{k}]g_{m-1}(x)+[x^{k}]g_{m-2}(x)$
$\displaystyle=\delta_{1,m}\delta_{0,k}+\sum_{i=0}^{\lfloor\frac{m}{2}\rfloor}(-1)^{i}\binom{m-i}{i}\binom{m-2i;3}{k-2i}-\sum_{i=0}^{\lfloor\frac{m-1}{2}\rfloor}(-1)^{i}\binom{m-i-1}{i}\binom{m-2i-1;3}{k-2i}$
$\displaystyle~{}+\sum_{i=0}^{\lfloor\frac{m-2}{2}\rfloor}(-1)^{i}\binom{m-i-2}{i}\binom{m-2i-2;3}{k-2i}.$

Thus, $r_{2m+1,k}$ is obtained from
$B_{m}(x)=g_{m}(x)+xg_{m}(x)-xg_{m-1}(x)-x^{2}g_{m-1}(x)$ in the same way.
$\square$

We can obtain the generating function of $R_{n}(x)$ from Theorem 3.4.

######  Theorem 3.6.

The generating function of $R_{n}(x)$ is

$\sum_{n\geq
0}R_{n}(x)y^{n}=\frac{1+(1+x)y-(x+x^{2})y^{3}-(x+x^{2})y^{4}+x^{2}y^{6}}{1-(1+x+x^{2})y^{2}+x^{2}y^{4}}.$

######  Proof..

By the definition of $A_{m}(x)$ and $B_{m}(x)$,

$\displaystyle\sum_{n\geq 0}R_{n}(x)y^{n}$ $\displaystyle=\sum_{m\geq
0}A_{m}(x)y^{2m}+\sum_{m\geq 0}B_{m}(x)y^{2m+1}$ $\displaystyle=\sum_{m\geq
0}A_{m}(x)y^{2m}+y\sum_{m\geq 0}B_{m}(x)y^{2m}$
$\displaystyle=\frac{1-xy^{4}-x^{2}y^{4}+x^{2}y^{6}}{1-(1+x+x^{2})y^{2}+x^{2}y^{4}}+y\frac{1+x-xy^{2}-x^{2}y^{2}}{1-(1+x+x^{2})y^{2}+x^{2}y^{4}}$
$\displaystyle=\frac{1+(1+x)y-(x+x^{2})y^{3}-(x+x^{2})y^{4}+x^{2}y^{6}}{1-(1+x+x^{2})y^{2}+x^{2}y^{4}}.$

$\square$

Since $R_{n}(1)$ is the number of vertices of $\Phi_{n}$, put $x=1$ in the
generating function of $R_{n}(x)$ we obtain the generating function of the
number of vertices of $\Phi_{n}$ is

$1+y^{2}+\frac{2y}{1-y-y^{2}}.$

Thus we have the following results related to Fibonacci sequences:

######  Corollary 3.7.

Using the above notation, we have

$\sum_{k=0}^{n}r_{n,k}=2F_{n}\;\;(n\geq 3).$

###  3.2 Cube polynomials

The cube polynomials of $\Phi_{n}$ is $Q_{n}(x)=\sum_{k\geq 0}q_{n,k}x^{k}$,
where $q_{n,k}:=q_{k}(\Phi_{n})$ is the number of the $k$-dimensional induced
hypercubes of $\Phi_{n}$. The first few of $Q_{n}(x)$ are listed.

$\displaystyle Q_{0}(x)$ $\displaystyle=1$ $\displaystyle Q_{1}(x)$
$\displaystyle=2+x$ $\displaystyle Q_{2}(x)$ $\displaystyle=3+2x$
$\displaystyle Q_{3}(x)$ $\displaystyle=4+3x$ $\displaystyle Q_{4}(x)$
$\displaystyle=6+6x+x^{2}$ $\displaystyle Q_{5}(x)$
$\displaystyle=10+13x+4x^{2}$ $\displaystyle Q_{6}(x)$
$\displaystyle=16+25x+11x^{2}+x^{3}$ $\displaystyle Q_{7}(x)$
$\displaystyle=26+48x+28x^{2}+5x^{3}.$

######  Lemma 3.8 ([12]).

Let $L$ be a finite distributive lattice and $K$ a cutting of $L$. Then

$q_{k}(L\boxplus K)=q_{k}(L)+q_{k}(K)+q_{k-1}(K).$

We can get the recurrence relation of $q_{n,k}$ from Lemma 3.8 evidently.

######  Proposition 3.9.

For $n\geq 4$,

$q_{n,k}=q_{n-1,k}+q_{n-2,k}+q_{n-2,k-1}.$

It is easy to get the recurrence relation of $Q_{n}(x)$.

######  Proposition 3.10.

For $n\geq 5$,

$Q_{n}(x)=Q_{n-1}(x)+(1+x)Q_{n-2}(x).$

######  Proof..

By the Proposition 3.9,

$\displaystyle Q_{n}(x)$ $\displaystyle=\sum_{k\geq 0}q_{n,k}x^{k}=\sum_{k\geq
0}(q_{n-1,k}+q_{n-2,k}+q_{n-2,k-1})x^{k}$ $\displaystyle=\sum_{k\geq
0}q_{n-1,k}x^{k}+\sum_{k\geq 0}q_{n-2,k}x^{k}+x\sum_{k\geq
0}q_{n-2,k-1}x^{k-1}$ $\displaystyle=Q_{n-1}(x)+(1+x)Q_{n-2}(x).$

$\square$

######  Theorem 3.11.

The generating function of $Q_{n}(x)$ is

$\sum_{n\geq
0}Q_{n}(x)y^{n}=\frac{1+(1+x)y-(1+x)^{2}y^{3}-(1+x)^{2}y^{4}}{1-y-(1+x)y^{2}}.$

######  Proposition 3.12.

For $n\geq 0$,

$Q_{n}(x)=\sum_{j=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-j+1}{j}(1+x)^{j}-\sum_{j=2}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-j-1}{j-2}(1+x)^{j}-\sum_{j=2}^{\lfloor\frac{n}{2}\rfloor}\binom{n-j-2}{j-2}(1+x)^{j}.$

and thus

$q_{n,k}=\sum_{j=0}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-j+1}{j}\binom{j}{k}-\sum_{j=2}^{\lfloor\frac{n+1}{2}\rfloor}\binom{n-j-1}{j-2}\binom{j}{k}-\sum_{j=2}^{\lfloor\frac{n}{2}\rfloor}\binom{n-j-2}{j-2}\binom{j}{k}.$

######  Corollary 3.13.

For $n\geq 3$, the number of vertices of $\Phi_{n}$ is

$q_{n,0}=2\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}=2F_{n}.$

###  3.3 Maximal cube polynomials

The maximal cube polynomial of $\Phi_{n}$ is $H_{n}(x)=\sum_{k\geq
0}h_{n,k}x^{k}$, where $h_{n,k}:=h_{k}(\Phi_{n})$ be the number of the maximal
$k$-dimensional cubes in $\Phi_{n}$, The first few of $H_{n}(x)$ are listed.

$\displaystyle H_{0}(x)$ $\displaystyle=1$ $\displaystyle H_{1}(x)$
$\displaystyle=x$ $\displaystyle H_{2}(x)$ $\displaystyle=2x$ $\displaystyle
H_{3}(x)$ $\displaystyle=3x$ $\displaystyle H_{4}(x)$ $\displaystyle=2x+x^{2}$
$\displaystyle H_{5}(x)$ $\displaystyle=4x^{2}$ $\displaystyle H_{6}(x)$
$\displaystyle=5x^{2}+x^{3}$ $\displaystyle H_{7}(x)$
$\displaystyle=2x^{2}+5x^{3}$

We can get the recurrence relation of $h_{n,k}$ from Lemma 2.2.

######  Proposition 3.14.

For $n\geq 6$,

$h_{n,k}=h_{n-2,k-1}+h_{n-3,k-1}.$

By Proposition 3.14 the recurrence relation of $H_{n}(x)$ is given easily.

######  Proposition 3.15.

For $n\geq 6$,

$H_{n}(x)=xH_{n-2}(x)+xH_{n-3}(x).$

The $(1,3,3)$-Padovan number $p_{n}$ is defined as: $p_{0}=1$, $p_{1}=3$,
$p_{2}=3$,$p_{n}=p_{n-2}+p_{n-3}$, for $n\geq 3$. Hence we have the following
corollary.

######  Corollary 3.16.

For $n\geq 3$,

$H_{n}(1)=p_{n-2}.$

Furthermore, we can obtain the generating function of $H_{n}(x)$ by
Proposition 3.15.

######  Theorem 3.17.

The generating function of $H_{n}(x)$ is

$\displaystyle\sum_{n=0}^{\infty}H_{n}(x)y^{n}$
$\displaystyle=\frac{1+xy(1+y)+2xy^{3}(1+y)-x^{2}y^{3}(1+y)^{2})}{1-xy^{2}(1+y)}$
$\displaystyle=-2y+xy+xy^{2}+\frac{1+2y}{1-xy^{2}(1+y)}.$

Because $-2y+xy+xy^{2}$ are parts of $H_{1}(x)y$ and $H_{2}(x)y^{2}$, we have
the Proposition 3.18.

######  Proposition 3.18.

For $n\geq 3$,

$H_{n}(x)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\left(\binom{k+1}{n-2k}+\binom{k}{n-2k-1}\right)x^{k},$

and

$h_{n,k}=\binom{k+1}{n-2k}+\binom{k}{n-2k-1}.$

######  Proof..

$\displaystyle\frac{1+2y}{1-xy^{2}(1+y)}$ $\displaystyle=\sum_{j\geq
0}(1+y)^{j}x^{j}y^{2j}+2\sum_{j\geq 0}(1+y)^{j}x^{j}y^{2j+1}$
$\displaystyle=\sum_{j\geq
0}\sum_{n-2j=0}^{j}\binom{j}{n-2j}x^{j}y^{n}+2\sum_{j\geq
0}\sum_{n-2j-1=0}^{j}\binom{j}{n-2j-1}x^{j1}y^{n}$ $\displaystyle=\sum_{n\geq
0}\sum_{k=\lceil\frac{n}{3}\rceil}^{\lfloor\frac{n}{2}\rfloor}\binom{k}{n-2k}x^{k}y^{n}+2\sum_{n\geq
0}\sum_{k=\lceil\frac{n-1}{3}\rceil}^{\lfloor\frac{n-1}{2}\rfloor}\binom{k}{n-2k-1}x^{k}y^{n}.$

The proof is completed. $\square$

###  3.4 Degree sequences polynomials

The degree sequences polynomial of $\Phi_{n}$ is $D_{n}(x)=\sum_{k\geq
0}d_{n,k}x^{k}$, where $d_{n,k}:=d_{k}(\Phi_{n})$ denoted the number of
vertices of the degree $k$ in $\Phi_{n}$, i.e. $d_{n,k}=|\\{\,v\in
V(\Phi_{n})\mid\operatorname{deg}_{\Phi_{n}}(v)=k\,\\}|$. The first few of
$D_{n}(x)$ are listed

$\displaystyle D_{0}(x)$ $\displaystyle=1$ $\displaystyle D_{1}(x)$
$\displaystyle=2x$ $\displaystyle D_{2}(x)$ $\displaystyle=2x+x^{2}$
$\displaystyle D_{3}(x)$ $\displaystyle=2x+2x^{2}$ $\displaystyle D_{4}(x)$
$\displaystyle=x+4x^{2}+x^{3}$ $\displaystyle D_{5}(x)$
$\displaystyle=5x^{2}+4x^{3}+x^{4}$ $\displaystyle D_{6}(x)$
$\displaystyle=3x^{2}+9x^{3}+3x^{4}+x^{5}$ $\displaystyle D_{7}(x)$
$\displaystyle=x^{2}+11x^{3}+10x^{4}+3x^{5}+x^{6}$

The recurrence relation $d_{n,k}$ is illustrated in the Figure 6.

$\Phi_{n-3}$$\Phi_{n-2}$$\Phi_{n}$ Figure 6: Illustrating the recurrence
relation of $d_{n,k}$

######  Proposition 3.19.

For $n\geq 4$,

$d_{n,k}=d_{n-2,k-1}+d_{n-1,k-1}-d_{n-3,k-2}+d_{n-3,k-1}.$

######  Proposition 3.20.

For $n\geq 6$,

$D_{n}(x)=xD_{n-1}(x)+xD_{n-2}(x)+(x-x^{2})D_{n-3}(x).$

Therefore, the generating function of $D_{n}(x)$ is obtained.

######  Theorem 3.21.

The generating function of $D_{n}(x)$ is given by

$\sum_{n\geq
0}D_{n}(x)y^{n}=-y+xy+x^{2}y^{2}+\frac{1+y-x^{2}y^{2}}{(1-xy)(1-xy^{2})-xy^{3}}.$

######  Proposition 3.22.

For $n\geq 3$, the number of vertices of degree $k$ of $\Phi_{n}$ is

$d_{n,k}=\sum_{j=0}^{k}\left(\binom{n-2j}{k-j}\binom{j}{n-k-j}+\binom{n-2j-1}{k-j}\binom{j}{n-k-j-1}-\binom{n-2j-2}{k-j-2}\binom{j}{n-k-j}\right).$

######  Proof..

The way is similar to the method of [3]. Using the expansion

$\frac{x^{n}}{(1-x)^{n+1}}=\sum_{j\geq n}\binom{j}{n}x^{j},$

we consider the formal power series expansion of

$f(x,y)=\frac{1}{(1-xy)(1-xy^{2})-xy^{3}},$ $\displaystyle f(x,y)$
$\displaystyle=\frac{1}{(1-xy)(1-xy^{2})-xy^{3}}$
$\displaystyle=\frac{(1-xy)^{-1}(1-xy^{2})^{-1}}{1-xy^{3}(1-xy)^{-1}(1-xy^{2})^{-1}}$
$\displaystyle=\sum_{t\geq 0}x^{t}y^{3t}(1-xy)^{-t-1}(1-xy^{2})^{-t-1}$
$\displaystyle=\sum_{t\geq
0}\frac{(xy)^{t}}{(1-xy)^{t+1}}\frac{(xy^{2})^{t}}{(1-xy^{2})^{t+1}}x^{-t}$
$\displaystyle=\sum_{t\geq 0}\sum_{i\geq t}\binom{i}{t}(xy)^{i}\sum_{j\geq
t}\binom{j}{t}(xy^{2})^{j}x^{-t}$ $\displaystyle=\sum_{n\geq
0}\sum_{k=0}^{n}\sum_{j=0}^{k}\binom{n-2j}{k-j}\binom{j}{n-k-j}x^{k}y^{n}.$

Thus

$[x^{k}][y^{n}]f(x,y)=\sum_{j=0}^{k}\binom{n-2j}{k-j}\binom{j}{n-k-j}.$

Note that

$\frac{1+y-x^{2}y^{2}}{(1-xy)(1-xy^{2})-xy^{3}}=f(x,y)+yf(x,y)-x^{2}y^{2}f(x,y),$

then

$\displaystyle~{}[x^{k}][y^{n}]\frac{1+y-x^{2}y^{2}}{(1-xy)(1-xy^{2})-xy^{3}}$
$\displaystyle=[x^{k}][y^{n}]f(x,y)+[x^{k}][y^{n-1}]f(x,y)-[x^{k-2}][y^{n-2}]f(x,y)$
$\displaystyle=\sum_{j=0}^{k}\binom{n-2j}{k-j}\binom{j}{n-k-j}+\sum_{j=0}^{k}\binom{n-2j-1}{k-j}\binom{j}{n-k-j-1}$
$\displaystyle~{}-\sum_{j=0}^{k}\binom{n-2j-2}{k-j-2}\binom{j}{n-k-j}.$

$\square$

We have a similar result as Corollary 3.7 as follows.

######  Corollary 3.23.

For $n\geq 3$,

$\sum_{k=0}^{n}d_{n,k}=2F_{n}.$

###  3.5 Indegree and outdegree polynomials

The indegree polynomial of $\Phi_{n}$ is
$D_{n}^{-}(x)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}d_{n,k}^{-}x^{k}$, where
$d_{n,k}^{-}$ denoted the number of vertices of the indegree $k$ in
$\Phi_{n}$, or the number of anti-chains with only $k$ elements in $\Phi_{n}$,
or the number of the element covered only by $k$ elements in $\Phi_{n}$. The
first few of $D^{-}_{n}(x)$ are listed.

$\displaystyle D_{0}^{-}(x)$ $\displaystyle=1$ $\displaystyle D_{1}^{-}(x)$
$\displaystyle=1+x$ $\displaystyle D_{2}^{-}(x)$ $\displaystyle=1+2x$
$\displaystyle D_{3}^{-}(x)$ $\displaystyle=1+3x$ $\displaystyle D_{4}^{-}(x)$
$\displaystyle=1+4x+x^{2}$ $\displaystyle D_{5}^{-}(x)$
$\displaystyle=1+5x+4x^{2}$ $\displaystyle D_{6}^{-}(x)$
$\displaystyle=1+6x+8x^{2}+x^{3}$ $\displaystyle D_{7}^{-}(x)$
$\displaystyle=1+7x+13x^{2}+5x^{3}.$

######  Proposition 3.24.

For $n\geq 3$ and $k\geq 1$,

$d_{n,k}^{-}=d_{n-1,k}^{-}+d_{n-2,k-1}^{-}.$

######  Proposition 3.25.

For $n\geq 5$,

$D_{n}^{-}(x)=D_{n-1}^{-}(x)+xD_{n-2}^{-}(x).$

######  Lemma 3.26 ([12]).

For $n\geq 0$,

$D_{n}^{-}(1+x)=Q_{n}(x).$

By Propositions 3.24, 3.25 and Lemma 3.26, a similar argument as proof of
Theorem 3.4 gives the generating function of $D^{-}_{n}(x)$ as follows.

######  Theorem 3.27.

The generating function of $D_{n}^{-}(x)$ is

$\sum_{n\geq
0}D_{n}^{-}(x)y^{n}=\frac{1+xy-x^{2}y^{3}-x^{2}y^{4}}{1-y-xy^{2}}.$

######  Proposition 3.28.

For $n\geq 0$,

$D_{n}^{-}(x)=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\left(\binom{n-k-2}{k-1}+\binom{n-k}{k}\right)x^{k}.$

Thus

$d_{n,k}^{-}=\binom{n-k-2}{k-1}+\binom{n-k}{k}.$

We have a similar result as Corollary 3.7 on indegree of each vertex of the
Fibonacci-like cubes from the fence-like posets.

######  Corollary 3.29.

For $n\geq 3$,

$\sum_{k=0}^{n}d_{n,k}^{-}=\sum_{k=0}^{n}\left(\binom{n-k-2}{k-1}+\binom{n-k}{k}\right)=2F_{n}.$

The conclusion of outdegree is similar to those of indegree.

## References

  * [1] L. Comtet.  Advanced Combinatorics: The art of finite and infinite expansions.  D. Reidel Publishing Company, Dordrecht, enlarged edition, 1974.
  * [2] W. J. Hsu.  Fibonacci cubes-a new interconnection topology.  IEEE Trans. Parallel Distrib. Syst., 4(1):3–12, Jan. 1993.
  * [3] S. Klavžar, M. Mollard, and M. Petkovšek.  The degree sequence of Fibonacci and Lucas cubes.  Discrete Math., 311(14):1310–1322, 2011.
  * [4] S. Klavžar and M. Mollard.  Cube polynomial of Fibonacci and Lucas cubes.  Acta Appl Math, 117(1):93–105, 2012.
  * [5] Munarini, E., Cippo, C. P., and Salvi, N. Z.  On the Lucas cubes.  Fibonacci Quarterly 39, 1 (2001), 12–21.
  * [6] M. Mollard.  Maximal hypercubes in Fibonacci and Lucas cubes.  Discrete Appl. Math., 160(16):2479–2483, 2012.
  * [7] E. Munarini and N. Zagaglia Salvi.  On the rank polynomial of the lattice of order ideals of fences and crowns.  Discrete Math., 259(1):163–177, 2002.
  * [8] Klavžar, S.  Structure of Fibonacci cubes: a survey.  J Combin Optim 25, 4 (2013), 505–522.
  * [9] E. Saygı and Ö. Eğecioğlu.  $q$-counting hypercubes in Lucas cubes.  Turkish J. Math., 42(1):190–203, 2018.
  * [10] N. J. A. Sloane.  On-line encyclopedia of integer sequences.  http://oeis.org/, 2019.
  * [11] R. P. Stanley.  Enumerative Combinatorics: Volume 1, volume 49 of Cambridge studies in advanced mathematics.  Cambridge University Press, Cambridge, 2nd edition, 2011.
  * [12] X. Wang, X. Zhao, and H. Yao.  Convex expansion for finite distributive lattices with applications.  arXiv: 1810.06762, 2018.
  * [13] X. Wang, X. Zhao, and H. Yao.  Structure and enumeration results of matchable Lucas cubes.  arXiv: 1810.07329, 2018.