pith. sign in

arxiv: 1309.3251 · v1 · pith:MAQSTWGTnew · submitted 2013-09-12 · 🧮 math.CO

Edge Boundaries for a Family of Graphs on mathbb{Z}^n

classification 🧮 math.CO
keywords edgeboundarymathbbdirectionepsilonfamilygapsgraphs
0
0 comments X
read the original abstract

We consider the family of graphs whose vertex set is $\mathbb{Z}^n$ where two vertices are connected by an edge when their $\ell_\infty$-distance is 1. Towards an edge isoperimetric inequality for this graph, we calculate the edge boundary of any finite set $S \subset \mathbb{Z}^n$. This boundary calculation leads to a desire to show that a set with optimal edge boundary has no ``gaps'' in any direction $\epsilon \in \{-1,0,1\}^n, \epsilon \not=0$. We show that one can find a set with optimal edge boundary that does not have gaps in any direction $e_i$ (or $-e_i$) where $e_i$ is the standard basis vector.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.