The representation number of a graph is a way to encode its structure using words. Imagine assigning a letter to each vertex of a graph, then writing a sequence where every letter appears exactly k times. The goal is that two letters alternate in the sequence (meaning they interleave rather than appear in separate blocks) if and only if the corresponding vertices are connected by an edge. The representation number is the smallest k for which such a sequence exists. This concept connects graph theory to combinatorics on words and has been studied for various graph families.
Crown graphs are a specific family of bipartite graphs. A crown graph is built by taking two equal sets of vertices and connecting every vertex in one set to every vertex in the other set except for one "partner," forming a kind of symmetric, nearly complete bipartite structure. These graphs were already known to have relatively large representation numbers, and researchers conjectured that among all bipartite graphs with the same number of vertices, crown graphs require the largest k. The paper proves this conjecture: any bipartite graph on N vertices (with N at least 9) has representation number no greater than the ceiling of N divided by 4, which matches the known value for crown graphs.
The proof strategy reduces the problem of finding a valid word to a question about ordering neighborhoods of vertices in a useful way, building on earlier work by other researchers. The authors identify precisely what structures obstruct such an ordering and use probabilistic arguments to rule them out for large enough graphs. Smaller cases that cannot be handled probabilistically are resolved using computer-checked proofs of unsatisfiability, essentially verifying that no counterexamples exist by exhaustive logical reasoning. Notably, the entire result including these computational components has been formally verified in Lean 4, a modern proof assistant, giving an unusually high level of certainty in the correctness of the argument.