While this submission is a draft, it cannot be used by other submissions.

Proof of `Circuits for patterns of bounded forestwidth`

groundedproofs/Lax461425Proofs/CircuitsForPatterns.lean · lax-461425

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

If FF has an edge, after unfolding ForestwidthLEΔ(k−1)FForestwidthLE Δ (k - 1) F (the arithmetic (k−1)+1=k(k - 1) + 1 = k, using k≥2k ≥ 2, is immediate) into a DepthDecompositionFΔkDepthDecomposition F Δ k, we split on whether FF has isolated vertices (isoJF=0isoJ F = 0 or not) and invoke existscircuitofnoIsolatedexists_circuit_of_noIsolated or existscircuitofisolatedexists_circuit_of_isolated respectively (existscircuitofedgeexists_circuit_of_edge). If FF has no edges, homKFnhom K F n is the constant n∣F.A∣∗n∣F.B∣n ^ |F.A| * n ^ |F.B| (homeqconstofnoedgehom_eq_const_of_no_edge), computed by the single-gate constCircuitconstCircuit, of size 11.