Discrete Flow Matching for Extremal Graph Search with Zero-Shot Size Transfer

Many existing neural systems for mathematical discovery of extremal combinatorial structures alternate between generation and local search, retraining a generative model on the best refined constructions. This model is typically parametrized as an autoregressive transformer over a serialization of the object, which is a questionable choice for graphs: vertex symmetry is not necessarily encoded, and edge decisions cannot be revised within the autoregressive sampling pass. This work instead draws on graph neural networks and discrete flow matching: a permutation-equivariant pair network predicts all edge decisions at once, and iterative denoising lets each be revisited as the rest of the graph changes. The same weights can generate graphs of different sizes. We show that this reuse works: generators trained on smaller graphs construct optimal $C_4$-free graphs at unseen sizes, before local search, and in up to 49% less training time than training at each target size. Reward fine-tuning further improves their value as search starts, with gains extending beyond the fine-tuning size. One selected adapted generator produces a 137-edge $C_4$-free graph on 42 vertices before local search, matching the best-known count without training at that size. To the best of our knowledge, this is the first time a learned approach attains this bound. Experiments on Ramsey construction demonstrate zero-shot size transfer under a second constraint family.