Evolving Local Corrections for Global Constructions in Combinatorics

This paper employs the AlphaEvolve computational engine to explore three combinatorial problems—graph reconstruction, the Alon-Tarsi parity problem, and Rota's Basis Conjecture—by iteratively refining local correcting steps to generate explicit algorithms and structural patterns that serve as foundations for future traditional mathematical proofs.

The Gist

Here is an explanation of the paper "Evolving Local Corrections for Global Constructions in Combinatorics" using simple language and creative analogies.

The Big Idea: Fixing a Puzzle Piece by Piece

Imagine you have a massive, impossible-to-solve jigsaw puzzle. You can't see the whole picture at once, and trying to force the pieces together randomly takes forever.

This paper is about a new way to solve these "impossible" math puzzles. Instead of trying to build the whole solution at once, the researchers used a smart computer program called AlphaEvolve to learn how to make tiny, local fixes.

Think of it like this: If your house is on fire, you don't try to rebuild the whole neighborhood instantly. You put out one small fire, then move to the next. The paper argues that for many hard math problems, if you can find the right "small fix" to apply over and over, you can eventually solve the whole global problem.

The Three Big Puzzles

The researchers tested this idea on three famous, unsolved math mysteries. Here is how they approached them:

1. The "Ghost Photo" Problem (Graph Reconstruction)

The Problem: Imagine you have a photo of a city (a graph), but someone cuts it into pieces by removing one building at a time. You are left with a pile of photos, each missing one building. Can you figure out what the original city looked like just by looking at these damaged photos?
The Analogy: It's like trying to guess the shape of a cookie by looking at the crumbs left on the plate after someone took a bite out of it.
The Solution: The computer learned to look at the "crumbs" (the missing pieces) to figure out the shape of the neighbors. It realized that if it knew how many connections a building had, and how its neighbors were connected, it could rebuild the whole city. It found a recipe to reconstruct the map perfectly for many types of cities.

2. The "Odd/Even" Parity Game (Latin Squares)

The Problem: A Latin Square is like a Sudoku grid where every row and column has unique numbers. Mathematicians want to know if there are more "Even" versions of these grids or "Odd" versions. For even-sized grids, this has been a mystery for decades.
The Analogy: Imagine a dance floor with couples. You want to know if there are more couples dancing clockwise or counter-clockwise. The trick is to find a way to pair up dancers so that every clockwise dancer is matched with a counter-clockwise dancer. If you can pair them all up perfectly, the numbers cancel out. If one dancer is left over, that's the answer.
The Solution: The computer invented a "dance move" (a local swap of numbers) that flips a grid from Even to Odd. It found a rule that pairs up almost every grid with its opposite. The few grids that couldn't be paired up all happened to be the same type (all Even or all Odd), which solved the mystery for those specific cases.

3. The "Rainbow Tower" Problem (Rota's Basis Conjecture)

The Problem: Imagine you have $N$ different sets of building blocks (bases). You want to rearrange them into a grid where every column is also a perfect set of blocks. It's like trying to sort a deck of cards into $N$ piles where every pile has one card of every suit, but the cards are all mixed up.
The Analogy: You have $N$ teams, each with $N$ players. You want to form $N$ new teams where every new team has exactly one player from each original team, and every new team is still a winning team.
The Solution: The computer acted like a greedy game player. It looked at the grid, found a "broken" column, and swapped a few blocks to fix it. It learned a strategy of "sacrificing" a good column temporarily to fix a bigger trap, eventually building a perfect grid.

How the Computer Learned (The "Evolution" Part)

The researchers didn't write the solution code themselves. Instead, they used AlphaEvolve, which is like a digital Darwinian evolution.

1. The Playground: They set up a test environment (a "harness") with a scoring system. If the computer's code made the puzzle slightly better, it got points.
2. Mutation: The computer wrote thousands of tiny variations of its own code. Some were silly, some were smart.
3. Survival of the Fittest: The versions that got the highest scores survived. The computer took the best parts of those winners and mixed them to make the next generation.
4. The Result: After running for hours or days, the computer "evolved" a set of rules (algorithms) that solved the puzzles better than any human had before.

The Takeaway: A Map for Human Mathematicians

The most important part of this paper isn't that the computer "proved" the theorems. It's that the computer drew a map.

• Before: Mathematicians were lost in a dark forest, guessing which path to take.
• After: The computer walked the path, found the dead ends, and showed the humans: "Hey, if you go this way, and make these specific small turns, you get closer to the exit."

The paper provides conjectures (educated guesses) based on these computer experiments. It tells human mathematicians: "Here is a specific pattern of small moves that seems to work. If you can prove why this pattern always works, you will solve the big problem."

In short: The computer didn't do the math homework for us; it found the right pencil and showed us exactly where to start writing.

Technical Summary

Here is a detailed technical summary of the paper "Evolving Local Corrections for Global Constructions in Combinatorics" by Gergely Bérczi.

1. Problem Statement

The paper addresses three major open problems in combinatorics where the existence of a global structure is conjectured, but explicit construction or proof remains elusive. These problems share a common structural feature: they can be modeled as finding a "global minimum" (a valid certificate) in a vast discrete space by applying a sequence of small, local correcting steps.

The three specific problems studied are:

1. Graph Reconstruction Conjecture: Can a finite simple graph be uniquely reconstructed (up to isomorphism) from its "deck" (the multiset of vertex-deleted subgraphs)? The paper focuses on bipartite graphs and planar graphs (specifically non-maximal, biconnected graphs with minimum degree $\ge 3$).
2. Alon-Tarsi Conjecture: For even $n$, the signed enumeration of Latin squares is non-zero ($E_n - O_n \neq 0$). The goal is to construct a sign-reversing involution that pairs most Latin squares, leaving a small residual set with a dominant sign.
3. Rota's Basis Conjecture: Given $n$ disjoint bases of a rank-$n$ matroid, can they be rearranged into an $n \times n$ grid where every column is also a basis? The paper focuses on linear matroids over $\mathbb{F}_2$ and seeks a policy to perform local exchanges to repair invalid columns.

2. Methodology: AlphaEvolve

The author utilizes AlphaEvolve, an experimental engine that treats the search for mathematical proofs as an evolutionary optimization problem. Instead of searching for a single static object (like a specific graph or Latin square), the system searches for algorithms (Python scripts) that generate these objects or perform the necessary corrections.

• The Evolvable Block: A Python function (e.g., find_best_certificate) that proposes a candidate solution or a local move.
• The Harness (Evaluator): A fixed module that encodes the mathematical rules. It takes the candidate, runs it on a test set, and returns a scalar score.
  • Scoring Strategy: The harness uses a tiered scoring system. Hard constraints (e.g., "must be a valid Latin square") are non-negotiable. Soft metrics (e.g., "sign-flip rate," "number of valid columns," "locality of moves") guide the search toward "proof-shaped" solutions.
  • Symmetry Handling: To prevent overfitting to arbitrary labels, the harness evaluates candidates under random symmetry operations (permutations of vertices, rows, columns, or symbols) and aggregates scores using worst-case statistics.
• Evolutionary Process: The system iteratively rewrites the evolvable code block. It favors modifications that improve the score, effectively "evolving" a heuristic or algorithm that performs local repairs to reach a global solution.

3. Key Contributions and Results

A. Graph Reconstruction

• Bipartite Graphs:
  • Result: AlphaEvolve discovered an algorithm achieving 100% reconstruction on a benchmark of 1,420 bipartite graphs.
  • Mechanism: The evolved algorithm reconstructs global degrees and "neighbor-degree profiles" (the multiset of degrees of a vertex's neighbors). It groups vertices into "types" based on these invariants and solves a constrained assignment problem using min-cost flow. It further refines this using "two-deletion compatibility signatures" (comparing subgraphs with two vertices removed) to resolve ambiguities.
  • Conjecture: In high-degree, 2-connected, non-regular bipartite graphs, low-order invariants (degrees and neighbor profiles) uniquely determine the graph, with remaining ambiguity resolved by two-deletion consistency.
• Planar Graphs:
  • Result: The system found a simple, exact-verification algorithm achieving 100% reconstruction on hardened planar benchmarks.
  • Mechanism: Leveraging Euler's bound (planar graphs have a vertex of degree $\le 5$), the algorithm enumerates candidate neighborhoods for a minimum-degree vertex, filters them using triangle counts, and verifies the candidate via exact deck equality.
  • Conjecture: Biconnected planar graphs with $\delta \ge 3$ are reconstructible via a bounded-degree search strategy running in polynomial time.

B. Alon-Tarsi Conjecture

• Result: The system evolved deterministic maps that act as sign-reversing involutions on 98–100% of Latin squares for even orders ($n=8, 10, 12, 14, 26$).
• Mechanism: The evolved algorithms utilize odd-cycle trades. By identifying odd-length cycles in the permutation induced by two rows (or columns/symbols) and swapping elements along these cycles, the algorithm flips the sign of the Latin square while preserving its validity.
  • Residual Bias: The few unpaired squares (the residual set) were found to be overwhelmingly of a single sign (e.g., all even or all odd), maximizing the signed sum.
  • Stability: The evolved maps include "stability checks" to ensure the map is a true involution ($F(F(L)) = L$) and are robust under isotopy (permutations of rows, columns, and symbols).
• Conjecture: For every even $n$, there exists a deterministic scan order of two-line cycle trades such that the induced map is a sign-reversing involution on all but a small residual set with a non-zero signed sum.

C. Rota's Basis Conjecture

• Result: The system evolved greedy local-exchange policies that successfully constructed $n$ disjoint transversal bases for 100% of test instances in ranks 5, 7, and a variable-rank benchmark (5–13) over $\mathbb{F}_2$.
• Mechanism: The policies use a scoring function that balances:
  • Progress: Rewarding moves that complete full columns.
  • Trap Avoidance: Penalizing moves that create small dependency circuits (traps).
  • Strategic Sacrifice: Allowing the algorithm to break a "full" column if it resolves a critical dependency circuit (a "heroic sacrifice").
  • Scale Awareness: The variable-rank policy uses dynamic "pressure" and "trap energy" metrics that scale with the rank $n$, allowing the algorithm to adapt its aggressiveness based on the problem size.
• Conjecture: For circuit-rich pools of vectors in $\mathbb{F}_2^n$, a deterministic de-randomization of the evolved scale-aware policy can successfully construct the required transversal bases.

4. Significance and Implications

• Shift in Mathematical Practice: The paper demonstrates that AI-driven evolutionary search can act as a powerful "hypothesis generator" for constructive combinatorics. It does not replace human proof but produces explicit algorithms and structural patterns that are amenable to traditional mathematical analysis.
• Local-to-Global Principle: The work validates the heuristic that difficult global existence problems often admit solutions via "discrete Lyapunov trajectories"—sequences of local moves that monotonically decrease a defect measure.
• New Conjectures: The paper formulates specific, testable conjectures (Conjectures 4–11) derived directly from the evolved algorithms. These conjectures are more precise than the original open problems, offering concrete pathways (e.g., specific types of trades or flow constraints) for future proofs.
• AI as a Collaborator: The use of AI-generated summaries (via Gemini) to interpret the "evolutionary trace" of the search highlights a new workflow where AI helps mathematicians understand why a search succeeded or failed, identifying key turning points and structural insights.

In summary, this paper presents a successful framework for using evolutionary computation to tackle deep combinatorial problems, yielding concrete algorithms and refined conjectures for the Graph Reconstruction, Alon-Tarsi, and Rota's Basis problems.