Research companion to the MSc thesis Tracing the Effects of Symmetry in Hypergraphs on the Fredman–Khachiyan Algorithm (Saimon Y. Islam, Simon Fraser University, 2024; supervisor Tamon Stephen).
- A set
T ⊆ Vis a transversal of a hypergraphHonVif it meets every hyperedge, and a minimal transversal if no proper subset is one. - The minimal transversals form the transversal hypergraph
Tr(H), which is Sperner. - TransHyp: given two Sperner hypergraphs
H₁andH₂, decide whetherH₂ = Tr(H₁). No polynomial algorithm is known. - Fredman and Khachiyan (1996) gave two quasi-polynomial algorithms, FK-A (
n^{O(log² n)}) and FK-B (n^{o(log n)}), wherenis the total number of hyperedges. - FK-A recurses on a split vertex of high frequency. The alternating trees (the GK- and TK-families, which Hertel unified) give superpolynomial recursion trees. The Fano plane is a small symmetric instance used to study the same decomposition.
- The thesis studies how the symmetry of a hypergraph, through its automorphism group
Aut(H)and its underlying graph, interacts with that recursion.
- Engine (
src/fka,src/fkb, Python): FK-A (the faithful version and the thesis's modified variant), FK-B, Berge's sequential method as an independent check, automorphism groups and memoisation. It runs the algorithms, draws their recursion trees and searches for candidates. A number it produces is a lead until it is formalised. - Vocabulary: the code uses the monotone Boolean register of the FK-B reference (
cnfforH,dnfforTr(H));docs/dictionary.mdgives the correspondence with the thesis's hypergraph terms. - Formalisation (
lean/, Lean 4 against Mathlib): the thesis statements, their corrections and the new results. The thesis source was recovered from the deposited PDF in October 2026. - Claim register:
thesis/CLAIMS.mdrecords the audited thesis statements and later results with their status and Lean declaration or written source. Its key distinguishes proofs, finite checks, computations, cited or conditional results, and open or withdrawn claims. - Axiom check: general theorems use only the axioms
propext,Classical.choiceandQuot.sound, and checked facts are evaluations;lean/HypergraphDualization/Axioms.leanmakes the build fail otherwise. - Thesis: one corrected source in
thesis/, with its compiled PDF and Lean declaration references. - Experiments (
experiments/): searches and generators, each seeded (index). - Validation (
tests/): the engine is checked against the printed recursion trees and the MATLAB FK-B reference. FK-B is an independent implementation from the published algorithm; the MATLAB reference stays local (FK- B/), since its redistribution terms are not established.
lean/: the Lean library (module index).thesis/: the corrected source, compiled PDF andCLAIMS.md.data/instances/: the thesis hypergraphs and the later instances (w11isS(4,5,11)), as JSON with provenance.docs/: the research record (research-2026-10.md), notes on the later results, computational notes from the Python engine, and the code vocabulary (dictionary.md)._archive/: original source log and withdrawn thesis instances required to reproduce the corrections.
python -m pip install -e ".[dev]" && python -m pytest -m "not slow"
python -m fka run fano # FK-A on the Fano plane, with its recursion tree
python -m fkb compare --all # FK-A against FK-B on the instance library
Build instructions are in lean/README.md and
thesis/README.md. SageMath is an optional backend for group computations
(docs/architecture.md#sagemath).
New results from October–November 2026, apart from corrections to the thesis, with their status as
defined under Methods. Theorem numbers are those of research-2026-10.md.
- Self-transversal designs. Every Steiner system
S(t, t+1, 2t+3)hasteven and satisfiesTr(H) = H; the Fano plane and the Witt designS(4,5,11)are the casest = 2, 4(Theorem 2.11, Lean). - Least frequency. Every non-trivial transversal pair on
npoints hasn·ε² ≥ 1(Theorem 3.1, Lean);sdisjoints-sets attainε = 1/satn = s², soε(n) = Θ(n^{−1/2})(written).ε(7) = 3/7, attained by the Fano plane (Corollary 3.2, Lean). - The frequency-lemma constant. Every dual pair has
|C||D| ≥ 4^{1/ε − 1}, and every read-once pair|C||D| ≥ e^{2(1/ε − 1)}; the alternating words attain8^{1/ε − 1}(written proofs,frequency-constant.md). - FK-A's subproblems. The memo DAG of unmodified FK-A is a free binary decision diagram (FBDD) of
size at most
2δ + 2(Theorem 4.13, Lean), so a monotone family with polynomially many edges and superpolynomial FBDD size would defeat every valid symmetric rule. A memo keyed by isomorphism class is sound (Theorem 4.28, Lean). - FK-A's recursion tree. It unfolds into a decision tree (Theorem 4.25, Lean). So on the GK and
TK families on
nvertices every valid rule hasτ ≥ 2·(27/16)^{n/4}/(n + 1)(Lean), which isN^{Ω(log N)}(written), while under the leftmost rule memoisation saves a factor exponential inn(Corollary 4.26, Lean); under the degree-sum rule of the implementation whetherδ/Nis bounded is open (Conjecture 4.19). - The exponent of that tree. On GK and TK the least
τover valid rules is bounded below by2^{0.41433 n}/(n + 1)and above by2^{(0.469254 + o(1)) n}(written lower bound; upper bound argued and computed). Depth-first trees are optimal for every leaf weighting on GKf₁–f₃(computed). The remaining gap reduces to one inequality per gate, Conjecture 17 (complex-evaluation.md). - Substitution.
Tr(T[Γ]) = min(Tr(T)[Tr Γ]), without theminon disjoint supports (Theorem 5.1, Lean).
Results are in docs/research-2026-10.md (proofs and Lean names),
thesis/CLAIMS.md (status of every statement and the thesis corrections),
results/ (computed tables; per-run JSON, HTML and DOT generated on demand) and
docs/research-2026-10.md#7-open-items (open problems).
Saimon Y. Islam; the original implementation was written with Lacey Liang. GPL-3.0-or-later. The
corrected thesis uses SFU's sfuthesis class (LPPL 1.3). Cite the thesis
(CITATION.cff).