Sidon sets in groups and induced subgraphs of Cayley graphs (Q1063041): Difference between revisions

A subset \(S\) of a group \(G\) is a Sidon subset of the first (second) kind if for any \(x,y,z,w\) in \(S\), of which at least 3 are different, \(xy\neq zw\) (\(xy^{-1}\neq zw^{-1}\)). For abelian groups, the two notions coincide. If \(G\) has a Sidon \(n\)-element subset of the second kind then every \(n\)-vertex graph is an induced subgraph of some Cayley graph of \(G\). Amongst other results, it is shown that (i) a sufficient condition for \(G\) to have a Sidon \(n\)-element subset (of either kind) is that \(| G| \geq cn^ 3\), (ii) for elementary Abelian groups of square order, \(| G| \geq n^ 2\) is sufficient, (iii) most \(n\)-vertex graphs are not induced subgraphs of any vertex transitive graph with \(< cn^ 2/\log^ 2n\) vertices.