{
  "id": "1112.1970",
  "version": "v1",
  "published": "2011-12-08T21:45:57.000Z",
  "updated": "2011-12-08T21:45:57.000Z",
  "title": "On Small Separations in Cayley Graphs",
  "authors": [
    "Martha Giannoudovardi"
  ],
  "comment": "9 pages, 2 figures",
  "categories": [
    "math.GR",
    "math.CO"
  ],
  "abstract": "We present two results on expansion of Cayley graphs. The first result settles a conjecture made by DeVos and Mohar. Specifically, we prove that for any positive constant $c$ there exists a finite connected subset $A$ of the Cayley graph of $\\mathbb{Z}^2$ such that $\\frac{|\\partial A|}{|A|}< \\frac{c}{depth(A)}$. This yields that there can be no universal bound for $\\frac{|\\partial A|depth(A)}{|A|}$ for subsets of either infinite or finite vertex transitive graphs. Let $X=(V,E)$ be the Cayley graph of a finitely generated infinite group and $A\\subset V$ finite such that $A\\cup\\partial A$ is connected. Our second result is that if $|A|> 16|\\partial A|^2$ then $X$ has a ring-like structure.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-12-08T21:45:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cayley graph",
      "small separations",
      "finite vertex transitive graphs",
      "first result settles",
      "universal bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.1970G"
    }
  }
}