Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs

Steven Schlicker Grand Valley State University Department of Mathematics

1 Campus Drive Allendale, MI 49401 USA

    schlicks@gvsu.edu

Roman Vasquez Auburn University Department of Mathematics and Statistics 221 Parker Hall Auburn, AL 36849 USA

                                      roman.vasquez@auburn.edu

Rachel Wofford Pacific Northwest National Laboratory 1100 Dexter Ave N. Seattle, WA 98109 USA

                       re.wofford@pnnl.gov

Abstract

The Hausdorff metric provides a way to measure the distance between nonempty compact sets in ℝ^{N}, from which we can build a geometry of sets. This geometry is very different than the standard Euclidean geometry and provides many interesting results. In this paper we focus on line segments in this geometry, where pairs of disjoint sets A and B satisfying certain distance conditions have the property that there are exactly m different sets on the line segment \overline{AB} at every distance from A, where m can assume many values different than one. We provide new families of sets that generate previously unrecorded integer sequences via these values of m by connecting the values of m to the number of edge coverings of a graph corresponding to the sets A and B.

1 Introduction

The Hausdorff metric h imposes a geometry on the hyperspace H(ℝ^{N}) of all nonempty compact subsets of ℝ^{N}. One notion of betweenness in this geometry is an extension of betweenness in Euclidean geometry. For certain positive integers m, there exists a pair of disjoint finite sets A and B for which there are m = #([A, B]) different sets on the line segment defined by these sets at every distance from one of the sets. There are many fascinating and interesting properties of these numbers m = #([A, B]). For example, for each integer m between 1 and 18 there exist sets A and B such that #([A, B]) = m, but no such sets exist for m = 19. Further discussion of this can be found in Section 3.

The number #([A, B]) is related to edge covers of bipartite graphs, which is explained in more detail in Section 4. For each fixed value of m, varying the size of one of the partite sets yields different numbers of edge covers, generating integer sequences. These sequences help us understand more about line segments in H(ℝ^{N}) and edge covers of graphs.

2 The Hausdorff metric

Felix Hausdorff introduced the Hausdorff metric h in the early 20th century as a way to measure the distance between compact sets. The Hausdorff metric imposes a geometry on the space H(ℝ^{N}), which is the subject of our study. Throughout, we let d_{E} denote the standard Euclidean metric in ℝ^{N}.

Definition 1. The Hausdorff distance h between sets A and B in H(ℝ^{N}) is

h(A, B) = max{d(A, B), d(B, A)},

where

d(A, B) = max_{a∈A}{d(a, B)}

and

d(x, A) = min_{a∈A}{d_{E}(x, a)}

for every x ∈ A.

In other words, to find the distance d(A, B) from set A to set B, we measure the Euclidean distance from a point x in A farthest from B to a point in B closest to x. The Hausdorff distance between A and B is then the larger of d(A, B) and d(B, A). The mapping h in Definition 1 is called the Hausdorff metric. The proof that h is a metric can be found in many topology texts, see Barnsley or Edgar [1, 6], for example.

Example 2. Let a_{1} = (−2, 0), a_{2} = (−1, 0), b_{1} = (1, −1), and b_{2} = (1, 1) in ℝ^{2}, and define segments A and B in ℝ^{2} as A = \overline{a_{1}a_{2}} and B = \overline{b_{1}b_{2}} as shown at left in Figure 1. In this example, d(A, B) = d_{E}(a_{1}, (1, 0)) = 3 and d(B, A) = d_{E}(b_{1}, a_{2}) = \sqrt{5}. So h(A, B) = 3. (Note that d itself is not a metric since d is not symmetric.)

Figure 1: Left: Segments A and B. Right: Dilations of the segments.

3 Betweenness and finite configurations

We can use the Hausdorff metric to extend the notion of Euclidean betweenness to H(ℝ^{N}).

Definition 3. Let A, B, and C be in H(ℝ^{N}). The set C is between A and B in H(ℝ^{N}) if

h(A, B) = h(A, C) + h(C, B).

We adopt the notation ACB from Blumenthal [3] when C is between A and B. So, as in Euclidean geometry, the line segment determined by A ≠ B in H(ℝ^{N}) is the set of all sets C satisfying ACB.

The Hausdorff metric is a complicated one, and it is generally not clear how to determine which sets lie on a given line segment. One construction that helps in this regard is the dilation of a set.

Definition 4. Let A be in H(ℝ^{N}) and let s be a positive real number. The dilation of A by s is the set

(A)_{s} = {x ∈ ℝ^{N} | d_{E}(x, a) ≤ s for some a ∈ A}.

Example 5. Consider again the segments A and B presented in Example 2. In this case, we have r = h(A, B) = 3. Let s be a real number between 0 and 3 and let t = r − s. See Figure 1 at right for illustrations of the dilations (A)_{s} and (B)_{t} for a fixed value of s.

The dilation of a set A by s has two important properties. The first is that h(A, (A)_{s}) = s. The second is that if C satisfies ACB, then C ⊆ (A)_{s} ⟺ d(C, A) ≤ s [5, Theorem 4]. It follows that C satisfies ACB with h(A, C) = s, then C is a subset of (A)_{s} ∩ (B)_{h(A,B)−s}. An example of this intersection is shown at right in Figure 1. In fact, Bogdewicz [4] shows that the set C_{s} = (A)_{s} ∩ (B)_{h(A,B)−s} always satisfies AC_{s}B with h(A, C_{s}) = s.

Given sets A and B in H(ℝ^{N}), there are two possibilities for sets C that satisfy ACB. Blackburn et al. [2] show that if there is a point a ∈ A or a point b ∈ B such that d(a, B) ≠ h(A, B) or d(b, A) ≠ h(A, B), then there are infinitely many different sets C that satisfy ACB and d(A, C) = s for any 0 < s < h(A, B). The other possibility is the one of interest in this paper and we call such a pair of sets a configuration.

Definition 6. A configuration is a pair A, B of sets in H(ℝ^{N}) such that d(a, B) = d(b, A) = h(A, B) for every a ∈ A and b ∈ B.

We will denote the configuration pair A, B as [A, B]. Blackburn et al. [2] demonstrate that if A and B are finite sets such that [A, B] is a finite configuration, then there is a finite number k such that there are exactly k sets C satisfying ACB with h(A, C) = s for every 0 < s < h(A, B). We denote this number k of sets C satisfying ACB for a finite configuration [A, B] – that is, the number of different sets which exist at the same location on the line segment between A and B in H(ℝ^{N}) – by #([A, B]). Moreover, the number of sets C with ACB and h(A, C) = s is the same for every value of s. Lund et al. [8] show that there are infinitely many different integers that appear as #([A, B]) – all of the Fibonacci numbers and even indexed Lucas numbers, for example. Every integer between 1 and 18 is #([A, B]) for some [A, B], and every number between 20 and 36 is #([A, B]) for some [A, B]. However, Blackburn et al. [2] show that there is, surprisingly, no configuration [A, B] with #([A, B]) = 19, and Honigs [7] proves that there is no configuration [A, B] with #([A, B]) = 37. Ovsyannikov [9] extends these results to show that there exist no configurations [A, B] with #([A, B]) equal to 41, 59, or 67.

4 Bipartite graphs

We are interested in determining which integers can occur as #([A, B]) for some finite configuration [A, B]. As we will see, there is a correspondence between finite configurations and bipartite graphs, and #([A, B]) is equal to the number of edge covers of the corresponding graph.

We use the standard terminology and notation from graph theory. We consider simple graphs G = (V, E) where V is the vertex set and E is the edge set. We say that two vertices are adjacent if they have an edge in common, two edges are incident if they share a vertex, and an edge and a vertex are incident if the edge contains the vertex. A bipartite graph is a graph G = (V, E) such that there exist disjoint sets V_{1} and V_{2} (called parts) such that V = V_{1} ∪ V_{2} and there are no adjacent vertices within a part.

Now we make the connection between finite configurations and bipartite graphs. Given A and B in H(ℝ^{N}), any set C that lies on the line segment \overline{AB} must satisfy h(A, C) = s and h(C, B) = h(A, B) − s for some 0 < s < h(A, B). This implies that C ⊆ (A)_{s} ∩ (B)_{h(a,b)−s}. If [A, B] is a finite configuration, then (A)_{s} ∩ (B)_{h(A,B)−s} is a finite set as illustrated at left in Figure 2, where A = {a_{1}, a_{2}}, B = {b_{1}, b_{2}}, and C = {c_{1}, c_{2}, c_{3}, c_{4}}.

We can represent this configuration as a bipartite graph. If [A, B] is a finite configuration, let V = A ∪ B, and let E be the set {(a, b) : a ∈ A and b ∈ B such that d_{E}(a, b) = h(A, B)}. Then G_{[A,B]} = (V, E) forms a bipartite graph with parts A and B and edge set E. Notice Figure 2: Left: Sets on the line segment \overline{AB} in H(ℝ^{N}). Right: A corresponding bipartite graph.

that if C satisfies ACB with h(A, C) = s, then each point c ∈ C satisfies a_{c}cb_{c} for some a_{c} ∈ A and b_{c} ∈ B, with d_{E}(a_{c}, c) = s. This point c can be identified with the edge (a_{c}, b_{c}) in G_{[A,B]} as illustrated at right in Figure 2. The set E_{C} = {(a_{c}, b_{c}) : c ∈ C} is a subset of E. The subsets C of (A)_{s} ∩ (B)_{h(a,b)−s} that satisfy ACB are those sets C such that every a ∈ A is a distance s from some c ∈ C, and every b ∈ B is a distance h(a, b) − s from some c′ ∈ C. In graph theory terms, E_{C} will not isolate any vertices in V. Such a set is called an edge cover.

Definition 7. An edge cover of a graph G = (V, E) is a subset E′ of the set E such that every vertex in V is incident to at least one edge in E′.

So E_{C} is an edge cover of G_{[A,B]}. Thus, #([A, B]) is equal to the number of edge covers of G_{[A,B]}. Similarly, every bipartite graph can be viewed as a finite configuration [2, Configuration Construction Theorem]. We also use the notation #(G) for the number of edge coverings of a graph G.

5 Edge covers of complete bipartite graphs

To understand which integers can appear as #([A, B]) for a finite configuration [A, B], we investigate edge covers of bipartite graphs. In an attempt to be systematic, we begin with the complete bipartite graphs, then study what happens when we begin to remove edges. We let K_{m,n} denote the complete bipartite graph with parts V_{1} and V_{2}, where |V_{1}| = m and |V_{2}| = n. Throughout, we assume m ≤ n.

We can also calculate the number of edge covers of a bipartite graph using biadjacency matrices whose entries are all 0 or 1 (a {0, 1} matrix). The biadjacency matrix of a bipartite graph with parts V_{1} and V_{2} of size m and n is an m×n matrix whose ijth entry is 1 if the ith vertex in V_{1} is adjacent to the jth vertex in V_{2} and is 0 otherwise. Since an edge cover cannot isolate a vertex, the number of edge covers of such a bipartite graph is equal to the number of {0, 1} m × n matrices with no zero rows or columns. This number is well-known and can be calculated through a standard inclusion-exclusion principle argument. The next theorem provides the result. (Entry \underline{A048291} in the Online Encyclopedia of Integer Sequences (OEIS) gives this formula for n × n matrices.)

Theorem 8. Let E(m, n) be the number of edge covers of a K_{m,n} complete bipartite graph. Then

E(m, n) = ∑_{j=0}^{m} \binom{m}{j}(−1)^{j}(2^{m−j} − 1)^{n}.

With this result in hand, we proceed to determine the number of edge covers of the graphs that result from K_{m,n} by removing one to three edges.

6 Edge covers of K_{m,n} minus one edge

To calculate the number of edge covers of a complete bipartite graph that is missing edges, we use the following proposition from Honigs [7].

Proposition 9. Let G={V, E} be a graph. Let v_{1}, v_{2} ∈ V, and suppose (v_{1}, v_{2}) ∉ E. Let G′ = {V, E′} where E′=E ∪ {(v_{1}, v_{2})}. Then

#(G′) = 2#(G) + #(G − v_{1}) + #(G − v_{2}) + #(G − v_{1} − v_{2}).

We use Proposition 9 to determine the number of edge covers of graphs obtained from complete graphs by removing one, two, or three edges. We begin with removing one edge.

Theorem 10. Let G be a graph obtained from a complete bipartite graph K_{m,n} after removing one edge. Then the number of edge covers of G is E_{1}(m, n) where

E_{1}(m, n) = #(G) = \frac{1}{2}(E(m, n) − E(m − 1, n) − E(m, n − 1) − E(m − 1, n − 1)). (1)

(The function E in Theorem 10 is defined in Theorem 8.)

Proof. Let the graph G′ be a complete bipartite graph and the graph G be G′ missing one edge, (v_{1}, w_{1}). Since we are only removing one edge, the completeness of K_{m,n} implies that it does not matter which edge. Solving for #(G) in Proposition 9 gives

#(G) = \frac{1}{2}(#(G′) − #(G − v_{1}) − #(G − w_{1}) − #(G − v_{1} − w_{1})).

As depicted in Figure 3, removing vertex v_{1} from G produces a K_{m−1,n} graph. Removing vertex w_{1} from G produces a K_{m,n−1} graph. Removing vertices v_{1} and w_{1} from G produces

K_{m,n} minus the edge (v_{1}, v_{2})  K_{m,n} minus the vertex v_{1}

K_{m,n} minus vertex v_{2}  K_{m,n} minus vertices missing vertices v_{1} and v_{2}

Figure 3: Calculating #(K_{m,n} minus an edge).

a K_{m−1,n−1} graph. Therefore

#(G) = \frac{1}{2}(#(K_{m,n}) − #(K_{m−1,n}) − #(K_{m,n−1}) − #(K_{m−1,n−1}))

= \frac{1}{2}(E(m, n) − E(m − 1, n) − E(m, n − 1) − E(m − 1, n − 1)).

As a result of Theorem 10, we obtain integer sequences by fixing the value of m in calculations of E_{1}(m, n) and letting n change. As examples, we have the sequences given in Table 1 (sequences simplified with a computer algebra system). The first entry appears as sequences \underline{A024023} and \underline{A103453} in the OEIS. This graph theoretic approach to these sequences provides a new perspective from which to view these sequences

\begin{matrix}E_{1}(2, n) & 3^{n−1} − 1 \\ E_{1}(3, n) (\underline{A335608}) & 3 · 7^{n−1} − 5 · 3^{n−1} + 2 \\ E_{1}(4, n) (\underline{A335609}) & 7 · 15^{n−1} − 16 · 7^{n−1} + 4 · 3^{n} − 3 \\ E_{1}(5, n) (\underline{A335610}) & 15 · 31^{n−1} − 43 · 15^{n−1} + 46 · 7^{n−1} − 22 · 3^{n−1} + 4 \\ E_{1}(6, n) (\underline{A335611}) & 31 · 63^{n−1} − 106 · 31^{n−1} + 145 · 15^{n−1} − 100 · 7^{n−1} + 35 · 3^{n−1} − 5 \end{matrix}

Table 1: Sequences (E_{1}(m, n))_{n≥m}.

It is not difficult to see from the sum (1) and Theorem 8 that the highest power exponential term in E_{1}(m, n) comes from the summands E(m, n) and E(m, n − 1). This term is

\frac{1}{2}((2^{m} − 1)^{n} − (2^{m} − 1)^{n−1}) = (2^{m−1} − 1)(2^{m} − 1)^{n−1}.

So the sequence (E_{1}(m, n))_{n≥m} behaves asymptotically as (2^{m} − 1)^{n−1} as n increases.

To conceptualize how edge covers of complete bipartite graphs missing one edge relate to the Hausdorff metric geometry, we consider the graph G that is K_{6,2} missing one edge. Since E_{1}(6, 2) = 242 we know that G has 242 edge covers. The corresponding configuration [A, B] with A = {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}} and B = {b_{1}, b_{2}} is illustrated in Figure 4. Because #([A, B]) = #(G), the number of distinct sets C that lie on the segment \overline{AB} in H(ℝ^{N}) at any fixed distance from A is also 242.

Figure 4: A configuration [A, B].

7 Edge covers of K_{m,n} minus two edges

The next step in our calculations of numbers of edge covers of subgraphs of complete bipartite graphs is to consider the case of removing two edges. When we remove two edges from a complete bipartite graph, there are three different cases for the number of edge covers of the graph that are based upon the vertices from which the two edges are removed.

Theorem 11. Let G be a K_{m,n} complete bipartite graph missing two edges. Partition the vertex set V of G into two parts, V_{1} and V_{2}, where |V_{1}| = m and |V_{2}| = n.

1. The number of edge covers of G when the 2 removed edges are incident to the same vertex in V_{1} and not incident to the same vertex in V_{2} is E_{2_{1}}(m, n) where

E_{2_{1}}(m, n) = #(G) = \frac{1}{2}(E_{1}(m, n) − E(m − 1, n) − E_{1}(m, n − 1) − E(m − 1, n − 1)).

2. The number of edge covers of G when the 2 removed edges are not incident to the same vertex in V_{1} but are incident to the same vertex in V_{2} is E_{2_{2}}(m, n) where

E_{2_{2}}(m, n) = #(G) = \frac{1}{2}(E_{1}(m, n) − E_{1}(m − 1, n) − E(m, n − 1) − E(m − 1, n − 1)).

3. The number of edge covers of G when the 2 removed edges are not incident to the same vertex in V_{1} and are not incident to the same vertex in V_{2} is E_{2_{3}}(m, n) where

E_{2_{3}}(m, n) = #(G) = \frac{1}{2}(E_{1}(m, n) − E_{1}(m − 1, n) − E_{1}(m, n − 1) − E_{1}(m − 1, n − 1)).

Proof. Assume the graph G′ is a K_{m,n} complete bipartite graph missing one edge. Let G be a graph obtained from G′ by removing an edge. Let the vertex set V of G be partitioned into two parts V_{1} = {v_{1}, v_{2}, …, v_{m}} and V_{2} = {w_{1}, w_{2}, …, w_{n}}. We consider three different cases based on the incidence of the removed edges to certain vertices. The removed edges can be incident to the same vertex in V_{1} but not in V_{2}, incident to the same vertex in V_{2} but not in V_{1}, or not incident to the same vertex in V_{1} or V_{2}, as illustrated from left to right, respectively, in Figure 5.

Figure 5: Case 1, Case 2, and Case 3 for removing two edges.

Case 1: Assume that the 2 removed edges in G are incident to the same vertex in V_{1} but are not incident to the same vertex in V_{2}. An illustration of such a graph G can be seen at left in Figure 6. The edges (v_{1}, w_{1}) and (v_{1}, w_{2}) are missing, and both edges are incident to vertex v_{1} in V_{1}. The graph of G′ can be seen at left in Figure 6. Notice that in the graph G′ only the edge (v_{1}, w_{1}) is missing.

The graph G′  The graph G

Figure 6: Case 1: Removing two edges incident to the same vertex.

Since G′ is a K_{m,n} complete bipartite graph missing one edge, #(G′) = E_{1}(m, n).

When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph, as seen at top left in Figure 7. So #(G − v_{1}) = E(m − 1, n).

When we remove the vertex w_{2} from G, the result is a K_{m,n−1} complete bipartite graph missing one edge, as seen at top right in Figure 7. So #(G − w_{2}) = E_{1}(m, n − 1).

The graph G − v_{1}  The graph G − w_{2}

The graph G − {v_{1}, w_{2}}

Figure 7: Case 1: Removing vertices from G.

When we remove vertices v_{1} and w_{2} from G, the result is a K_{m−1,n−1} complete bipartite graph, as seen at bottom in Figure 7. So #(G − v_{1} − w_{2}) = E(m − 1, n − 1).

Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{1}(m, n) − E(m − 1, n) − E_{1}(m, n − 1) − E(m − 1, n − 1)).

Case 2: In this case, the 2 removed edges in G are not incident to the same vertex in V_{1} but are incident to the same vertex in V_{2}. Note that this is the same case as case 1 with m and n interchanged.

Case 3: In this case, the 2 removed edges in G are not incident to the same vertex in V_{1} and are not incident to the same vertex in V_{2}. An example of such a graph G can be seen at right in Figure 8. The edges (v_{1}, w_{1}) and (v_{m}, v_{n}) are missing. Edge (v_{1}, w_{1}) is incident to a different vertex in V_{1} and a different vertex in V_{2} than edge (v_{m}, w_{n}). The graph of G′ can be seen at left in Figure 8.

The graph G′  The graph G

Figure 8: Case 3: Removing two edges incident to the same vertex.

Since G′ is a K_{m,n} complete bipartite graph missing one edge, #(G′) = E_{1}(m, n).

When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph missing one edge, as seen top left in Figure 9, so #(G − v_{1}) = E_{1}(m − 1, n).

The graph G − {v_{1}, w_{1}}

Figure 9: Case 3: Removing vertices from G.

When we remove the vertex w_{1} from G, the result is a K_{m,n−1} complete bipartite graph missing one edge, as seen top right in Figure 9, so #(G − w_{1}) = E_{1}(m, n − 1).

When we remove vertices v_{1} and w_{1} from G, the result is a K_{m−1,n−1} complete bipartite graph missing one edge, as seen at bottom in Figure 9, so #(G − v_{1} − w_{1}) = E_{1}(m − 1, n − 1).

Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{1}(m, n) − E_{1}(m − 1, n) − E_{1}(m, n − 1) − E_{1}(m − 1, n − 1)).

As a result of Theorem 11, there are three families of integer sequences given by E_{2_{i}}(m, n) with m fixed and n varying. Some of these sequences are presented in Table 2. The first entry is given in sequences \underline{A024023} and \underline{A103453} in the OEIS. Once again, this graph theoretic approach to these sequences provides a new perspective from which to view these sequences.

E_{2_{1}}(2, n)  3^{n−2} − 1
\begin{matrix}E_{2_{1}}(3, n) \\ (\underline{A335612}) \end{matrix}  9 · 7^{n−2} − 11 · 3^{n−2} + 2
\begin{matrix}E_{2_{1}}(4, n) \\ (\underline{A335613}) \end{matrix}  49 · 15^{n−2} − 76 · 7^{n−2} + 10 · 3^{n−1} − 3
\begin{matrix}E_{2_{1}}(5, n) \\ (\underline{A337416}) \end{matrix}  225 · 31^{n−2} − 421 · 15^{n−2} + 250 · 7^{n−2} − 58 · 3^{n−2} + 4
\begin{matrix}E_{2_{1}}(6, n) \\ (\underline{A337417}) \end{matrix} 961 · 63^{n−2} − 2086 · 31^{n−2} + 1615 · 15^{n−2} − 580 · 7^{n−2} + 95 · 3^{n−2} − 5

\begin{matrix}E_{2_{2}}(3, n) \\ (\underline{A337418}) \end{matrix}  7^{n−1} − 2 · 3^{n−1} + 1
\begin{matrix}E_{2_{2}}(4, n) \\ (\underline{A340173}) \end{matrix}  3 · 15^{n−1} − 8 · 7^{n−1} + 7 · 3^{n−1} − 2
\begin{matrix}E_{2_{2}}(5, n) \\ (\underline{A340174}) \end{matrix}  7 · 31^{n−1} − 23 · 15^{n−1} + 4 · 7^{n} − 5 · 3^{n} + 3
\begin{matrix}E_{2_{2}}(6, n) \\ (\underline{A340175}) \end{matrix}  15 · 63^{n−1} − 58 · 31^{n−1} + 89 · 15^{n−1} − 68 · 7^{n−1} + 26 · 3^{n−1} − 4
E_{2_{3}}(2, n)  3^{n−2}
\begin{matrix}E_{2_{3}}(3, n) \\ (\underline{A340199}) \end{matrix}  9 · 7^{n−2} − 7 · 3^{n−2} + 1
\begin{matrix}E_{2_{3}}(4, n) \\ (\underline{A340200}) \end{matrix}  49 · 15^{n−2} − 60 · 7^{n−2} + 22 · 3^{n−2} − 2
\begin{matrix}E_{2_{3}}(5, n) \\ (\underline{A340201}) \end{matrix}  225 · 31^{n−2} − 357 · 15^{n−2} + 202 · 7^{n−2} − 46 · 3^{n−2} + 3
\begin{matrix}E_{2_{3}}(6, n) \\ (\underline{A340897}) \end{matrix} 961 · 63^{n−2} − 1830 · 31^{n−2} + 1359 · 15^{n−2} − 484 · 7^{n−2} + 79 · 3^{n−2} − 4
Table 2: Sequences (E_{2_{k}}(m, n))_{n≥m}.

As an example of interpreting edge covers of complete bipartite graphs from a geometric perspective, consider the configurations [A, B] (left) and [A′, B′] (right) as shown in Figure 10, where A = A′ = {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}} and B = B′ = {b_{1}, b_{2}}. Both configurations have corresponding K_{2,6} graphs missing two edges. We have #([A, B]) = E_{2_{3}}(2, 6) = 81 and #([A′, B′]) = E_{2_{1}}(2, 6) = 80, so there are 81 distinct sets that lie on the line segment \overline{AB} at each fixed distance from A, and 80 distinct sets that lie on the line segment \overline{A′B′} at each distance from A′. These findings correspond to the sequence 3^{n−2} and the fifth term of \underline{A024023} in the OEIS, respectively.

8 Edge covers of K_{m,n} minus three edges

We will take one more step in our calculations of number of edge covers and determine the number of edge covers of a K_{m,n} complete bipartite graph missing 3 edges. In this case, there are 6 different possibilities for the removal of edges as indicated in Theorem 12. The functions E_{2_{1}}, E_{2_{2}}, and E_{2_{3}} are defined in Theorem 11.

Theorem 12. Let G be a K_{m,n} complete bipartite graph missing three edges. Let the vertex set V of G be partitioned into two parts V_{1} and V_{2} where |V_{1}| = m and |V_{2}| = n.

Figure 10: Two complete configurations missing two edges.

1. The number of edge covers of G when all 3 removed edges are incident to the same vertex in V_{1} but are incident to different vertices in V_{2} is E_{3_{1}}(m, n) where

E_{3_{1}}(m, n) = #(G) = \frac{1}{2}(E_{2_{1}}(m, n)−E(m−1, n)−E_{2_{1}}(m, n−1)−E(m−1, n−1)). (2)

2. The number of edge covers of G when all 3 removed edges are incident to different vertices in V_{1} and none of the removed edges are incident to the same vertex in V_{2} is E_{3_{2}}(m, n) where

E_{3_{2}}(m, n) = #(G) = \frac{1}{2}(E_{2_{3}}(m, n) − E_{2_{3}}(m − 1, n) − E_{2_{3}}(m, n − 1) − E_{2_{3}}(m − 1, n − 1)).

(3)

3. The number of edge covers of G when all 3 removed edges are incident to different vertices in V_{1} but all 3 removed edges are incident to the same vertex in V_{2} (note that this equation returns a value of 0 in the K_{3,n} case) is E_{3_{3}}(m, n) where

E_{3_{3}}(m, n) = #(G) = \frac{1}{2}(E_{2_{2}}(m, n)−E_{2_{2}}(m−1, n)−E(m, n−1)−E(m−1, n−1)). (4)

4. The number of edge covers of G when exactly 2 of the removed edges are incident to the same vertex in V_{1} but none of the removed edges are incident to the same vertex in V_{2} is E_{3_{4}}(m, n) where

E_{3_{4}}(m, n) = #(G) = \frac{1}{2}(E_{2_{3}}(m, n)−E_{1}(m−1, n)−E_{2_{3}}(m, n−1)−E_{1}(m−1, n−1)). (5)

5. The number of edge covers of G when all 3 removed edges are incident to different vertices in V_{1} but exactly 2 removed edges are incident to the same vertex in V_{2} is E_{3_{5}}(m, n) where

E_{3_{5}}(m, n) = #(G) = \frac{1}{2}(E_{2_{3}}(m, n)−E_{2_{3}}(m−1, n)−E_{1}(m, n−1)−E_{1}(m−1, n−1)). (6)

6. The number of edge covers of G when exactly 2 removed edges are incident to the same vertex in V_{1} and exactly 2 removed edges are incident to the same vertex in V_{2} is E_{3_{6}}(m, n) where

E_{3_{6}}(m, n) = #(G) = \frac{1}{2}(E_{2_{3}}(m, n)−E_{1}(m−1, n)−E_{1}(m, n−1)−E(m−1, n−1)). (7)

Proof. Assume the graph G′ is a K_{m,n} complete bipartite graph missing two edges. Let the graph G be a graph obtained from G′ by removing an edge. Let the vertex set V of G be partitioned into two parts V_{1} and V_{2} where |V_{1}| = m and |V_{2}| = n. We consider six different cases based on the incidence of the removed edges to certain vertices. The possible cases are those listed in Theorem 12.

Case 1: In this case, all 3 removed edges are incident to the same vertex in V_{1}. An example of a graph of G′, with edges (v_{1}, w_{2}) and (v_{1}, w_{3}) missing, and a corresponding graph G missing the additional edge (v_{1}, w_{1}) can be seen in Figure 11. All 3 edges are incident to v_{1} in V_{1} but are incident to different vertices in V_{2}.

Figure 11: The graphs for case 1.

Since G′ is a K_{m,n} complete bipartite graph missing two edges that are incident to the same vertex in V_{1} but different vertices in V_{2}, we have that #(G′) = E_{2_{1}}(m, n).

When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph, as seen in Figure 11. So #(G − v_{1}) = E(m − 1, n).

When we remove the vertex w_{1} from G, the result is a K_{m,n−1} complete bipartite graph missing two edges that are incident to the same vertex in V_{1} but incident to different vertices in V_{2}, as seen in Figure 11. So #(G − w_{1}) = E_{2_{1}}(m, n − 1).

When we remove vertices v_{1} and w_{1} from G, the result is a K_{m−1,n−1} complete bipartite graph, as seen in Figure 11. This means we can use E to calculate #(G − v_{1} − w_{1}), so #(G − v_{1} − w_{1}) = E(m − 1, n − 1).

Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{2_{1}}(m, n) − E(m − 1, n) − E_{2_{1}}(m, n − 1) − E(m − 1, n − 1)).

Case 2: In this case, all 3 edges are incident to different vertices in V_{1} and none of the vertices are incident to the same vertex in V_{2}. An example of a graph G′ missing vertices (v_{2}, w_{2}) and (v_{m}, w_{n}) and a corresponding G missing the additional edge (v_{1}, w_{1}) can be seen in Figure 12. None of the edges are incident to the same vertices in V_{1} or in V_{2}.

Figure 12: The graphs for case 2.

Since G′ is a K_{m,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 12, we can use E_{2_{3}} to calculate #(G′), so #(G′) = E_{2_{3}}(m, n).

When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 12. This means we can use E_{2_{3}} to calculate #(G − v_{1}), so #(G − v_{1}) = E_{2_{3}}(m − 1, n).

When we remove the vertex w_{1} from G, the result is a K_{m,n−1} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 12. This means we can use E_{2_{3}} to calculate #(G − w_{1}), so #(G − w_{1}) = E_{2_{3}}(m, n − 1).

When we remove vertices v_{1} and w_{1} from G, the result is a K_{m−1,n−1} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 12. This means we can use E_{2_{3}} to calculate #(G−v_{1} −w_{1}), so #(G−v_{1} −w_{1}) = E_{2_{3}}(m − 1, n − 1).

Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{2_{3}}(m, n) − E_{2_{3}}(m − 1, n) − E_{2_{3}}(m, n − 1) − E_{2_{3}}(m − 1, n − 1)).

Case 3: In this case, all 3 edges removed are incident to different vertices in V_{1} but all 3 removed edges are incident to the same vertex in V_{2}. An example of a G′ missing edges (v_{2}, w_{1}) and (v_{3}, w_{1}) along with a corresponding G missing the additional edge (v_{1}, w_{1}) can be seen in Figure 13. All 3 edges are incident to different vertices in V_{1} but are incident to vertex w_{1} in V_{2}.

Figure 13: The graphs for case 3.

Since G′ is a K_{m,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} but the same vertex in V_{2}, as seen in Figure 13, we can use E_{2_{2}} to calculate #(G′), so #(G′) = E_{2_{2}}(m, n).

When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} but the same vertex in V_{2}, as seen in Figure 13. This means we can use E_{2_{2}} to calculate #(G − v_{1}), so #(G − v_{1}) = E_{2_{2}}(m − 1, n).

When we remove the vertex w_{1} from G, the result is a K_{m,n−1} complete bipartite graph, as seen in Figure 13. This means we can use E to calculate #(G − w_{1}), so #(G − w_{1}) = E(m, n − 1).

When we remove vertices v_{1} and w_{1} from G, the result is a K_{m−1,n−1} complete bipartite graph, as seen in Figure 13. This means we can use E to calculate #(G − v_{1} − w_{1}), so #(G − v_{1} − w_{1}) = E(m − 1, n − 1).

Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{2_{2}}(m, n) − E_{2_{2}}(m − 1, n) − E(m, n − 1) − E(m − 1, n − 1)).

Case 4: In this case, exactly 2 of the removed edges are incident to the same vertex in V_{1}, but none of the removed edges are incident to the same vertex in V_{2}. An example of a graph G′ missing edges (v_{1}, w_{2}) and (v_{2}, w_{3}) along with a corresponding graph G missing the additional edge (v_{1}, w_{1}) can be seen in Figure 14. There are 2 edges incident to v_{1} in V_{1} while one edge is not. All of the edges are incident to different vertices in V_{2}.

Figure 14: The graphs for case 4.

Since G′ is a K_{m,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 14, we can use E_{2_{3}} to calculate #(G′), so #(G′) = E_{2_{3}}(m, n).

When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph missing one edge, as seen in Figure 14. This means we can use E_{1} to calculate #(G − v_{1}), so #(G − v_{1}) = E_{1}(m − 1, n).

When we remove the vertex w_{1} from G, the result is a K_{m,n−1} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and different vertices in V_{2}, as seen in Figure 14. This means we can use E_{2_{3}} to calculate #(G − w_{1}), so #(G − w_{1}) = E_{2_{3}}(m, n − 1). When we remove vertices v_{1} and w_{1} from G, the result is a K_{m−1,n−1} complete bipartite graph missing one edge, as seen in Figure 14. This means we can use E_{1} to calculate #(G − v_{1} − w_{1}), so #(G − v_{1} − v_{2}) = E_{1}(m − 1, n − 1). Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{2_{3}}(m, n) − E_{1}(m − 1, n) − E_{2_{3}}(m, n − 1) − E_{1}(m − 1, n − 1)).

Case 5: In this case, all 3 removed edges are incident to different vertices in V_{1}, but exactly 2 removed edges are incident to the same vertex in V_{2}. An example of a graph G′ missing edges (v_{2}, w_{1}) and (v_{3}, w_{3}) along with a corresponding graph G missing the additional edge (v_{1}, w_{1}) can be seen in Figure 15. All 3 edges are incident to different vertices in V_{1}, but 2 of the edges are incident to w_{1} in V_{2}.

Figure 15: The graphs for case 5.

Since G′ is a K_{m,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 15, we can use E_{2_{3}} to calculate #(G′), so #(G′) = E_{2_{3}}(m, n). When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 15. This means we can use E_{2_{3}} to calculate #(G − v_{1}), so #(G − v_{1}) = E_{2_{3}}(m − 1, n).

When we remove the vertex w_{1} from G, the result is a K_{m,n−1} complete bipartite graph missing one edge, as seen in Figure 15. This means we can use E_{1} to calculate #(G − w_{1}), so #(G − w_{1}) = E_{1}(m, n − 1).

When we remove vertices v_{1} and w_{1} from G, the result is a K_{m−1,n−1} complete bipartite graph missing one edge, as seen in Figure 15. This means we can use E_{1} to calculate #(G − v_{1} − w_{1}), so #(G − v_{1} − w_{1}) = E_{1}(m − 1, n − 1).

Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{2_{3}}(m, n) − E_{2_{3}}(m − 1, n) − E_{1}(m, n − 1) − E_{1}(m − 1, n − 1)).

Case 6: In this case, exactly 2 removed edges are incident to the same vertex in V_{1} and exactly 2 removed edges are incident to the same vertex in V_{2}. An example of a graph G′ missing edges (v_{2}, w_{1}) and (v_{1}, w_{2}) along with a corresponding graph G missing the additional edge (v_{1}, w_{1}) can be seen in Figure 16. Exactly two edges are incident to v_{1} in V_{1}, and exactly two edges are incident to w_{1} in V_{2}.

Figure 16: The graphs for case 6.

Since G′ is a K_{m,n} complete bipartite graph missing two edges that are incident to different vertices in V_{1} and V_{2}, as seen in Figure 16, we can use E_{2_{3}} to calculate #(G′), so #(G′) = E_{2_{3}}(m, n).

When we remove the vertex v_{1} from G, the result is a K_{m−1,n} complete bipartite graph missing one edge, as seen in Figure 16. This means we can use E_{1} to calculate #(G − v_{1}), so #(G − v_{1}) = E_{1}(m − 1, n).

When we remove the vertex w_{1} from G, the result is a K_{m,n−1} complete bipartite graph missing one edge, as seen in Figure 16. This means we can use E_{1} to calculate #(G − w_{1}), so #(G − w_{1}) = E_{1}(m, n − 1).

When we remove vertices v_{1} and w_{1} from G, the result is a K_{m−1,n−1} complete bipartite graph, as seen in Figure 16. This means we can use E to calculate #(G − v_{1} − w_{1}), so #(G − v_{1} − w_{1}) = E(m − 1, n − 1).

Proposition 9 then gives us

#(G) = \frac{1}{2}(E_{2_{3}}(m, n) − E_{1}(m − 1, n) − E_{1}(m, n − 1) − E(m − 1, n − 1)).

A few of the sequences given by Theorem 12 are shown in Table 3. The first entry is given in sequences \underline{A024023} and \underline{A103453}—the remainder had not been previously recorded in the OEIS.

Theorem 12 once again informs us about the number of sets that lie on certain line segments in H(ℝ^{N}) at a fixed distance from one of the endpoints. For example, if A = {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}} and B = {b_{1}, b_{2}}, then #([A, B]) = E_{3_{1}}(2, 6) = 26 when [A, B] is the configuration shown at left in Figure 17, and #([A, B]) = E_{3_{4}}(2, 6) = 27 when [A, B] is the configuration shown at right in Figure 17.

Figure 17: Two complete configurations missing three edges.

9 Conclusion

All of the sequences (E_{1}(k, n)) for k from 3 to 6, (E_{2_{i}}(k, n)) for i from 1 to 3 and k from 3 to 6, and (E_{3_{i}}(k, n)) for i from 1 to 6 and k from 4 to 6 in this investigation were previously uncatalogued integer sequences in the OEIS. It is likely that line segments in H(ℝ^{N}) (and edge covers of graphs) can provide many more examples of new integer sequences.

E_{3_{1}}(2, n)  3^{n−3} − 1
\begin{matrix}E_{3_{1}}(3, n) \\ (\underline{A340898}) \end{matrix}  27 · 7^{n−3} − 29 · 3^{n−3} + 2
\begin{matrix}E_{3_{1}}(4, n) \\ (\underline{A340899}) \end{matrix}  343 · 15^{n−3} − 424 · 7^{n−3} + 28 · 3^{n−2} − 3
\begin{matrix}E_{3_{1}}(5, n) \\ (\underline{A342580}) \end{matrix}  3375 · 31^{n−3} − 4747 · 15^{n−3} − 166 · 3^{n−3} + 1534 · 7^{n−3} + 4
\begin{matrix}E_{3_{1}}(6, n) \\ (\underline{A342796}) \end{matrix} 29791 · 63^{n−3} − 46666 · 31^{n−3} + 20305 · 15^{n−3} − 3700 · 7^{n−3} + 275 · 3^{n−3} − 5
\begin{matrix}E_{3_{2}}(3, n) \\ (\underline{A342850}) \end{matrix}  27 · 7^{n−3} − 3^{n−1}
\begin{matrix}E_{3_{2}}(4, n) \\ (\underline{A340403}) \end{matrix}  343 · 15^{n−3} − 216 · 7^{n−3} + 4 · 3^{n−1} − 1
\begin{matrix}E_{3_{2}}(5, n) \\ (\underline{A340404}) \end{matrix}  3375 · 31^{n−3} − 2891 · 15^{n−3} + 846 · 7^{n−3} − 10 · 3^{n−1} + 2
\begin{matrix}E_{3_{2}}(6, n) \\ (\underline{A340405}) \end{matrix} 29791 · 63^{n−3} − 31050 · 31^{n−3} + 12369 · 15^{n−3} − 2260 · 7^{n−3} + 19 · 3^{n−1} − 3
\begin{matrix}E_{3_{3}}(4, n) \\ (\underline{A340433}) \end{matrix}  15^{n−1} − 3 · 7^{n−1} + 3^{n} − 1
\begin{matrix}E_{3_{3}}(5, n) \\ (\underline{A340434}) \end{matrix}  3 · 31^{n−1} − 11 · 15^{n−1} + 15 · 7^{n−1} − 3^{n−1} + 2
\begin{matrix}E_{3_{3}}(6, n) \\ (\underline{A340435}) \end{matrix}  7 · 63^{n−1} − 30 · 31^{n−1} + 51 · 15^{n−1} − 43 · 7^{n−1} + 6 · 3^{n} − 3
\begin{matrix}E_{3_{4}}(3, n) \\ (\underline{A340436}) \end{matrix}  27 · 7^{n−3} − 13 · 3^{n−3} + 1
\begin{matrix}E_{3_{4}}(4, n) \\ (\underline{A340437}) \end{matrix}  343 · 15^{n−3} − 264 · 7^{n−3} + 52 · 3^{n−3} − 2
\begin{matrix}E_{3_{4}}(5, n) \\ (\underline{A340438}) \end{matrix}  3375 · 31^{n−3} − 3339 · 15^{n−3} + 1054 · 7^{n−3} − 118 · 3^{n−3} + 3
\begin{matrix}E_{3_{4}}(6, n) \\ (\underline{A341551}) \end{matrix} 29791 · 63^{n−3} − 34890 · 31^{n−3} + 14673 · 15^{n−3} − 2740 · 7^{n−3} + 211 · 3^{n−3} − 4
\begin{matrix}E_{3_{5}}(3, n) \\ (\underline{A341552}) \end{matrix}  3 · 7^{n−2} − 2 · 3^{n−2}
\begin{matrix}E_{3_{5}}(4, n) \\ (\underline{A341553}) \end{matrix}  21 · 15^{n−2} − 4 · 7^{n−1} + 11 · 3^{n−2} − 1
\begin{matrix}E_{3_{5}}(5, n) \\ (\underline{A342327}) \end{matrix}  105 · 31^{n−2} − 185 · 15^{n−2} + 116 · 7^{n−2} − 29 · 3^{n−2} + 2
\begin{matrix}E_{3_{5}}(6, n) \\ (\underline{A342328}) \end{matrix}  465 · 63^{n−2} − 982 · 31^{n−2} + 807 · 15^{n−2} − 316 · 7^{n−2} + 56 · 3^{n−2} − 3
\begin{matrix}E_{3_{6}}(3, n) \\ (\underline{A343372}) \end{matrix}  3 · 7^{n−2} − 4 · 3^{n−2} + 1
\begin{matrix}E_{3_{6}}(4, n) \\ (\underline{A343373}) \end{matrix}  21 · 15^{n−2} − 36 · 7^{n−2} + 17 · 3^{n−2} − 2
\begin{matrix}E_{3_{6}}(5, n) \\ (\underline{A343374}) \end{matrix}  105 · 31^{n−2} − 217 · 15^{n−2} + 148 · 7^{n−2} − 13 · 3^{n−1} + 3
\begin{matrix}E_{3_{6}}(6, n) \\ (\underline{A343800}) \end{matrix}  465 · 63^{n−2} − 1110 · 31^{n−2} + 967 · 15^{n−2} − 388 · 7^{n−2} + 70 · 3^{n−2} − 4

Table 3: Sequences (E_{3_{k}}(m, n))_{n≥n}.

10 Acknowledgments

This work was supported by National Science Foundation grant DMS-1659113. The authors also thank Grand Valley State University for hosting and supporting a Research Experiences for Undergraduates program.

References

[1] M. F. Barnsley, Fractals Everywhere, Second Edition, Academic Press Professional, 1998.

[2] C. Blackburn, K. Lund, S. Schlicker, P. Sigmon, and A. Zupan, A missing prime configuration in the Hausdorff metric geometry, J. Geom. 92 (2009), 28–59.

[3] L. M. Blumenthal, Theory and Applications of Distance Geometry, Oxford University Press, 1953.

[4] A. Bogdewicz, Some properties of hyperspaces, Demonstr. Math. 33 (2000), 135–149.

[5] D. Braun, J. Mayberry, A. Malagon, and S. Schlicker, A singular introduction to the Hausdorff metric geometry, Pi Mu Epsilon J. (2005), 129–138.

[6] G. A. Edgar, Measure, Topology, and Fractal Geometry, Springer-Verlag, 1990.

[7] K. Honigs, Missing edge coverings of bipartite graphs and the geometry of the Hausdorff metric, J. Geom. 104 (2013), 107–125.

[8] K. Lund, P. Sigmon, and S. Schlicker, Fibonacci sequences in the space of compact sets, Involve 1 (2008), 197–215.

[9] Z. N. Ovsyannikov, The number of edge covers of bipartite graphs or of shortest paths with fixed endpoints in the space of compact sets in R^{n} (English Translation), Dokl. Math. 93 (2016), 65–68.

[10] S. Schlicker, L. Morales, and D. Schultheis, Polygonal chain sequences in the space of compact sets, J. Integer Seq. 12 (2009).

2020 Mathematics Subject Classification: Primary 51F99; Secondary 05C99, 11B83. Keywords: Hausdorff metric, configurations, bipartite graphs, edge covers, integer sequences.

(Concerned with sequences \underline{A024023}, \underline{A048291}, \underline{A103453}, \underline{A335608}, \underline{A335609}, \underline{A335610}, \underline{A335611}, \underline{A335612}, \underline{A335613}, \underline{A337416}, \underline{A337417}, \underline{A337418}, \underline{A340173}, \underline{A340174}, \underline{A340175}, \underline{A340199}, \underline{A340200}, \underline{A340201}, \underline{A340403}, \underline{A340404}, \underline{A340405}, \underline{A340433}, \underline{A340434}, \underline{A340435}, \underline{A340436}, \underline{A340437}, \underline{A340438}, \underline{A340897}, \underline{A340898}, \underline{A340899}, \underline{A341551}, \underline{A341552}, \underline{A341553}, \underline{A342327}, \underline{A342328}, \underline{A342580}, \underline{A342796}, \underline{A342850}, \underline{A343372}, \underline{A343373}, \underline{A343374}, \underline{A343800}.)

Received September 13 2021; revised versions received March 2 2023; June 18 2023. Published in Journal of Integer Sequences, June 19 2023.

Return to Journal of Integer Sequences home page.