Yeo’s Theorem for Locally Colored Graphs: the Path to Sequentialization in Linear Logic
Rémi Di Guardia ORCID:0009-0004-8632-108X, Olivier Laurent ORCID:0009-0007-1306-8994, Lorenzo Tortora de Falco ORCID:0000-0002-3987-1095, Lionel Vaux Auclair ORCID:0000-0001-9466-418X · 2026
Read Yeo’s Theorem for Locally Colored Graphs: the Path to Sequentialization in Linear Logic by Rémi Di Guardia ORCID:0009-0004-8632-108X, Olivier Laurent ORCID:0009-0007-1306-8994, Lorenzo Tortora de Falco ORCID:0000-0002-3987-1095, Lionel Vaux Auclair ORCID:0000-0001-9466-418X (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03262.txt.
Introduction
Rémi Di Guardia and three colleagues revisit a classic problem in linear logic: turning a proof net back into a step-by-step derivation. Proof nets are graph-like proofs, and a correctness test decides which graphs count as valid. Sequentialization then recovers the ordered proof. Their 2026 paper finds the right level of abstraction in a theorem from graph theory, Yeo's theorem, restated with colorings of half-edges.
A key lemma, cusp minimization, shows how to shrink certain color patterns around cycles until a splitting vertex appears, one that unlocks the inductive recovery. Different color choices then yield different recovery styles in a modular way, with no change to the graph itself. The method also covers proof nets with mix rules and the unit-free multiplicative-additive fragment, and it subsumes several older graph results.
Catalog record
| CREATOR | Rémi Di Guardia ORCID:0009-0004-8632-108X, Olivier Laurent ORCID:0009-0007-1306-8994, Lorenzo Tortora de Falco ORCID:0000-0002-3987-1095, Lionel Vaux Auclair ORCID:0000-0001-9466-418X |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 140498 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.03262
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Yeo’s Theorem for Locally Colored Graphs: the Path to Sequentialization in Linear Logic Rémi Di Guardia ORCID:0009-0004-8632-108X, Olivier Laurent ORCID:0009-0007-1306-8994, Lorenzo Tortora de Falco ORCID:0000-0002-3987-1095, Lionel Vaux Auclair ORCID:0000-0001-9466-418X Abstract . We revisit sequentialization proofs associated with the Danos-Regnier correctness criterion in the theory of proof nets of linear logic. Our approach relies on a generalization of Yeo’s theorem for graphs, based on colorings of half-edges. This happens to be the appropriate level of abstraction to extract sequentiality information from a proof net without modifying its graph structure. We thus obtain different ways of recovering a sequent calculus derivation from a proof net inductively, by relying on a splitting vertex, which we can impose to be a � \invamp -vertex, or a terminal vertex, or a non-axiom vertex, etc., in a modular way. This approach applies in presence of the mix -rules as well as for proof nets of unit-free multiplicative-additive linear logic (through an appropriate further generalization of Yeo’s theorem). The proof of our Yeo-style theorem relies on a key lemma that we call cusp minimization . Given a coloring of half-edges, a cusp in a path is a vertex whose adjacent half-edges in the path have the same color. And, given a cycle with at least one cusp and subject to suitable hypotheses, cusp minimization constructs a cycle with strictly less cusps. In the absence of cusp-free cycles, cusp minimization is then enough to ensure the existence of a splitting vertex, i.e. a vertex that is a cusp of any cycle it belongs to. Our theorem subsumes several graph-theoretical results, including some known to be equivalent to Yeo’s theorem. The novelty is that they can be derived in a straightforward way, just by defining a dedicated coloring, again without any modification of the underlying graph structure (vertices and edges) – similar results from the literature required more involved encodings. \titlecomment \lsuper * The present paper is a revised and extended version of [ DiGuardiaLaurentdeFalcoVauxAuclair25 ] , expanding the result to the additive proof nets and with a different organization. [a] [b] [c] [d] 1. Introduction Proof nets are a major contribution from linear logic [ ll ] . Contrary to the usual representation of proofs as derivation trees in sequent calculus, proof nets represent proofs as general graphs respecting some correctness criterion [ structmult ] , which imposes the absence of a particular kind of cycle. Proof nets identify the derivations of sequent calculus up to rule permutations [ mallpncom ] and, as a consequence of this canonicity, results like cut elimination become easier to prove in this formalism. A key theorem in this approach is the fact that each proof net is indeed the graph representation of a derivation in the sequent calculus: the process of recovering such a derivation tree is called sequentialization . Many proofs of this result can be found in the literature [ ll , structmult , quantif2 , pn , curienludics2 , etc.] , but proving sequentialization is still considered as not easy. Not only many proofs but more generally many equivalent correctness criteria have been introduced in the last 40 years, based on the existence or absence of particular paths in an associated graph (long trips, switching cycles, alternating-elementary-cycles) [ ll , structmult , rbpn ] , on the success of a rewriting procedure (contractibility, parsing) [ phddanos , pnin , cclin , NauroisMogbil11 ] , on homological [ homolpn ] or topological [ Mellies2004 ] properties, etc. They all describe the same set of valid graphs (those which are the image of a sequent calculus derivation) but through very different statements of properties characterizing the appropriate structure. The diversity of these approaches reflects both the central nature of the concept of proof net in linear logic, and the variety of motivations in the design of correctness criteria: some ensure tight complexity bounds (especially those based on contractibility), some weave connexions with other fields ( e.g. , topology or graph theory), some are more naturally generalized to other logical systems, etc. On the other hand, when it comes to the study of the theory of proof nets (confluence, normalization, reduction strategies, etc.) most of those approaches are hardly usable in practice. This gives the Danos-Regnier criterion [ structmult ] a special status: the absence of switching cycles is of direct use for proving results about proof nets. For instance, it forbids the occurrence of axiom-cut cycles along cut elimination [ synsem ] ; it ensures the confluence of reduction in multiplicative-exponential linear logic [ snll ] ; it provides the existence of so-called closed cuts [ Laurent20 ] , which play a crucial rôle in geometry of interaction [ goi1 ] ; it allows for the definition of a parallel procedure of cut elimination for multiplicative [ DBLP:journals/lmcs/ChouquetA21 ] or even multiplicative-exponential linear logic [ DBLP:conf/lpar/GuerrieriMFA24 ] ; etc. This means in particular that, based on this criterion, it becomes possible to develop the theory of proof nets without referring to the sequent calculus anymore. For this reason, we are interested in a better understanding of this precise criterion and its links with the sequential structure of tree derivations, via sequentialization. Following previous lines of work on relating graph theory and proof net theory [ rbpn , pnehrhard , pngraph ] , we looked for a direct link between graph properties and the sequential structure of proof nets: splitting vertices . Indeed, the key step for extracting a sequent calculus derivation from a proof net is to inductively decompose it into sub-graphs themselves satisfying the correctness condition. In graph theory, it is common to have several (equivalent) characterizations for a same class of graphs, and an inductive characterization may allow for simpler proofs – see e.g. , cographs [ CORNEIL1981163 ] , k -trees [ Beineke_Pippert_1971 ] or graphs with a unique perfect matching [ Kotzig1959 ] . Such an inductive characterization may be deduced from the existence of a vertex or of an edge separating the graph in a “nice” manner ( e.g. a bridge [ bangdigraphs ] ). Five theorems yielding such a vertex or edge have been shown equivalent by Szeider [ Szeider04c ] , meaning they can be deduced from each other using an encoding of the graph under consideration. Among those five are Yeo’s theorem on colored graphs [ yeotheorem ] , Kotzig’s theorem on unique perfect matchings [ Kotzig1959 ] , but also Shoesmith and Smiley’s theorem on turning vertices [ thseqsemicycle ] – interestingly the approach of the latter bears striking resemblance with our own work, that we discuss more in detail in the paper (see Section 4.2 ). On the proof net side, Rétoré remarked that perfect matchings provide an alternative presentation of proof nets [ rbpn ] : in this context, he recovered sequentialization proofs based on different notions of splitting vertex, in the spirit of Kotzig’s theorem [ Kotzig1959 ] . Remarkably, Nguyễn later established that Kotzig’s theorem is in fact equivalent to the sequentialization theorem of unit-free multiplicative proof nets with mix [ pngraph ] , again through graph encodings. In the present paper, we focus on Yeo’s theorem [ yeotheorem ] instead, which is about edge-colored undirected graphs. Our