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 `Promise-gap hardness of Max Independent Set`

groundedproofs/Lax47Proofs/IndependentSetGapHardness.lean · lax-47

Description

Apply the registered PCP-to-clique gap reduction with exponent 1/q1/q. The threshold guard converts its relative gap into the absolute independent-set gap on the complement. Graphs below the solver cutoff are handled by bounded exhaustive search. The finite-Turing adapter certifies this comparison, and independent majority trials provide the error bound needed for composition.