Maximum Clique Detection via Second-Order Local Statistics Theoretical and Experimental Analysis on DIMACS Benchmarks

We present a polynomial-time algorithm for the Maximum Clique Problem (MCP) based on second-order local statistics (common neighborhood intersections). The core is a five-phase pipeline (0–4); two further deterministic refinement phases — Phase 5 (budgeted plateau search) and Phase 8 (Hall-violation exchange augmentation) — and an optional, budgeted Phase 2.5 (triangle anchoring) extend it. The algorithm finds optimal solutions on 34 of the 38 DIMACS benchmark instances with proven optima (89.5%), achieving 100% success on all pure random graphs G(n, p), all adversarial degree-compensated instances (brock family, 100%), all regular algebraic instances (hamming10-4, 100%), and all explicit planted-clique instances. On the large open instances without a proven optimum it now matches the best-known value on C500.9 (≥57, found: 57) and C1000.9 (≥68, found: 68), and is within 3 vertices on C2000.9 (≥80, found: 77). On six previously unseen BHOSLIB (Model-RB) instances, run unmodified to rule out benchmark overfitting, it matches 3 of 6 hidden optima exactly with graceful degradation (gap ≤2) on the rest. Two new algorithmic phases are introduced: Phase 3 (ratio-slice exploration) detects distributional asymmetry in the restricted-degree profile within cells without any external knowledge of graph type, resolving brock800 (gap 0) and hamming10-4 (gap 0); Phase 4 (swap chain refinement) traverses the local neighborhood of the solution in swap space via iterative 1→1 swaps, resolving gen200_p0.9_44 and gen400_p0.9_75 (gap 0). Phase 5 additionally traverses same-size plateaus from an elite pool of trajectories, accounting for every remaining v3.1 gain on the C family and on gen400_p0.9_55. Phase 8 enumerates coordinated exchanges of bounded width in the complement graph, certifying — rather than merely failing to find — the absence of small augmenting moves: on MANN_a45 it proves the known optimum is isolated from the 344-clique by a coordinated exchange of width ≥9, the first such exchange-optimality certificate reported for a DIMACS local optimum. Running Phase 2 to completion via deterministic slice-parallelism (24 workers, bit-for-bit identical to the sequential sweep) establishes, for the first time, the method's exact ceiling on MANN-scale instances: exhaustive coverage proves the optimal cells are always processed and that every residual gap therefore lies in extraction, never in cell selection. A two-part classifier — LP persistency and colour (WL) refinement — separates the residual gaps into exactly two structural mechanisms: symmetry (provably immune to any isomorphism-invariant feature) on MANN, and camouflage (computationally hidden under Model-RB hardness) on BHOSLIB. We show the method's success boundary coincides with this tractability frontier. Phase 2.5 then probes the one kind of signal the symmetry theorem does not forbid — conditioning on a concrete third vertex, which is not isomorphism-invariant — and, run to completion, pierces the exhaustively-established ceiling on keller6 (55→57, gap 4→2), the first such result in this work; the same mechanism, run to completion, does not improve MANN_a45 or the BHOSLIB family, splitting symmetric hardness into an anchorable and an isolated subclass. We develop a quantitative theoretical model centered on the difficulty metric ρ = ω/√(p²n), classifying instances into three distinct regimes with provably different failure mechanisms: Regime 1 (ρ ≲ 1.5, guaranteed exact recovery via martingale analysis), Regime 2 (ρ > 1.5, accumulated greedy error partially corrected by local swaps), and Regime 3 (adversarial calibration that destroys all polynomial local signals). Formal results include a correctness theorem for Regime 1 (Theorem 6.6), a calibration barrier theorem (Theorem 6.9), correction capacity bounds (Theorem 6.11), a negative result on multi-scale block sampling (Theorem 6.15), and an asymptotic tractability conjecture (Conjecture 6.14). Fifteen partial formal results toward Conjecture 6.14 are presented in Appendix E (F.1–F.15), establishing equivalence to the Grimmett–McDiarmid (1975) gap, open for 50 years, proving that greedy errors follow a Poisson distribution in the tractable regime (F.14, verified by Monte Carlo), and showing — via a dispersion test on 90 measured instances (F.15) — that this regime's residual failures are not independent per cell but a mixture at the level of the instance. We additionally show, by direct measurement on an exact branch-and-bound solver, that seeding it with the method's own optimum removes only ≈3% of the search on tractable instances and nothing on MANN — the method contributes to exhibiting a clique (the NP half) but not to proving optimality (the co-NP half). The base algorithm runs in O(p³n⁴ log n) worst-case time with bitset optimizations and exhibits empirical O(n³ log n) behavior on DIMACS instances. Complete, deterministic C implementations (base pipeline ~700 LOC; extended versions with Phases 5, 8, and 2.5), all experimental data, and proofs are provided in a public repository.