# Connectivity in high dimensional grids

The journal version of The Effects of Faults on Network Expansion, with Bagchi, Bhargava, Chaudhury, and Scheideler, in *Theory of Computing Systems*, has been put online by the publisher. It's about showing that certain network connectivity structures are robust against failures — if a small enough fraction of nodes fail, many of the remaining nodes can still be connected together to form a subgraph that is not just connected, but nearly as well connected as the original graph in terms of its expansion.

My contribution was a lemma about high dimensional grids: suppose \( S \) is a collection of points in the integer lattice \( \mathbb{Z}^d \), that \( S \) is connected orthogonally, and that the complement of \( S \) is also connected. Let \( B \) be the points in \( S \) that are adjacent to a point not in \( S \) (a discrete analog of the boundary of \( S \)). \( B \) may not be orthogonally connected (think of the boundary of an X pentomino) but what I could show is that, if one connects any two points in \( B \) that are at distance at most \( \sqrt{2} \) from each other, the resulting graph is connected, regardless of dimension. This turned out to be the key for showing the desired robustness results for grid-connected computer networks, and I was very pleased to be able to use some baby homology theory in the proof.