Crown graphs maximise the representation number of bipartite graphs

@misc{colbrook2026crown,
  title = {{Crown graphs maximise the representation number of bipartite graphs}},
  author = {Matthew J. Colbrook and Catherine Drysdale},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.35842},
  eprint = {2609.35842},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.35842},
}

TY  - UNPB
TI  - Crown graphs maximise the representation number of bipartite graphs
AU  - Matthew J. Colbrook
AU  - Catherine Drysdale
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.35842
UR  - https://arxiv.org/abs/2609.35842
AB  - The representation number of a graph is the least positive integer k for which its vertices can be arranged in a word, each occurring k times, so that two distinct letters alternate precisely when the corresponding vertices are adjacent. We prove that every bipartite graph on N≥9 vertices has representation number at most ⌈ N/4⌉. Together with the known representation number of crown graphs, this settles the conjecture that crowns maximise the representation number among bipartite graphs of the same order. The proof develops a construction of Mozhui and Krishna by reducing the choice of a representing word to an ordering problem for neighbourhoods. We characterise the obstructions to this ordering and use probability estimates to exclude them for all sufficiently large balanced bipartitions. Two finite assertions complete the argument, each established by a checked Boolean unsatisfiability certificate. A refinement of the ordering argument treats the remaining odd part sizes directly. The main theorem and the crown-extremality corollary, including the finite certificate arguments, have also been formalised and verified in Lean 4.
ER  -