Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question feels completely trivial and I am somewhat embarrassed to be asking it, but I am having a brain dead moment and failing to prove what I'm sure is a completely trivial statement about groups; I think the proof will probably be a 1- or 2-line affair.

I have a finite connected Cayley graph with $n$ vertices (or elements), with generating set $S \cup S^{-1}$ (so we assume $S$ spans the group), and I want to write a general element $x$ in terms of the generators. I wish to show that we can always write as a product of generators $x = g_1 \ldots g_m$, where $m \leq n/2$; i.e. we can always write an element as a product of generators of length at most half the order of the group.

For the theorem I am using this to prove, I also assume $S \cup S^{-1}$ is closed under conjugation, i.e. contains full conjugacy classes, but I don't think this is needed here. In case I'm actually not being stupid (though I'm 95% sure I am), the shorter the proof possible, the better.

Thanks for your help, and for putting me out of my misery!

share|improve this question

2 Answers 2

This might not be the best argument, but it seems to work. First, no nontrivial finite, connected, vertex-transitive graph has a cutpoint (nontrivial here means something like cardinality at least $3$ to avoid having to define cutpoint carefully). If it did, then every vertex would be a cutpoint, so you could inductively build an arbitrarily long finite path of distinct vertices $(v_n)$ by choosing $v_{n+1}$ to live in a connected component of $G \setminus \{v_n\}$ which does not contain any of $v_1, \ldots, v_{n-1}$ (which necessarily live in the same component, as they are a path).

So any set whose deletion disconnects the graph has cardinality at least $2$. We claim in this case that the graph-theoretic distance between any two vertices is at most one half the total number $n$ of vertices, which is enough to get what you want. Fix any vertex $v$ and put $S_i$ to equal the set of points of distance $i$ from $v$. So $S_0 = \{v\}$, $S_1$ is the neighbors of $v$, and so on. Say $r \geq 1$ is maximal such that $S_r$ is nonempty; we want to show that $r \leq n/2$.

Note that for each $i \in \{1, \ldots, r-1\}$, $S_i$ is a cutset of the graph, since any path from $v$ to a point in $S_r$ must pass through a point in $S_i$. So the cardinality of $S_i$ is at least $2$. Then $$ n = |S_0| + |S_1| + \cdots + |S_r| \geq 1 + 2(r-1) + 1, $$ from which we conclude $r \leq n/2$.

share|improve this answer
    
Of course this argument doesn't use any of the algebraic structure of the group. There's probably a much better proof which exploits the group structure. –  user83827 Mar 30 '12 at 22:18
    
Since it's really a fact about finite vertex-transitive graphs rather than specifically about Cayley graphs, I think it's nice to prove it this way. –  Tara B Mar 30 '12 at 23:10
    
I thought you might be able to attack the problem by considering Hamiltonian cycles and then showing that one of the 2 paths in any Hamiltonian cycle between any 2 given vertices must have length at most $n/2$. Unfortunately I then read about the Lovász conjecture and realised that wasn't going to work out. It does seem to me like there should be a more concise proof of this though, it looks like elementary group theory but I'm afraid it's stumped me. –  Spyam Mar 31 '12 at 5:34
    
(Still, I like your solution!) –  Spyam Mar 31 '12 at 5:36

I can think of another proof in your specific situation ($S\cup S^{-1}$ closed under conjugation), but I don't see how to modify it to not need that assumption, and I prefer ccc's proof.

For $g\in G$, let $|g|_S$ denote the minimum length of a word in elements of $S\cup S^{-1}$ representing $g$. Note that $S\cup S^{-1}$ being closed under conjugation implies that for any $g,h\in G$ we have $|g^{-1}hg|_S = |h|_S$.

Suppose $x\in G$ with $|x|_S = m>\frac{n}{2}$ and write $x = g_1 g_2\ldots g_m$ with $g_i\in S\cup S^{-1}$. Then the prefixes $g_1\ldots g_i$ are all distinct. Also $g_m^{-1}\ldots g_1^{-1}$ is a shortest word representing $x^{-1}$ and so the prefixes $g_m^{-1}\ldots g_i^{-1}$ are all distinct.

Now, including $1_G$, we have found $2m+1\geq n+2$ elements of $G$, and so $g_1\ldots g_i =_G g_m^{-1}\ldots g_j^{-1}$ for some $1\leq i,j <m$. But then $x = g_1 \ldots g_i g_{i+1}\ldots g_m = g_m^{-1}\ldots g_j^{-1} g_{i+1}\ldots g_m$. So $x = g_m^{-1}hg_m$, where $|h|_S \leq m - 2$. But this implies $|x|_S \leq m-2$, a contradiction.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.