Logo
All Problems Random Solved Random Open
0 solved out of 2 shown
Let $G$ be a group and let $\Gamma(G)$ be the commuting graph of $G$, with vertex set $G$ and $x\sim y$ if and only if $xy=yx$. Let $h(n)$ be minimal such that if the largest independent set of $\Gamma(G)$ has at most $n$ elements then $\Gamma(G)$ can be covered by $h(n)$ many complete subgraphs. Estimate $h(n)$ as well as possible.
Pyber [Py87] has proved there exist constants $c_2>c_1>1$ such that $c_1^n<h(n)<c_2^n$.
If $G$ is an abelian group then can there exist an exact covering of $G$ by more than one cosets of different sizes? (i.e. each element is contained in exactly one of the cosets)
A problem of Herzog and Schönheim.
Additional thanks to: Boris Alexeev and Dustin Mixon