1 · The essentials
Weisfeiler–Leman refinement is a procedure for comparing graphs, with a setting called dimension that affects the comparison. This family of manuscripts studies how much computation its decisions require. For every sufficiently large fixed dimension, one manuscript shows that some comparisons require time whose power grows at least proportionally with that dimension. This conclusion needs no unconfirmed complexity assumption, but it applies to the specific sequential computing models and graph input format stated in the manuscript. When the dimension is supplied as part of the input, the comparison problem is complete for a class of problems solvable in exponential time—even when each vertex has at most three neighbors. A related question, whether refinement identifies a graph among all comparison graphs, has the same complexity classification. The main result has a Lean formalization, though the supplied source does not specify its exact coverage.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine comparing two network diagrams using a checking procedure with an adjustable setting. The manuscripts distinguish between choosing that setting in advance and allowing each new comparison to specify it; they also distinguish comparing two diagrams from asking whether one diagram can be singled out against every possible alternative.
Why it matters
The unconditional lower bounds establish computational limitations without relying on a complexity conjecture. They persist for connected graphs of diameter at most two, while the variable-dimension comparison classification persists for graphs of maximum degree at most three. These restrictions make precise that the stated difficulty remains within particular constrained graph families.
2 · Going further
The fixed-dimension problem asks whether two -vertex graphs are -dimensional Weisfeiler–Leman equivalent, under either joint or separate-coordinate replacement. Manuscript 3 shows in the manuscript an unconditional deterministic sequential worst-case lower bound of for every sufficiently large fixed . The bound holds at every sufficiently large graph order, even for simple connected uncolored graphs of diameter at most two. Its input representation is explicit adjacency matrices, and its computing models are multitape Turing machines and sequential logarithmic-word RAMs with fixed polynomial-bit-time instructions.
The main manuscript supplies a construction for : two uncolored graphs are equivalent exactly when a prescribed finite-domain choice system has no compatible choice. The system uses domains for joint refinement and domains for separate-coordinate refinement. A compatible choice is detected after two joint rounds or one separate round. Applied to sparse satisfiability, this construction yields fixed-dimension time exclusions under positive-rate ETH, even for deciding equality of the histograms at those early rounds. This conditional conclusion is distinct from Manuscript 3's unconditional lower bound; the abstracts do not describe the latter's argument.
The other companions address dimension supplied as input. Manuscript 4 shows in the manuscript that joint-update equivalence is -complete for binary-encoded , with explicit adjacency-matrix inputs, even for connected simple uncolored graphs of equal positive order and maximum degree three. Manuscript 2 shows in the manuscript that identification is also -complete: its input is a nonempty finite simple uncolored graph in adjacency-matrix form and a positive binary-encoded dimension. Unlike a comparison of two supplied graphs, identification quantifies over every comparison graph.
Useful notions
- Graphs, vertices, and adjacency matrices
- Worst-case running time
- Fixed parameters versus parameters supplied as input
- Conditional versus unconditional complexity bounds
- Complexity classes and completeness
What was known before / what is new
Before
The supplied source gives no historical account of earlier bounds or algorithms. It takes joint and separate-coordinate Weisfeiler–Leman refinement as the procedures under study and distinguishes pairwise equivalence from identification against every comparison graph.
New
The main manuscript presents a choice-system construction linking the absence of a compatible choice to Weisfeiler–Leman equivalence, with detection of successful choices after only the stated early rounds. The companions give unconditional fixed-dimension time lower bounds and variable-dimension EXPTIME-completeness classifications. The latter cover joint equivalence on subcubic graphs and identification of an input graph.
Limits and assumptions
The main construction assumes , and its sparse-satisfiability time exclusions assume positive-rate ETH. The unconditional bounds apply to sufficiently large fixed dimensions and sufficiently large graph orders in the specified sequential adjacency-matrix models; the source does not assert them for arbitrary computation models or representations. The variable-dimension equivalence classification concerns joint updates with binary-encoded , whereas the identification input permits any positive binary-encoded dimension. The main result has a Lean formalization, but the source does not state its exact scope, so formal verification should not be attributed to every companion claim. No remaining open problem is specified.
Mini glossary
- Weisfeiler–Leman equivalence —
- The relation of two graphs being treated as equivalent by Weisfeiler–Leman refinement at the specified dimension and update convention.
- Identification —
- The property of refinement identifying a graph, with the comparison ranging over every comparison graph rather than just one supplied graph.
- Fixed dimension —
- A dimension chosen in advance rather than supplied as part of each input.
- Unconditional lower bound —
- A limitation on required computation time that does not depend on a complexity assumption.
- Subcubic graph —
- A graph whose maximum vertex degree is at most three.
Keywords : Weisfeiler–Leman refinement · Time lower bounds · EXPTIME-completeness
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Proves unconditional deterministic time lower bounds for joint and separate k-dimensional Weisfeiler–Leman equivalence, for sufficiently large fixed k in the specified sequential adjacency-matrix models. With dimension as input, joint equivalence is EXPTIME-complete even on subcubic graphs; deciding whether refinement identifies a graph is also EXPTIME-complete.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalence
25/09/2026For k ≥ 4, we construct two uncolored graphs that are k-dimensional Weisfeiler–Leman equivalent exactly when a prescribed finite-domain choice system has no compatible choice. The system has domains for joint refinement and k for separate-coordinate refinement. A successful choice is detected after two joint rounds or one separate round. Applied to sparse satisfiability, the reduction gives fixed-dimension time exclusions under positive-rate ETH, even for deciding equality of these early histograms.
The complexity of identifying a graph by Weisfeiler–Leman refinement
25/09/2026We prove that deciding whether Weisfeiler–Leman refinement of an input dimension identifies a given graph is EXPTIME-complete. The input is a nonempty finite simple uncolored graph in adjacency-matrix form and a positive binary-encoded dimension. Identification quantifies over every comparison graph.
Unconditional time lower bounds for Weisfeiler–Leman equivalence
25/09/2026For every sufficiently large fixed k, deciding whether two n-vertex graphs are k-Weisfeiler–Leman equivalent requires deterministic sequential time in the worst case. The bound holds at every sufficiently large graph order, even for simple connected uncolored graphs of diameter at most two, without a complexity assumption. Inputs are explicit adjacency matrices; the models are multitape Turing machines and sequential logarithmic-word RAMs with fixed polynomial-bit-time instructions. Both joint and separate replacement conventions are covered.
Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphs
25/09/2026Deciding joint-update k-dimensional Weisfeiler–Leman equivalence is -complete when the two graphs are given by explicit adjacency matrices and k ≥ 2 is encoded in binary. The result holds even for connected simple uncolored graphs of equal positive order and maximum degree at most three.