Notes on Adjacency

Let x=(i,j) be in I x I, where I is the set of integers. The four pairs (i+1,j), (i-1,j), (i,j+1), and (i,j-1) are the 4-neighbors of x and are said to be 4-adjacent to x. The 8-neighbors and 8-adjacency are similarly defined.

If S and T are subsets of I x I, then S is 4- or 8-adjacent to T if some x in S is 4- or 8-adjacent to some y in T.

A path from x to y is a sequence of distinct points such that each is adjacent to its predecessor.

x and y in S are connected in S if there is a path from x to y entirely in S. Connected is an equivalence relation, and the equivalence classes are called the connected components of S. If S has only one component, S is called connected.

Proposition: If S contains T, every component of T is contained in a unique component of S.

Let S' be the complement of S. If S is finite, all points of S' that are sufficiently far from the origin are evidently connected in S'. It follows that exactly one component of S' is infinite; we call this the background of S. All other components of S', if any, are called holes in S. If S is connected and has no holes, it is called simply-connected.

We assume from now on that S is finite. We shall sometimes refer to points of S as 1's and to points of S' as 0's. Many of the theorems that can be proved about connectedness hold only if opposite adjacency definitions are used for S and S'. Then we have only two types of simply-connected S's: a 4-connected S that has no 8-holes, and an 8-connected S that has no 4-holes.

Proposition: If S' is connected, every component of S is simply-connected. If S' has k+1 components, no component of S has more than k holes.

By the border of S we mean the set of points of S that are adjacent to the points of S'. More generally, if C is a component of S, and D is a component of S', by the D-border of C we mean the set of points of C that are adjacent to the points of D. From now on we assume adjacent means 4-adjacent.

Let B be the background component of S', and let F, G be distinct components of S or S'. We say that G surrounds F, or that F is inside G, if any 4-path from any point of F to any point of B must also meet G. B surrounds every other component of S or S'.

Theorem: Let C be a component of S, and D a component of S' that is adjacent to C. Then either C surrounds D or D surrounds C; moreover, exactly one such D sourrounds C.