Hexagon

math.CO — Combinatorics

An intrinsic interval-deletion characterization of digraph support families

Contributed by Michael Mislan

For a finite directed graph with loops allowed, its supported subsets are those in which every vertex has an in-neighbour within the subset. We characterize exactly which set families arise this way on their original ground set. Starting from the power set, a legal step chooses an inclusion-maximal remaining nonmember, selects a previously unused root absent from every target-family member below it, and deletes the rooted interval. A family is a digraph support family if and only if some legal deletion sequence reaches it. The maximal residual set may follow any fixed valid policy; only roots require branching. Successful traces have at most one step per vertex and reconstruct a realizing digraph. Consequences include exact root sets and trace length, a finite recognizer, conventional NP membership for explicit lists, projection, deletion and product closure, and RAF realizability criteria using the published antimatroid characterization. The characterization and selected consequences and trace-checking interfaces are verified in Lean 4; conventional statements and computational examples are identified separately.

Primarily AI-generated textHuman understanding: some partsLean formalizationRAF realizabilitydigraph support familiesinterior operatorsrooted-interval deletionsingle-head Horn theories

Oct 20, 2026PDF ↗View work →

hexagon:2610.00374v1

math.CO — Combinatorics

Antimatroid characterization of RAF interior operators

Contributed by Michael Mislan

Addressing the RAF-realizability question in Section 4 of Mike Steel's Interior Operators and Their Relationship to Autocatalytic Networks (arXiv:2305.16714v4, 2023), we characterize which interior operators on the subsets of a finite set E are maxRAF operators of catalytic reaction systems whose reaction set is exactly E. An interior operator is represented by its family of fixed sets, a union-closed family containing the empty set. A same-ground realization is a system with one reaction per element of E, finitely many molecule types, a food set and a catalysis relation; it realizes the empty set together with its RAFs, the nonempty reaction sets whose reactants arise from food by iterated closure under the selected reactions and whose reactions are each catalysed by a molecule of that closure. Such a family has a same-ground realization if and only if it is the intersection of an accessible union-closed family A and a predecessor-support family. Here A contains the empty set, is closed under unions, and every nonempty member of A has an element whose removal leaves a member of A; the members of A need not cover E. A set S is supported by a predecessor map P on E when every element e of S has some element of S in P(e), loops allowed. The family consisting of the empty set and all subsets of size at least three has a same-ground realization if and only if E has at most four elements. This gives the sharp threshold for the family considered in Proposition 5 and its subsequent remarks in Steel (2023). Both results are formalized in Lean 4 with Mathlib.

Primarily AI-generated textHuman understanding: some partsLean formalizationRAF setsantimatroidsfood generationinterior operatorsrealizability

Oct 20, 2026PDF ↗View work →

Matching works

An intrinsic interval-deletion characterization of digraph support families

Antimatroid characterization of RAF interior operators

Advanced search

math.AC — Commutative Algebra
math.AG — Algebraic Geometry
math.AP — Analysis of PDEs
math.AT — Algebraic Topology
math.CA — Classical Analysis and ODEs
math.CO — Combinatorics
math.CT — Category Theory
math.CV — Complex Variables
math.DG — Differential Geometry
math.DS — Dynamical Systems
math.FA — Functional Analysis
math.GM — General Mathematics
math.GN — General Topology
math.GR — Group Theory
math.GT — Geometric Topology
math.HO — History and Overview
math.IT — Information Theory
math.KT — K-Theory and Homology
math.LO — Logic
math.MG — Metric Geometry
math.NA — Numerical Analysis
math.NT — Number Theory
math.OA — Operator Algebras
math.OC — Optimization and Control
math.PR — Probability
math.QA — Quantum Algebra
math.RA — Rings and Algebras
math.RT — Representation Theory
math.SG — Symplectic Geometry
math.SP — Spectral Theory
math.ST — Statistics Theory
cs.AI — Artificial Intelligence
cs.CC — Computational Complexity
cs.CG — Computational Geometry
cs.DM — Discrete Mathematics
cs.DS — Data Structures and Algorithms
cs.FL — Formal Languages and Automata Theory
cs.IT — Information Theory
cs.LO — Logic in Computer Science
cs.MS — Mathematical Software
cs.NA — Numerical Analysis
cs.SC — Symbolic Computation
math-ph — Mathematical Physics
quant-ph — Quantum Physics
stat.TH — Statistics Theory