Crown graphs maximise the representation number of bipartite graphs
Matthew J. Colbrook, Catherine Drysdale
math.CO
Sep 24, 2026 · v1
cs.DM
TL;DR
The main bipartite representation-number theorem and crown-extremality corollary, including the finite SAT-certificate arguments, are formalised and verified in Lean 4.
Abstract
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\ge9$ vertices has representation number at most $\lceil N/4\rceil$. 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.
Problem
The representation number of a graph is the least k such that its vertices can be arranged in a word, each occurring k times, with two letters alternating exactly when the vertices are adjacent. A conjecture states that crown graphs H_{n,n} maximise the representation number among bipartite graphs on 2n vertices.
Approach
The proof extends a construction of Mozhui and Krishna, reducing the choice of a representing word to an ordering problem for neighbourhood rank vectors. Obstructions to this ordering are characterised via an implication system on Boolean star assignments. Probability estimates over random matchings and orientations exclude obstructions for large balanced parts. The finite cases of six and eight vertices are settled by checked Boolean unsatisfiability certificates, and odd part sizes are handled by a refined ordering argument.
Results
Every bipartite graph on N ≥ 9 vertices has representation number at most ⌈N/4⌉, which settles the crown-maximisation conjecture. The theorem, the corollary, and the certificate arguments are verified in Lean 4.