Version history

Submission versions

  1. lax-614640current version

    Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

  2. lax-47viewing

    Tight Inapproximability of Max Independent Set in Triangle-Free Graphs

    GitHub sourceShown on this page

Proof of `Tight inapproximability of Max Independent Set in triangle-free graphs`

groundedproofs/Lax47Proofs/Main.lean · lax-47

What this proof establishes

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

The polynomial-cutoff randomized blow-up converts a purported N1/2−εN^{1/2-\varepsilon} triangle-free approximation into a bounded-error, polynomial-step solver for Håstad's general-graph promise gap. Håstad's hardness theorem then contradicts NP⊈BPPNP\nsubseteq BPP.