Erdős Problem #1098

Let $G$ be a group and $\Gamma=\Gamma(G)$ be the non-commuting graph, with vertices the elements of $G$ and an edge between $g$ and $h$ if and only if $g$ and $h$ do not commute, $gh\neq hg$.

If $\Gamma$ contains no infinite complete subgraph, then is there a finite bound on the size of complete subgraphs of $\Gamma$?

#1098: [Ne76]

group theory

Neumann [Ne76] reported this was asked by Erdős at the 15th Summer Research Institute of the Australian Mathematical Society in 1975.

This was solved by Neumann [Ne76], who proved that $\Gamma$ contains no infinite complete subgraph if and only if the centre of the group has finite index, and noted that if the centre has index $n$ then $\Gamma$ contains no complete subgraph on $>n$ vertices.

View the LaTeX source

This page was last edited 18 October 2025.

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)

0 comments on this problem

Likes this problem	None
Interested in collaborating	None
Currently working on this problem	None
This problem looks difficult	None
This problem looks tractable	None

Additional thanks to: Alfaiz

When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:

T. F. Bloom, Erdős Problem #1098, https://www.erdosproblems.com/1098, accessed 2026-01-16