Pair-Defensive Silver Colourings of Hypercubes

@misc{farhat2026pairdefensive,
  title = {{Pair-Defensive Silver Colourings of Hypercubes}},
  author = {Saman Farhat and Mehrak Shirkhani},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.38993},
  eprint = {2609.38993},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38993},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Pair-Defensive Silver Colourings of Hypercubes
AU  - Saman Farhat
AU  - Mehrak Shirkhani
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.38993
UR  - https://arxiv.org/abs/2609.38993
AB  - A silver colouring is a proper colouring in which every colour appears in the closed neighbourhood of each vertex of a prescribed independent set. This local condition suffices when vertices are tested one at a time. We study a stronger requirement for simultaneous testing: whenever one or two vertices of the independent set are attacked together, each colour must supply distinct nearby defenders for them. We call this a pair-defensive silver colouring. For the hypercube Q_d, with one parity class as the attacked set, we prove that the maximum number of colours in a pair-defensive silver colouring is at most ⌊(d+3)/2⌋, roughly half the ordinary silver-colouring target d+1. We construct colourings attaining this bound in four consecutive dimensions around every power of two, and we study the structure of the extremal, bound-attaining colourings. In each odd critical dimension, we characterize the extremal colourings by a partition of the defender parity into regular, triangle-free subgraphs of the halved cube. This characterization also has a local form in terms of coordinate matchings and a defect coordinate
ER  -