A clique is a set of vertices in which every two distinct vertices are adjacent. Finding a clique of a prescribed size is a basic graph problem. Even when the size is fixed, the exponent of the input size matters. Enumerating ordered lists of nine vertices, for example, takes time proportional to the ninth power of the number of vertices. Algorithms for matrix multiplication have long given a better benchmark. For clique sizes divisible by three, Nešetřil and Poljak grouped the vertices into three blocks and reduced the problem to matrix multiplication. Their bound underlies the -Clique Hypothesis used in fine-grained complexity. Vassilevska Williams and Zamir, introduction
The input to the counting problem is a simple undirected graph on vertices. A set of vertices contributes one to the answer if all its pairs are edges. In particular the ordering of its vertices contributes no multiplicity. The clique size is fixed when measuring running time as a function of .
An intermediate problem uses nine labeled positions. Each position receives one of possible values. A unary table supplies a weight for each position and value, and a binary table supplies a weight for each edge of the pattern and its two values. The task is to sum the product of these weights over all assignments. The sum allows repeated values. Pairwise zero weights can enforce distinctness when an application needs copies of the pattern. Arithmetic takes place in a field of characteristic zero. Write for the infimum of admissible square matrix multiplication exponents over that field. Paper, Section 3
There is an absolute such that the weighted sum for every nine-vertex pattern can be computed with
arithmetic operations. The statement expresses the lower-order term by allowing every positive exponent slack. One program for a given pattern and size must work for every choice of weight tables.
The mission goal is exact clique counting. There are constants and such that, for each fixed , a word-RAM algorithm counts the -cliques in time
The bounds cover all sufficiently large clique sizes, including sizes outside the multiples of nine. The saving is relative to the matrix multiplication exponent itself and applies even if it is two. Paper, Theorems 1.1 and 1.2
For a fixed large clique size the improvement is polynomial in the number of vertices, and the exponent gained grows linearly with the clique size. Since the output is the exact count, checking positivity also gives a decision algorithm. A future improvement in the upper bound on matrix multiplication would improve the baseline and the clique bound together. A formal proof would let a reader inspect which parts use only field operations and where the integer representation and the costs of machine instructions enter. Paper, Section 3.4 and Appendix A
At , writing down a dense matrix of order already takes writes. A derivation that starts with three such matrices supplied for free would miss a central part of the result. The input for the arithmetic milestones consists of the original small weight tables. The costed program must compute the desired output on all table entries, including the arithmetic needed to construct its projected factors. The word-RAM theorem has a separate obligation to control the representation of the numbers used during clique counting. Paper, Lemma 3.4 and Appendix A
The draft uses Mathlib simple graphs on finite vertex types and the published adjacency-matrix input layout and word-RAM interpreter. The output is the signed value in the first word after the input. The word-width constant and program may depend on fixed . The logarithmic word size permits a single output word wide enough for the count. The goal uses the conventional characteristic-zero exponent represented by . The arithmetic milestone uses the exponent of the actual coefficient field. The transition from arithmetic programs to uniform word-RAM code, including a suitable exact integer matrix multiplication implementation, belongs to the proof of the goal.
The algebraic milestones use dyadic domain sizes, rational partial-swap identities and the explicit four-vector product basis. The decomposition milestone isolates the finite identity and its rank and term-count savings. There is a separate costed basis-transform statement. The folding milestones cover the free-coordinate bijection, the loss of one edge per active wedge, and the construction of all transformed tables in one quadratic-size arithmetic program. The proof of the complete algorithm must also account for generation of the decomposition data, the finite induction on the number of pattern edges, and the lift to arbitrary clique size. The draft statements are open proof targets.
The operation count in Theorem 1.2 uses the arithmetic-program definition. Prove2Me’s matrix multiplication campaign uses the tensor-rank definition. In this mission’s Lean environment the proved comparison over the complex numbers gives . Thus the same word-RAM program and the same saving in Theorem 1.1 give the bound stated with the campaign exponent. The clique result uses no numerical upper bound on either exponent.
theorem VWZClique.count_large_cliques :
∃ δ : ℝ, 0 < δ ∧ ∃ K₀ : ℕ, ∀ k ≥ K₀,
VWZClique.countsWithin k
((OAI.MatrixMultiplication.Arithmetic.omega ℂ - δ) * (k : ℝ) / 3) := by sorryFor every sufficiently large fixed clique size, exact clique counting on adjacency-matrix inputs admits a word-RAM algorithm with running time for an absolute .
No open leaves. Every sub-goal is proved or awaiting decomposition.