EE Seminar: On Symmetric Structures in Graphs and Applications in Property Testing

~~Speaker: Amit Levi
M.Sc. student under the supervision of Prof. Dana Ron

Wednesday, June 24, 2015 at 15:30
Room 011, Kitot Bldg., Faculty of Engineering

On Symmetric Structures in Graphs and Applications in Property Testing

In this work we study different properties of graph symmetry. The first, is vertex transitivity, which informally says, that each vertex has the same global view of the graph. We give a simple one-sided error testing algorithm for vertex transitivity in the dense-graphs model, whose query complexity is $\widetilde{\Theta}(n)$. In addition, we prove that any one-sided error testing algorithm for vertex transitivity must perform $\Omega(n)$ queries  transitivity.  We also show that any two-sided error tester for vertex transitivity (which may be adaptive) must perform at least $\Omega(\sqrt{n})$ queries. In addition, we present two results in the bounded-degree graphs model. The first, is a structural result for a subclass of vertex transitive graphs. In particular, we consider $4$-regular Cayley graphs over $\mathbb{Z}_p$, where $p$ is some large prime number. We show that for every $\epsilon>0$, each $4$-regular Cayley graph over $\mathbb{Z}_p$ is either $\epsilon$-close to some graph which is isomorphic to a Cayley graph, or it contains some ``special'' cycle of size $O(1/\epsilon^2)$. This result might be useful for designing a tester for such Cayley graphs.
The second result, is a testing algorithm for a property which captures local vertex symmetry, in which every vertex has the same local view of a tree for some fixed distance $\ell$. We present a one-sided error testing algorithm for this property whose query complexity and running time are $O\left(\frac{d^\ell}{\eps}\right)$, where $d$ is the degree bound.