Exact majority C-colourings of balanced Hamming graphs and grids
A majority C-colouring partitions a graph into classes in which every vertex has at least half of its neighbours. Write $M(G)$ for the maximum number of classes. We determine $M(K_q^{\square(2k+1)})=\left\lfloor\frac{q^{k+1}}{\lfloor q/2\rfloor+1}\right\rfloor\qquad(q\ge3,\ k\ge0).$ The lower bound follows from explicit rectangular partitions and a uniform three-dimensional bridge. A punctured-rectangle construction supplies both the bridge and a partition in the intermediate dimension. The upper bound is a classical consequence of Hamming edge isoperimetry; an elementary proof is included.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.31674
curl -X POST /api/v1/records/arxiv/2609.31674/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.31674/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'