Embedding graphs in Cayley graphs (Q1820168)

Over ten years ago Babai showed that for any graph Y and for any sufficiently large group G, there is a Cayley graph X of G such that Y is an induced subgraph of X. The bounds given by him for \(| G|\) have been recently reduced by Babai and Sós to approximately \(9.5| Y|^ 3\). Using different methods the present paper reduces the bound to roughly \(3.7| Y|^ 3\). Better bounds are given for odd order groups and Abelian groups. It is noted that while there exist examples which show \(| G|\) must be \(O(n^ 2)\), no such examples exist which require \(| G|\) to be \(O(n^ 3)\).