A polynomial versus superpolynomial gap in vertex-distribution-free graph testing

Abstract

A full negative answer to Gishboliner–Shapira's comparison question in Oberwolfach Report 19/2019, Problem 5 (printed p.1139), and arXiv:1905.09903v5, Problem 5.6. The single fixed hereditary, extendable property consists of K4-free graphs becoming 3-colorable after deletion of at most one vertex. It has a polynomial classical canonical tester for every nonempty finite input size, but requires superpolynomial worst-case total sample-plus-adjacency cost in the vertex-distribution-free model against adaptive two-sided testers, even with the vertex set, size, complete positive rational weight vector and heavy vertex supplied. Distances count unordered changed pairs weighted by the product of their vertex masses and allow arbitrary additions and deletions. Five-page research note with a self-contained classical sampling argument and an exact factor-36 tripartite-cover/heavy-apex reduction importing the established Alon–Shapira two-sided triangle-testing lower bound. Earlier colorability sampling, hard-triangle, parity and heavy-vertex techniques are credited explicitly. The unchanged original direct proof, explicit rational hard family, six standard-library verification programs and independent mathematical/priority reports are included. Finite computations supplement the analytic proofs. No sample-only claim with unlimited free arbitrary-name queries or polynomial running-time claim is made. A bounded current primary-source priority audit identified no earlier full answer; novelty and exhaustive priority are uncertified. The official 2021 GS journal body was unavailable, manuscript identity with it was not assumed, forward-citation retrieval was incomplete, and the original full Behrend/RS articles were unrecovered; source inspection limits are documented. AI tools were used extensively in development, verification, literature review and writing. Unrefereed; independent adversarial reviews were AI-assisted. No external human peer review, journal acceptance or formal proof-assistant certification is claimed.