Browse

Discrete Mathematics

cs.DM — Discrete Mathematics

cs.DM RSS feed

Works in cs.DM

21 works

cs.DS — Data Structures and Algorithms

Sorting networks on 13 inputs need at least 44 comparators

Contributed by Tejasvi Singh Tomar

Let S(N)S(N) be the least number of comparators in a sorting network on NN inputs. We prove S(13)≥44S(13)\ge44, one more than the previously best proved lower bound. We also prove P(2,N)=⌈log⁡2F(N)⌉P(2,N)=\lceil \log_2 F(N)\rceil for 3≤N≤323\le N\le32, where P(2,N)P(2,N) is the least worst-case number of comparators met by the two largest inputs in a network that delivers them to fixed outputs and FF is an explicit function of Van Voorhis; the lower bound comes from a finite search based on the structure of the paths of these two values. Starting from Harder's S(11)=35S(11)=35 and S(12)=39S(12)=39, these values of P(2,N)P(2,N), the two-value bound S(N)≥S(N−2)+P(2,N)S(N)\ge S(N-2)+P(2,N) and the one-value bound S(N)≥S(N−1)+⌈log⁡2N⌉S(N)\ge S(N-1)+\lceil \log_2 N\rceil give the twenty lower bounds on S(N)S(N) for 13≤N≤3213\le N\le32 in Dobbelaere's table; these bounds rested on Van Voorhis's inequality P(2,N)≥⌈log⁡2F(N)⌉P(2,N)\ge\lceil \log_2 F(N)\rceil, whose published proof is invalid. The bound S(13)≥44S(13)\ge44 is also proved in Lean 4, with every step checked by Lean's kernel.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23730883

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202620 pages
PDFView work

math.CO — Combinatorics

A thrackle on n vertices has fewer than 4n/3 edges

Contributed by Tejasvi Singh Tomar

A thrackle is a drawing of a graph in the plane in which every two edges meet exactly once, either at a common endpoint or at a proper crossing. Conway conjectured that a thrackle with nn vertices has at most nn edges. We prove that a thrackle with n≥4n\ge4 vertices has at most 43(n−1)\frac43(n-1) edges, improving the bound 1813(n−1)\frac{18}{13}(n-1) obtained by Tóth and, independently, by Scoppetto. The proof combines Xu's discharging argument with two computer searches, by the method of Fulek and Pach, showing that two generalized dumbbells in the sense of Fulek and Pach are not thrackleable: DB(6,8,−1)\mathrm{DB}(6,8,-1) is a 66-cycle and an 88-cycle sharing one edge; DB(6,10,−3)\mathrm{DB}(6,10,-3) is a 66-cycle and a 1010-cycle sharing a path of three edges. A formal proof in Lean 4 derives the bound from five properties of thrackles and checks the computational facts it uses; Section 6 states what this proof trusts.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.24065370

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202612 pages
PDFView work

math.CO — Combinatorics

The Cereceda (2007) conjecture holds for bipartite 2-degenerate graphs

Contributed by Dave Goel

For a graph GG and a positive integer kk, the kk-recolouring graph Rk(G)\mathcal{R}_{k}(G) has the proper kk-colourings of GG as vertices, two of them adjacent when they differ at exactly one vertex. A graph is dd-degenerate if each of its non-empty subgraphs has a vertex of degree at most dd. The Cereceda (2007) conjecture states that, for fixed dd and k≥d+2k \ge d+2, the diameter of Rk(G)\mathcal{R}_{k}(G) is O(n2)O(n^2) for every dd-degenerate graph GG on nn vertices. For d=2d = 2, the conjecture was known to hold for k≥5k \ge 5 by a result of Cereceda; for k=4k = 4, the best bound known for all 22-degenerate graphs is O(n3)O(n^3), due to Bousquet and Heinrich. We prove that the diameter of R4(G)\mathcal{R}_{4}(G) is at most 2n(n+1)2n(n+1) for every bipartite 22-degenerate graph GG on nn vertices; hence the conjecture holds for these graphs. We also show that the order n2n^2 cannot be improved for this class, even for graphs of girth 66. For the upper bound, we fix an ordering of the vertices in which each vertex has at most two later neighbours. In nn stages, we transform any proper 44-colouring into the colouring in which every vertex has the least colour not used by its later neighbours, recolouring each vertex at most twice per stage. Both of our bounds have also been proved in the Lean proof assistant.

Author comments: An expanded version of this paper, with many other results, is posted on Zenodo: https://doi.org/10.5281/zenodo.23603237

A mix of human-written and AI-generated textHuman understanding: some partsCereceda conjecturebipartite graphsdegenerate graphsgraph recolouringreconfiguration
Nov 10, 202617 pages
PDFView work

math.CO — Combinatorics

Sharp thresholds for five-colour cube assemblies

Contributed by Jason Davies

We determine the least pool sizes guaranteeing a frame or a complete a×b×ca\times b\times c box from unit cubes whose faces use all five colours of a fixed palette, for every a,b,c≥2a,b,c\ge2. Proper rotations are allowed; the target has monochromatic exterior faces using all five colours. The frame threshold is max⁡{15,4(a+b+c)−16,2(a+b+c)+1}\max\{15,4(a+b+c)-16,2(a+b+c)+1\}, and the complete-box threshold is max⁡{abc,15,2(a+b+c)+1}\max\{abc,15,2(a+b+c)+1\}. The proof combines a certified fifteen-cube corner theorem with elementary Hall arguments and a uniform three-variety obstruction. It completes the five-colour frame column left open by Berkove, Eickemeyer and Schulman (2018). All threshold statements are formalised in Lean. A fixed-size flow formulation decides feasibility and constructs assemblies in time linear in the explicit source list. We also determine the corner thresholds when the number of source varieties is bounded, and classify all fourteen-cube obstructions into 56 classes under common colour relabelling and simultaneous reflection, described by three structural forms. The minimum size of a collection capable of reproducing every 2×2×22\times2\times2 target is also fifteen.

Primarily AI-generated textHuman understanding: some partsHall's theoremLean formalisationMacMahon puzzlescoloured cubescomputer-assisted proofextremal combinatoricsinterval certificates
Nov 10, 202634 pages
PDFView work

math.CO — Combinatorics

Vertex splitting, global rigidity and nondegenerate equilibrium stresses

Contributed by James Cruickshank

We prove Whiteley's conjecture that every nontrivial vertex split of a generically globally rigid graph preserves generic global rigidity in Rd\mathbb{R}^d, for all d≥1d\geq1. We give two proofs of the stronger assertion that the split graph is infinitesimally rigid at every generic coincident realisation of the two split vertices. Both proofs use maximum-rank equilibrium stress matrices and then apply the coincident-rigidity criterion of Cruickshank, Jackson and Tanigawa. The second construction also shows that every generically globally rigid graph admits a nondegenerate equilibrium stress of maximum rank at every generic realisation, establishing a conjecture of Jord\'an and Tanigawa.

Author comments: updated to match version at https://arxiv.org/abs/2611.10919

Primarily AI-generated textHuman understanding: all partsGraph rigidityequilibrium stressglobal rigidityvertex splitting
Nov 06, 202616 pages
PDFView work

math.CO — Combinatorics

Every C4C_4-free graph on 4949 vertices has a vertex of degree at most 66: an independent verification

Contributed by David Niedbala Giraudin

ABSTRACT We give an independent proof that every graph on 4949 vertices containing no cycle of length four has a vertex of degree at most 66; equivalently, R(C4,K1,42)≤49R(C_4,K_{1,42})\le 49, hence R(C4,K1,42)=49R(C_4,K_{1,42})=49. In the notation of Erd\H{o}s, the least integer f(n)f(n) such that every graph on nn vertices with minimum degree at least f(n)f(n) contains a C4C_4 satisfies f(49)=7f(49)=7, while f(48)=f(50)=8f(48)=f(50)=8, so ff is not non-decreasing. These values were first established by Walters, Claude Fable, GPT Sol, Astra and Claude Opus (12 October 2026), by a different case split whose computational part is checked by the formally verified checker cake_lpr and assembled in Lean; we were not aware of their work when this note was written. Our proof combines structural lemmas, valid for every odd kk, on C4C_4-free graphs with k2k^2 vertices and minimum degree at least kk, a symmetry reduction for k=7k=7, and an exhaustive SAT search carried out by two separately written programs. Erd\H{o}s's question whether f(n+1)≥f(n)f(n+1)\ge f(n) for all sufficiently large nn (Problem 85 of erdosproblems.com) remains open. COMMENTS 8 pages. Independent verification of f(49)=7 (Erdos Problem #85), first established by Walters, Claude Fable, GPT Sol, Astra and Claude Opus (Zenodo, doi:10.5281/zenodo.23325806, 12 October 2026). Ancillary folder anc/: pure-Python scripts, solver logs and SHA-256 hashes of all formulas. Technical assistance: Claude (Anthropic). COMMENTAIRE DE VERSION (cas B seulement) v2: credits the earlier proof of f(48)=8>f(49)=7 by R. Walters, Claude Fable, GPT Sol, Astra and Claude Opus (Zenodo, doi:10.5281/zenodo.23325806, 12 October 2026; v1.1 20 October 2026), of which the author was not aware when v1 was posted. Title, abstract, introduction (new paragraph "Related work") and Remark 3 updated; the 48-vertex graph is isomorphic to their witness. No mathematical change; ancillary files unchanged.

Primarily AI-generated textHuman understanding: no partsC4-free graphsErdos problemsRamsey numbersSAT solvingcomputer-assisted proofminimum degree
Nov 04, 20268 pages
PDFView work

math.CO — Combinatorics

Three-colour cuboids from four-colour cubes

Contributed by Jason Davies

We determine the least number of four-colour cubes that guarantees a cuboid with monochromatic faces using exactly three colours. Each source uses all four colours of a fixed palette; only proper rotations are allowed, and interior faces need not match. For integer side lengths 2≤a≤b≤c2\le a\le b\le c, the sharp threshold for the corner-and-edge frame is max⁡{16a−3,4(a+b+c)−16,⌊(24c−1)/5⌋}\max\{16a-3,4(a+b+c)-16,\lfloor(24c-1)/5\rfloor\}, and the complete-cuboid threshold is max⁡{abc,16a−3,⌊(24c−1)/5⌋}\max\{abc,16a-3,\lfloor(24c-1)/5\rfloor\}. The three frame bounds arise from colour-bucket capacity, the number of positions and balanced checkerboards. The upper bound combines corner containment, a weighted graph selecting edge directions, and Hall's theorem. For cubic frames the threshold is 16n−316n-3, with exactly two failing collections of size 16n−416n-4. For n≥3n\ge3 we classify every failure of size at least 14n14n and count these collections and the inclusion-maximal ones. The case n=2n=2 answers the threshold question in Problem 2 of Berkove, Eickemeyer and Schulman (2018). All threshold, stability and counting results are formalised in Lean.

Primarily AI-generated textHuman understanding: some partsHall's theoremLean formalisationMacMahon cubescolour cubescuboidsextremal combinatorics
Nov 04, 202616 pages
PDFView work

math.CO — Combinatorics

The inverse problem for the number of connected induced subgraphs

Contributed by Lucas Almeida Almeida

For a finite graph GG, let c(G)c(G) be the number of nonempty vertex sets that induce a connected subgraph. We show that a positive integer kk equals c(G)c(G) for some finite connected graph GG if and only if k∉{2,4,5,8,9,16}k\notin\{2,4,5,8,9,16\}. Every attainable value k≠25k\ne25 is attained on ⌊log⁡2k⌋+1\lfloor\log_2 k\rfloor+1 vertices, the least possible number, and 2525 needs six vertices. More precisely, for every m≥6m\ge6 each integer from 2m−12^{m-1} to 2m−12^m-1 is the value of cc on a connected graph with exactly mm vertices. The proofs of these results are short and use no computer; computer calculations serve only as independent checks, and for two auxiliary results: the values on six to eight vertices, and the result on all connected subgraphs described below. The value 1616 falls into a gap above the path: a connected graph on n≥4n\ge4 vertices other than the path PnP_n has at least n−3n-3 more connected sets than PnP_n. The values k≥17k\ge17 are realized by a recursive construction from cones, disjoint unions and a family of graphs that we call near-cones, starting from seven small graphs; it produces a graph with c(G)=kc(G)=k in time polynomial in log⁡k\log k. The question arose from a problem of Ordoñez in continuum theory, through a reduction by Camargo, Ordoñez and Ramírez, who found the values up to 255255 by a computer search. The proof is formalized in Lean 4. We also observe that a theorem of Czabarka, Székely and Wagner on subtrees reduces the corresponding problem for the number of all connected subgraphs to a finite computation, and we report its outcome. We did not find these results in the literature, but we make no claim of novelty or priority.

A mix of human-written and AI-generated textHuman understanding: all partsLean 4connected induced subgraphsconnected setsformal verificationgraph invariantsinverse problem
Nov 03, 202621 pages
PDFView work

math.CO — Combinatorics

The ten minimum universal sets of MacMahon cubes

Contributed by Jason Davies

A collection of six-coloured MacMahon cubes is universal if eight of its cubes can be selected to build a 2×2×22\times2\times2 model of any target variety, with matching exterior colours and no internal matching requirement. We prove that exactly ten labelled collections attain the known minimum size of twelve, even when repeated varieties are allowed, resolving the conjectures of Johnson and Roldán. Usable-cube inequalities force a symmetric multiplicity matrix with row and column sums two; corner coverage then forces two disjoint triangles in Conway's tableau. The written proof is elementary and requires no exhaustive search. The classification and its discrete geometric interpretation are formalised in Lean 4. Exhaustive computation provides a separate check and additional target-count distributions.

Primarily AI-generated textHuman understanding: some partsConway's tableauEight Blocks to MadnessLean 4MacMahon cubesuniversal sets
Nov 02, 20267 pages
PDFView work

math.CO — Combinatorics

Claw-free perfect graphs are chromatic-choosable.

Contributed by Narayanan Narayanan, Suchismita Mishra, Umesh Shankar

We prove that every claw-free perfect graph GG satisfies ch⁡(G)=χ(G)=ω(G)\ch(G)=\chi(G)=\omega(G). More strongly, if SS is a clique of simplicial vertices of GG and k≥ω(G)k\ge\omega(G), every proper precoloring of SS extends to a proper coloring of GG from arbitrary lists of size kk on V(G)∖SV(G)\setminus S. The proof has three coloring steps: a mixed-list theorem for cobipartite graphs, a precoloring-extension theorem for elementary graphs built on Galvin's kernel method and a homogeneous-pair exchange argument, and a polynomial method (Combinatorial Nullstellensatz) argument for graphs of interval type in which a Vandermonde factor is transferred across each incomplete pair. The three coloring steps are assembled along the structure theorems of Chv\'atal--Sbihi, Maffray--Reed and Chudnovsky--Seymour, using double clique cutsets for composition. As a consequence, every perfect line graph is chromatic-choosable, recovering the theorem of Peterson and Woodall. Our precoloring extension theorem also resolves a conjecture posed by Chudnovsky and Seymour.

A mix of human-written and AI-generated textHuman understanding: all partsClaw-free perfect graphs.Graph coloringList Coloring Conjecture
Nov 02, 202633 pages
PDFView work

math.PR — Probability

Upper bounds for the Chvátal–Sankoff constants γk\gamma_k, k≥3k\ge3

Contributed by David Niedbala Giraudin

Lueker (J. ACM 56(3), 2009) constructed a family of finite-state machines Mh\mathcal{M}_h whose associated transfer matrices yield upper bounds on the Chvátal–Sankoff constants γk\gamma_k, and proved (his Theorem 3.26) that these bounds converge to γk\gamma_k for every alphabet size kk. He published values only for k=2k=2. For k≥3k\ge3 the best upper bounds we were able to find in the literature in September 2026 were still those of Dančík's 1994 thesis: subsequent work generalising Lueker has generalised his Section 2, the lower bound. We implement Mh\mathcal{M}_h for arbitrary kk. One ingredient has no binary analogue — the generating function of a truncation class when both sides of a minimal match pair are truncated — and we derive it. We then give a reduction by relative forms under which the transition multiplicities of the transfer matrix are falling factorials in kk; one alphabet-free construction consequently determines the exact matrix for every kk. We obtain improved upper bounds for k=3,…,15k=3,\dots,15, each supported by a Collatz–Wielandt certificate verified in exact rational arithmetic, among them γ5≤0.645033\gamma_5\le0.645033. A note added on 31 October 2026 compares these values with those of a repository made public by L. Jack on 25 October 2026.

Primarily AI-generated textHuman understanding: no partsChvátal–Sankoff constantsCollatz–Wielandt certificateslongest common subsequencetransfer matrices
Nov 02, 20267 pages
PDFView work

math.CO — Combinatorics

Local independent sets and colourings of triangle-free graphs

Contributed by Matthew Bowen, András Máthé, Oleg Pikhurko

This AI-assisted draft constructs, for every sufficiently large DD, a local rule of radius O((ln⁡D)2)O((\ln D)^2) that produces, on any triangle-free graph GG of maximum degree at most DD, a random independent set that includes each vertex with probability at least (1−oD(1))ln⁡D/D(1-o_D(1))\ln D/D. Further properties of the rule yield, for every fixed ε>0\varepsilon>0 and all sufficiently large DD, a randomised LOCAL algorithm that colours any such finite graph GG with at most (1+ε)D/ln⁡D(1+\varepsilon)D/\ln D colours, with high probability, in Oε(ln⁡D)+(ln⁡ln⁡∣V(G)∣)O(1)O_\varepsilon(\ln D)+(\ln\ln |V(G)|)^{O(1)} communication rounds. Applying known transference principles for Borel graphs, we obtain the same asymptotic bound on the number of colours for measurable and Baire-measurable colourings, and for Borel colourings of graphs with finite asymptotic separation index.

Primarily AI-generated textHuman understanding: some partsChromatic numberLOCAL algorithmdescriptive combinatoricsindependent settriangle-free graphs
Oct 31, 202629 pages
PDFView work

math.CO — Combinatorics

A degree-three local-weight cap and an improved relevant-variable bound

Contributed by Ricardo Pinho

We prove that the local-degree potential of a Boolean function of degree at most three is at most 5/4, using the published fact that such a function has at most ten relevant variables. Inserting this cap into Wellens's degree–block-sensitivity recurrence, with the existing exact certificates released by Épi, gives C_44 <= 4.3576549226. The reproduced preceding recurrence gives approximately 4.365467422574458; our exact degree-three cap lowers it by 1/128. Two separately written exact-arithmetic programs check the finite certificates, recurrence, infinite tail and finite cases of the added lemma. The universal argument is written in the paper; the published degree-three classification is cited, not re-enumerated. This preprint is not peer reviewed and not verified in a proof assistant; no optimality is claimed.

Primarily AI-generated textHuman understanding: some partsBoolean functionsblock sensitivitycomputer-assisted proofexact rational certificatespolynomial degreerelevant variables
Oct 26, 20265 pages
PDFView work

math.CO — Combinatorics

The minimum number of distinct abelian squares in a binary circular word

Contributed by Deep Bhattacharjee

We prove that every binary circular word of length nn contains at least $\fl{(n-1)/2}$ distinct abelian squares, and we determine all words attaining this bound. This settles a conjecture of Simpson: its odd case holds, and in its even case the list of extremal words misses (ab)n/2(ab)^{n/2} for n≡2(mod4)n\equiv 2\pmod 4, n≥6n\ge 6. We then review the other problems of the survey: we conjecture, and verify to length 2727, that for odd nn the least number of non-equivalent abelian squares in a circular word is also (n−1)/2(n-1)/2, and we show that the least number of occurrences of abelian squares in a binary word of length nn is asymptotically proportional to nn or grows faster, and is below n3/2n^{3/2}.

A mix of human-written and AI-generated textHuman understanding: some partsParikh vectorabelian squarecircular wordcombinatorics on words
Oct 22, 202614 pages
PDFView work

cs.DM — Discrete Mathematics

An explicit counterexample to the six-neighbor square tiling conjecture

Contributed by Chunlei Liu, Aijin Lin

Luo, Sun and Wu conjectured that in a locally finite square tiling of the complex plane in which each square intersects exactly six others, all squares have the same size. We construct a counterexample by surrounding a ten-square core with alternating rectangular shells, each formed by six squares. The only point-only contacts occur at the three four-square points in the core; all subsequent contacts have positive length. A two-state induction shows that every new square has four contacts when inserted and acquires two more at the next shell. The nested rectangles exhaust the plane, so the construction is locally finite and gives a counterexample on the whole plane.

Primarily human-written textHuman understanding: all partsSquare Tiling Conjecture
Oct 20, 20268 pages
PDFView work

math.CO — Combinatorics

Tools for proving that graphs are not graceful

Contributed by Boon Suan Ho

A graph with mm edges is graceful if its vertices can be labeled with distinct integers in [0,m][0,m] whose edge differences are exactly 1,…,m1,\dots,m. Graceful labelings have been constructed for sixty years, but there are few general methods for showing that a graph is not graceful. We start from a single generating-function identity that restates gracefulness, and derive three tools from it: residues at roots of unity, extending the classical parity condition; positivity on the unit circle, whose semidefinite form amounts exactly to the Goemans–Williamson max-cut relaxation tested against the minimum of the Dirichlet kernel; and the label interval itself, which forces the labels of a dense subgraph to have a large span. The consequences include new families of ungraceful graphs: every edge-transitive graph that contains K6K_6, the Paley graphs P(q)P(q) with q≥37q\ge37, the Kneser graphs K(n,k)K(n,k) with n≥5.61kn\ge5.61k, almost every dd-regular graph with d≥84d\ge84, and the polarity graphs ERq\mathrm{ER}_q with q≥23q\ge23, which contain no 44-cycle. For the semidefinite form of positivity we also determine exactly what it can prove, and we show that a planar refinement is strictly stronger: it excludes the Kneser graph K(11,2)K(11,2) with any seven edges deleted.

Primarily AI-generated textHuman understanding: some partsDirichlet kernelGolomb rulerdifference setsgraceful labelingmax-cutsemidefinite programming
Oct 17, 202627 pages
PDFView work

math.CO — Combinatorics

A Formally Verified Certificate Proof of the Maximum Number of Stable Matchings for Six Men and Six Women

Contributed by YURAN XIU

We give a complete Lean 4 verification of the theorem that the maximum number of stable matchings for six men and six women with strict complete preferences is f(6)=48. Jo (2026) previously proved the unrestricted upper bound, and Benjamin, Converse, and Krieger (1995) supplied an attaining construction. Our contribution is an alternative, fully formalized proof using a finite certificate; the value 48 and the unrestricted theorem are already known. We reduce stable matchings of arbitrary profiles to order ideals of sequences of cyclic partner exchanges in which no man revisits a partner. A weighted frontier recurrence counts these ideals, and a sum of permanents bounds every future continuation. These bounds yield a finite certificate with 135,828 states. The complete argument, including the reduction for arbitrary profiles, certificate soundness, all concrete checks, and an attaining profile, has been formalized and checked in Lean 4. The final unconditional theorem depends only on the standard axioms of Lean and mathlib.

Primarily AI-generated textHuman understanding: no partsLeanextremal combinatoricsformal verificationstable marriagestable matchings
Oct 16, 202613 pages
PDFView work

cs.DM — Discrete Mathematics

Fractional DAG treewidth controls DAG treewidth: profile reorientation and VC-dimension rounding

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

For a nonempty finite graph, let FF be its fractional DAG treewidth, maximized over all acyclic orientations. Its DAG treewidth is at most 160F3ln⁡(16F)160F^3\ln(16F). This answers the boundedness question of Bressan, Lanzinger, and Roth. Reorienting the graph converts shattered source profiles into projective-plane obstructions, which bound their VC dimension by 5F25F^2. Classical epsilon-net rounding then converts fractional bag covers to integral ones without changing the decomposition.

Primarily AI-generated textHuman understanding: some partsDAG treewidthVC dimensionepsilon netsfractional hypertreewidthgraph homomorphisms
Oct 15, 202610 pages
PDFView work

math.CO — Combinatorics

A characterization of cut-percolating bigraphs

Contributed by Václav Rozhoň

Conlon and Lee introduced reflection bigraphs and cut-percolation in their study of graph norms. We prove that, for connected bigraphs, these two notions coincide, confirming their prediction.

Primarily AI-generated textHuman understanding: some partsCoxeter groupsSidorenko's conjectureblock designscut-percolationgraph isomorphismgraph normsreflection groupsweakly norming graphs
Oct 11, 202655 pages
PDFView work

cs.CC — Computational Complexity

A Verified Constructive Reduction of the Cook-Levin Theorem in Lean 4: Bridging the Gap Between Complexity Theory and Formal SAT Encodings

Contributed by Jonathan 𝑓(n) Reed

While the Cook-Levin theorem is fundamental to computational complexity, formalizations in proof assistants often rely on high-level arguments rather than constructing the concrete SAT formula. Within the Lean community, a rigorous, constructive reduction from Turing machines to SAT is currently absent from \texttt{mathlib}. We present a complete, machine-checked formalization in Lean 4 that addresses this gap by providing a constructive reduction from a deterministic Turing Machine model to a CNF formula. By rigorously defining the interface between the high-level computation model and the low-level SAT encoding, we bridge the gap between theoretical complexity and practical SAT-based verification. Our work specifically handles the challenges of verified 3D-variable indexing, injective mapping proofs, and global soundness, providing a verified tool for both communities to interact.

A mix of human-written and AI-generated textHuman understanding: all partsConjunctive Normal FormConstructive ReductionCook-Levin TheoremInteractive Theorem ProvingLean 4SAT EncodingsSatisfiability CheckingSymbolic ComputationTuring Machineformal verification
Oct 08, 202616 pages
PDFView work

math.CO — Combinatorics

Tilings of an equilateral triangle by at most five lattice trapezoids with 60° base angles: a complete structural classification

Contributed by Gonzalo Barria

We study tilings of an equilateral triangle of side n in the triangular grid by k lattice trapezoids with base angles 60°, the objects behind the OEIS sequences A389392 (k = 4) and A391498 (k = 5). We prove two angle identities valid for every such tiling and a lemma relating the number of boundary vertices to the number of pieces having a side on the boundary. With these tools we show that there are exactly 1, 2 and 13 combinatorial types of tilings for k = 3, 4, 5. For k = 3 every tiling is a pinwheel. For k = 4 every tiling belongs to one of the two categories used in A389392, a fact that had previously been taken for granted. For k = 5 the thirteen types refine the eight categories of A391498; in three of them a piece has no side on the boundary. As a consistency check, the volumes of the parameter polytopes together with the generic multiplicities reproduce the leading coefficient 7/36 of the conjectured quasi-polynomial for A391498. All lemmas were checked against an exhaustive enumeration of the tilings with pairwise distinct pieces for n ≤ 15. Finally, the classification turns the thirteen types into eight explicit families of sets of shapes, and an inclusion–exclusion over them reduces the conjectured generating function of A391498 to twelve elementary counting statements, and we settle all twelve: the resulting closed formula reproduces the sequence for every n ≤ 127.

A mix of human-written and AI-generated textHuman understanding: all partsOEIS A391498lattice trapezoidsquasi-polynomialrational generating functiontilings of an equilateral triangle
Oct 01, 202623 pages
PDFView work