💻 computer science

Yeo's Theorem for Locally Colored Graphs: the Path to Sequentialization in Linear Logic

This paper presents a modular approach to sequentialization in linear logic by generalizing Yeo's theorem for locally colored graphs, utilizing a "cusp minimization" lemma to extract splitting vertices and recover sequent calculus derivations from proof nets without altering their underlying graph structure.

Original authors: Rémi Di Guardia, Olivier Laurent, Lorenzo Tortora de Falco, Lionel Vaux Auclair

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rémi Di Guardia, Olivier Laurent, Lorenzo Tortora de Falco, Lionel Vaux Auclair

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, complex jigsaw puzzle. But here's the twist: the pieces aren't just shapes; they are logical arguments, and the picture they form is a mathematical proof. In the world of Linear Logic, these puzzles are called Proof Nets.

For decades, mathematicians have known how to build these puzzles from a set of instructions (called a "sequent calculus derivation"). But the hard part has always been the reverse: looking at a finished, messy puzzle and figuring out exactly what instructions were used to build it. This process is called Sequentialization.

This paper is like a new, super-smart guide that tells you exactly how to take apart any valid proof net, piece by piece, until you get back to the original instructions. And the secret weapon they use? A clever trick involving colors and a theorem named after a mathematician called Yeo.

Here is the breakdown of their discovery, using simple analogies:

1. The Problem: The Tangled Knot

Imagine a proof net as a web of strings connecting different points. Some strings are "solid," some are "dashed," and some are "dotted."

The Rule: In a valid proof net, you shouldn't be able to trace a loop (a cycle) that follows a specific pattern, like "solid-dashed-solid-dashed." If you can find such a loop, the proof is broken (it's a logical fallacy).
The Goal: We want to find a "cut point." If you cut this specific point, the whole web falls apart into smaller, manageable pieces, and none of those pieces are connected to the cut point by more than one color of string.

2. The Secret Sauce: "Local Coloring"

Usually, mathematicians color an entire string one color. But the authors realized that in these logical webs, the "color" of a string might look different depending on which end of the string you are looking at.

The Analogy: Imagine a rope. From the left side, it looks red. From the right side, it looks blue.
The "Cusp": If you walk along a path and you hit a knot where the rope looks the same color coming in and going out (e.g., red-in, red-out), that's a cusp. It's a "traffic jam" in the logic.
The Goal: The authors want to find a point where you never get stuck in a traffic jam. They call this a Splitting Vertex. If you find one, you can safely cut the web there.

3. The Magic Trick: "Cusp Minimization"

How do they find this magical cutting point? They use a strategy they call Cusp Minimization.

The Metaphor: Imagine you are walking through a maze full of dead ends (cusps). You want to find a path with no dead ends.
The Trick: If you get stuck in a loop with dead ends, the authors show you a way to "shrink" the loop. You take a shortcut that bypasses the dead ends, creating a smaller loop with fewer dead ends.
The Result: If you keep shrinking these loops, eventually you either find a loop with zero dead ends (which proves the proof is broken) or you run out of loops entirely. If you run out of loops, you know you must have found a "Splitting Vertex"—a safe place to cut.

4. Why This is a Big Deal

Before this paper, proving that you could break down a proof net required very complicated, heavy machinery. You often had to redraw the graph or change its structure to make the math work.

The Innovation: This new method is modular and non-invasive. It's like having a pair of scissors that can cut the web in different ways depending on what you need, without ever having to glue the web back together or redraw it.
- Need to cut at a specific type of logical junction? Just change the "coloring rules" slightly.
- Need to cut at the very end of the proof? Change the rules again.
- Need to handle complex "Additive" logic (where choices are made)? They generalized the theorem to handle those too.

5. The "Yeo" Connection

The paper is named after Yeo's Theorem, a known result in graph theory (the math of networks). The authors didn't just use Yeo's theorem; they upgraded it.

Original Yeo: "If you have a network with no bad loops, there is a safe cutting point."
New "Yeo-style" Theorem: "If you have a network with local colors (where the color depends on the direction), and no bad loops, there is a safe cutting point that we can choose specifically."

Summary: What Did They Actually Do?

They took a very difficult problem in computer science and logic (how to reverse-engineer a proof) and solved it using a fresh perspective on graph theory.

They invented a way to look at logical proofs as colored maps.
They proved that if the map is valid, there is always a "safe exit" (a splitting vertex).
They showed that you can find this exit by looking for the "least tangled" path (cusp minimization).
They demonstrated that this single, elegant idea works for simple proofs, complex proofs with choices, and even proofs with "mixing" rules.

In a nutshell: They found a universal "key" that can unlock any valid logical proof, turning a tangled mess of logic back into a clear, step-by-step instruction manual, all by looking at the colors of the connections.

1. Problem Statement

The paper addresses the sequentialization problem in the theory of proof nets for Linear Logic.

Context: Proof nets are graph-based representations of proofs in Linear Logic that abstract away from the syntactic bureaucracy of sequent calculus (e.g., rule permutations). A central theorem in this field is that every valid proof net (satisfying a correctness criterion) corresponds to a valid sequent calculus derivation. The process of reconstructing this derivation from the graph is called sequentialization.
The Challenge: Proving sequentialization is notoriously difficult. Existing proofs often rely on complex encodings, specific graph transformations, or intricate topological arguments. Furthermore, extending these proofs to richer logics (such as those with additive connectives or mix rules) often requires ad-hoc modifications.
The Goal: The authors aim to provide a unified, modular, and elementary proof of sequentialization for both Multiplicative Linear Logic (MLL) and Multiplicative-Additive Linear Logic (MALL). They seek to achieve this by establishing a direct link between the graph-theoretic properties of proof nets and the existence of splitting vertices (vertices whose removal decomposes the graph into smaller valid components) without modifying the underlying graph structure.

2. Methodology

The authors' approach relies on a novel generalization of Yeo's Theorem (a result concerning edge-colored graphs) applied to locally colored graphs.

A. Local Coloring and Cusps

Instead of standard edge coloring (where an edge has one color), the authors introduce local coloring:

Definition: A function assigns a color to each half-edge (an edge endpoint). Thus, an edge $e$ connecting vertices $u$ and $v$ can have color $c(e, u)$ at $u$ and $c(e, v)$ at $v$ .
Cusps: A cusp at a vertex $v$ occurs when two incident edges in a path share the same color at $v$ . A path is cusp-free (or alternating) if it contains no cusps.
Splitting Vertex: A vertex $v$ is splitting if every cycle containing it has a cusp at $v$ .

B. Cusp Minimization (The Core Lemma)

The proof hinges on a key lemma called Cusp Minimization:

Given a cycle with at least one cusp, the lemma constructs either a cusp-free cycle or a new cycle with strictly fewer cusps.
This process relies on an ordering ( $\prec$ ) defined on vertex-color pairs. If a graph has no cusp-free cycles, this ordering ensures the existence of a maximal vertex-color pair, the vertex of which must be a splitting vertex.

C. Generalization to MALL

For MALL (which includes additive connectives $\&$ and $\oplus$ ), standard cusp-free cycles (switching cycles) may exist. The authors generalize Yeo's theorem to handle maximal connected unions of cusp-free cycles. They introduce an exit function (a specific edge leaving a cycle union) to extend the cusp minimization argument to this more complex setting.

3. Key Contributions

1. A New Graph-Theoretic Theorem

The paper proves a Parametrized Local Yeo's Theorem (Theorem 3.6):

In a locally colored graph with no cusp-free cycles, for any set $P$ of vertex-color pairs that "dominates" the cusp-points, any $\prec$ -maximal element in $P$ corresponds to a splitting vertex.
Significance: This theorem subsumes several known results (Yeo's original theorem, Kotzig's theorem on perfect matchings, Shoesmith and Smiley's theorem on turning vertices) as simple corollaries obtained merely by choosing specific colorings, without altering the graph structure.

2. Modular Sequentialization for MLL

The authors apply their theorem to Multiplicative Linear Logic (MLL) proof nets:

They define a well-colored proof structure where the local coloring mimics the logical rules (e.g., premises of a $\otimes$ vertex have distinct colors, premises of a $\parr$ vertex share a color).
In this setting, cusp-free paths correspond exactly to switching paths (the Danos-Regnier correctness criterion).
Result: The existence of a splitting vertex is guaranteed by the graph theorem. By varying the parameter set $P$ $P$ , they can force the splitting vertex to be:
- An arbitrary splitting vertex.
- A splitting $\parr$ -vertex (a "section").
- A terminal splitting vertex.
- A non-axiom vertex.
This provides a uniform proof of sequentialization that works even with mix rules (which allow disconnected components).

3. Sequentialization for MALL (Additives)

The paper extends the method to Multiplicative-Additive Linear Logic (MALL):

Challenge: MALL proof nets (à la Hughes and van Glabbeek) contain switching cycles, so the basic "no cusp-free cycle" hypothesis fails.
Solution: The authors use the generalized Theorem 8.2, which handles maximal unions of cusp-free cycles by utilizing "exit edges" (jump edges in the proof net context).
Result: They prove the existence of splitting vertices (including terminal ones) in MALL proof nets, leading to a sequentialization theorem that recovers the Hughes-van Glabbeek results but with a more direct, graph-theoretic proof.

4. Key Results

Theorem 3.6 (Parametrized Local Yeo): Establishes the existence of splitting vertices in locally colored graphs based on a partial order of vertex-color pairs.
Theorem 6.1 & 10.1 (Sequentialization): Proves that for any DR-correct proof net (MLL or MALL), there exists a sequent calculus derivation.
Corollaries: The framework allows for the derivation of specific sequentialization strategies (e.g., finding a splitting terminal vertex) simply by adjusting the parameter set $P$ , rather than changing the proof technique.
Equivalence: The paper demonstrates that their generalized theorem is equivalent to several other graph-theoretic results (Kotzig, Shoesmith/Smiley, etc.), unifying them under a single "cusp minimization" proof.

5. Significance

Simplicity and Unification: The paper replaces complex, case-specific proofs with a single, elementary graph-theoretic argument (cusp minimization). It shows that the sequentialization of proof nets is a direct consequence of a generalized Yeo's theorem.
Modularity: The approach is highly modular. By changing the definition of "cusp" or the set of allowed vertex-color pairs, the same proof skeleton adapts to different logical systems (MLL, MALL, systems with mix, etc.) and different splitting strategies (terminal vs. internal).
No Structural Modification: Unlike previous approaches that often required encoding proof nets into other graph types (e.g., perfect matchings) or modifying the graph structure, this method works directly on the proof net's graph with a local coloring.
Extension to Additives: It successfully bridges the gap between multiplicative and additive proof nets, providing a robust proof of sequentialization for MALL that handles the complexities of switching cycles and jump edges naturally.

In summary, the paper provides a powerful new lens for understanding proof nets: the sequentialization problem is fundamentally a problem of finding splitting vertices in locally colored graphs, solvable via a generalized version of Yeo's theorem and the technique of cusp minimization.