Frobenius problem and dead ends in integers (Q2483162): Difference between revisions

Let \(G\) be a group generated by a finite set \(S\). The word length of an element \(g\) with respect to \(S\), denoted by \(l(g)\), is the shortest length of a group word over \(S\) representing \(g\). The Cayley graph of \(G\) with respect to \(S\) is the graph whose vertices are the elements of \(G\) and in which two vertices \(g\) and \(h\) are connected by an edge if and only if \(g= hs\) for some \(s\) in \(S\cup S^{-1}\). A dead end in \(G\) with respect to \(S\) is an element \(d\) in \(G\) such that \(l(ds)\leq l(d)\) for every \(s\) in \(S\cup S^{-1}\). In this paper, the author gives a connection of dead ends in Cayley graphs with the Diophantine Frobenius problem. The author also describes all dead ends when \(G= \mathbb Z\) in the case when \(S\) consists of two elements. In an appendix, the author shows that every finitely generated group has a generating set with respect to which dead ends exist.