---

Statement

For a group $G$, the paper's graph $\Gamma(G)$ (p. 467) has the elements of $G$ as vertices, with $g$ and $h$ joined exactly when $[g,h]\ne1$, where $[g,h]=g^{-1}h^{-1}gh$; a complete subgraph is a set of elements of $G$ no two of which commute. A PE-group is a group whose graph contains no infinite complete subgraph, and a FIZ-group is a group whose center has finite index (p. 467).

Theorem 6 (p. 470). "The group $G$ is a PE-group if, and only if, it is a FIZ-group."

That is, $\Gamma(G)$ has no infinite complete subgraph if and only if $|G:Z(G)|$ is finite.

Bound from the proof (p. 470). If $|G:Z(G)|=n$, then among any $n+1$ elements of $G$ two lie in the same coset of $Z(G)$ and so commute; hence $\Gamma(G)$ has no complete subgraph with more than $n$ vertices.

Remarks of p. 471. The paper states, without proof, that the bound $n$ "can be immediately improved to $n-1$ in general", and a little further when the arithmetic of $n$ is taken into account. The bound $n-1$ fails for abelian $G$, where $n=1$ and a single element is a complete subgraph, so "in general" is read here as covering non-abelian $G$; that reading, and the following argument for it, are this page's and not the paper's. For non-abelian $G$, a complete subgraph with at least two vertices contains no central element and meets each non-central coset of $Z(G)$ at most once, so it has at most $n-1$ vertices, and a single vertex is within the bound since $n\ge4$ when $G/Z(G)$ is not cyclic. The paper further records (p. 471):

• the value $n-1=3$ is attained by the quaternion group and by the dihedral group of order $8$; when $n=2^d$, the value $n-1$ is attained by the free group of rank $d$ of the variety generated by the quaternion group (a remark credited to M. F. Newman); for the symmetric group of degree $3$, $n=6$ while the largest complete subgraph has order $4$;
• if $\Gamma(G)$ has no complete subgraph of order greater than $m$, the proof of Theorem 6 yields $\log n=O(m^2)$, a bound the paper calls very crude; the author's guess, "based on no evidence", is $n=O(m^2)$;
• among the finite values of the exact maximum order $m$ of a complete subgraph, $2$ is the only one that does not occur: $2$ fails by Erdős's remark that for non-commuting $a,b$ the element $ab$ commutes with neither; the paper's example is the dihedral group of order $4(m-1)$, whose graph has a complete subgraph of order $m$ and none larger (the paper omits the verification; the example covers $m\ge3$, and $m=1$ is the abelian case).

Source. B. H. Neumann, A problem of Paul Erdős on groups, J. Austral. Math. Soc. Ser. A 21 (1976), 467--472, DOI 10.1017/S1446788700019303; definitions on p. 467, Theorem 6 and its proof on p. 470, remarks on p. 471. The copy read is identified on the source card.

Read depth. Claims checked: Theorem 6, the definitions it uses, its proof and the lemmas it cites were read clause by clause on the page images. The remarks of p. 471 were read but not verified; the $\log n=O(m^2)$ bound and the dihedral examples are not re-derived here. Nothing here is independently reviewed.

Proof pointer

Pages 468--470. The forward direction combines Lemma 1 (p. 468), every PE-group is an FC-group (every conjugacy class finite), proved by Ramsey's theorem, with Corollary 5 (p. 470), no group that is FC but not FIZ is a PE-group. Corollary 5 comes from Lemma 4 (pp. 469--470), which extends a pair of sequences $a_1,\dots,a_n$ and $b_1,\dots,b_n$ with the $a_i$ pairwise non-commuting, $[a_i,b_j]=1$ for $i\ne j$, $[a_i,b_i]\ne1$ and the $b_i$ pairwise commuting by one more term each, using Lemma 2 and Corollary 3 (p. 469): an FC-group with an abelian subgroup of finite index is FIZ, so the centralizer of the finitely many $a_i,b_i$, a subgroup of finite index, is not abelian. Iterating gives an infinite pairwise non-commuting sequence. The converse is the coset count above.

Dependencies

Ramsey's theorem (infinite form), and Lemmas 1, 2 and 4 and Corollaries 3 and 5 of the same paper.

Bears on

• Problem 1098: the problem asks whether a group whose non-commuting graph has no infinite complete subgraph has a finite bound on the size of its complete subgraphs. Theorem 6 makes such a group's center of finite index $n$, and the bound from its proof caps every complete subgraph at $n$ vertices, so the answer is yes.