ProofAtlas

Graph theory · decision-tree complexity · topological combinatorics

Aanderaa–Karp–Rosenberg Conjecture

Collaboration beta

Must every nontrivial monotone graph property sometimes inspect every possible edge before deciding whether the property holds?

D(P)=(n2)
Known results and sources
A finite graph is crossed by a branching sequence of edge queries that ends at an unresolved highlighted shell, with no completed proof path shown.
The conjecture asks whether some input always forces every possible edge query; the retained route narrows the obstruction but still lacks an actual-node synchronization theorem.

Research problem

Exact mathematical statement

Let PP be a nonconstant monotone property of finite simple undirected graphs on a fixed labeled vertex set of size nn, invariant under relabeling. In the deterministic edge-query model, an algorithm asks whether individual potential edges are present. The conjecture says that the worst-case query complexity is

D(P)=(n2).D(P)=\binom{n}{2}.

Equivalently, every such property is evasive: some input forces every possible edge to be queried. The retained source develops a substantial ten-vertex route, but claims neither an n=10n=10 proof nor a uniform all-nn proof.

Problem infographic

Problem at a glance

A problem-first graph decision-tree schematic separates a complete ten-vertex edge set, a branching query history, several certified residual shell motifs, and the missing transition to an actual node; the general all-vertex case remains open.
Certified high-depth residual shells would contradict a shallow decision tree if reached with the exact remaining edges. The missing step must force one shell at an actual node and then extend the mechanism beyond ten vertices.

Current mathematical picture

Where work on Aanderaa–Karp–Rosenberg Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureStatic aligned-scaffold contradiction

The source records that pure aligned factorial equations are globally consistent and that static fixed complexes repeatedly cone off. Use a sibling-aware invariant tied to actual query histories rather than another static formal restriction.

Route status · Narrowed route
Main reductionRepair-diamond and remote-orbit funnel

The current work reports universal repair-diamond obstructions, eighty-six two-edge obstructions, and a C2 by C5 fixed-point obstruction on the remote block.

Evidence posture · Source-reported route statement · dependencies incomplete
Priority open bridgeProve the exact actual-node sibling-synchronization interface for at least one certified shell family.Task status · Ready to work on

Work mapped so far

Aanderaa–Karp–Rosenberg Conjecture in numbers

1.2kretained lines of mathematical investigation1,201 in the current working snapshot
Argument development
955 · 80%
Explored or eliminated routes
34 · 3%
Computational analysis
74 · 6%
Open obligations
79 · 7%
Definitions and setup
59 · 5%
7selected mapped statements2routes investigated5open questions5contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byRichard M. KarpStatus checkedAug 25, 2026
Source recordedAug 25, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

14 selected steps

Scroll horizontally to explore the route

Working route overview for Aanderaa–Karp–Rosenberg ConjectureA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Every nontrivial monotone graph property should be evasive. — Depends on missing premiseEvery nontrivial monotonegraph property should beevasive.Current reduction — Depends on missing premiseCurrent reductionRepair-diamond and remote-orbit funnel — Depends on missing premiseRepair-diamond andremote-orbit funnelTerminal-independent jump and nonet — Depends on missing premiseTerminal-independent jumpand nonetClosing target — Depends on missing premiseClosing targetFour-migration terminal census — Depends on missing premiseFour-migration terminalcensusOdd two-anchor selector coefficient — Depends on missing premiseOdd two-anchor selectorcoefficientStatic aligned-scaffold contradiction — stoppedStatic aligned-scaffoldcontradictionPure total edge ordering — stoppedPure total edge orderingProve the exact actual-node sibling-synchronization interface for at least one certified shell family. — OpenProve the exact actual-nodesibling-synchronizationinterface…Construct or refute a sibling-relative topological obstruction for overlapping selector, diamond, or nonet frames. — OpenConstruct or refute asibling-relative topologicalobstruction…Find a uniform all-n mechanism rather than treating a possible ten-vertex contradiction as the full theorem. — OpenFind a uniform all-nmechanism rather thantreating…Formal shells are not actual nodes — OpenFormal shells are not actualnodesUniform all-n mechanism — OpenUniform all-n mechanism
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded
Narrowed routeStatic aligned-scaffold contradiction

The source records that pure aligned factorial equations are globally consistent and that static fixed complexes repeatedly cone off. Use a sibling-aware invariant tied to actual query histories rather than another static formal restriction.

Route status · Narrowed route
Narrowed routePure total edge ordering

The current work records explicit orderings that avoid the simplest last-two selector pattern and one-variable extensions that collapse the universal nonet. Track both answers, colored partial assignments, overlapping frames, and exact remaining depth in a parity adversary, relative-homology calculation, or bounded query-tree search.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

5 featured tasks
01
Prove the exact actual-node sibling-synchronization interface for at least one certified shell family.Suggested move: Write the reverse-Möbius transition for the odd selector coefficient under a residual-edge query, then test whether a mod-two sum over labeled two-anchor frames guarantees a preserving child without losing the required free shell edges.
Ready to work on
02
Construct or refute a sibling-relative topological obstruction for overlapping selector, diamond, or nonet frames.Suggested move: Enumerate invariant monotone child pairs under one shared parent query and compute relative boundary maps, retaining graph-isomorphism identifications and exact depth budgets.
Ready to work on
03
Formal shells are not actual nodes

None of the high-depth formal shells closes the decision-tree argument until its exact free-edge set is forced at an actual node.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
04
Uniform all-n mechanism

A ten-vertex contradiction would still require a distinct invariant or reduction that works uniformly for arbitrary vertex counts.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.
Ready to work on
05
Find a uniform all-n mechanism rather than treating a possible ten-vertex contradiction as the full theorem.Suggested move: Stress-test any surviving synchronization invariant on general two-anchor selector blocks, prime-power residual blocks, remote prime orbits, and iterated repair lifts.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 25, 2026
Current statusOpen conjecture

The finite Aanderaa–Karp–Rosenberg conjecture remains open. Topological methods prove important special cases, including prime-power vertex counts, while the cited ten-vertex work restricts possible counterexample structure without closing that case.

[1][3]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. PreprintCsernák and Soukup explicitly describe the finite conjecture as unsettled while proving contrasting results for infinite vertex sets.[3]
  2. PreprintEngström classifies the transitive graphs that can occur in a possible ten-vertex counterexample, narrowing but not resolving the n=10 case.[2]
  3. Peer reviewedKahn, Saks, and Sturtevant introduced the topological fixed-point method and established evasiveness for prime-power vertex counts; the cited summary also records the n=6 case.[1][2]
3 cited sources3 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusAanderaa–Karp–Rosenberg conjecture
Solved special caseprime-power and six-vertex cases

The exact evasiveness statement is known when the number of vertices is a prime power and, as recorded by Engström, for six vertices.

[1][2]
Dependency or reductionten-vertex transitive counterexample structure

Any ten-vertex counterexample must respect Engström's classification of possible transitive graphs; this is a restriction, not a proof of the ten-vertex case.

[2]
Related problemelusiveness on infinite vertex sets

Infinite-vertex evasiveness has substantially different behavior and does not settle the finite conjecture.

[3]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

  • Formalization targetA statement-aligned formalization would need the deterministic edge-query decision-tree model, nonconstant monotone isomorphism-invariant graph properties, and exact equality with the full edge count.
  • Formalization targetThe established prime-power and n=6 cases do not provide a uniform all-n theorem.
  • Formalization targetThe current work's ten-vertex actual-node synchronization interface remains source-reported research rather than externally reviewed evidence.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements2 proposed statements5 open questions2 narrowed routes
Statements by mathematical role7 selected mapped statements
  • theorem candidate1 of 71
  • reduction3 of 73
  • lemma3 of 73
Selected mathematical clusters1 mathematical clusters
Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 2 routes included
  • retained route statementEvery nontrivial monotone graph property should be evasive.
  • retained route statementCurrent reductionintermediate
  • retained route statementClosing targetintermediate
  • retained route statementFour-migration terminal censusintermediate
  • retained route statementTerminal-independent jump and nonetintermediate
  • retained route statementOdd two-anchor selector coefficientintermediate
  • retained route statementRepair-diamond and remote-orbit funnelintermediate
  • Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
  • DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
  • Useful failureStatic aligned-scaffold contradictionreported failure
  • Useful failurePure total edge orderingreported failure
  • Research targetProve the exact actual-node sibling-synchronization interface for at least one certified shell family.open
  • Research targetConstruct or refute a sibling-relative topological obstruction for overlapping selector, diamond, or nonet frames.open
  • Research targetFind a uniform all-n mechanism rather than treating a possible ten-vertex contradiction as the full theorem.open
  • Research targetFormal shells are not actual nodesopen
  • Research targetUniform all-n mechanismopen
  • ComputationThe current work contains finite rooted-function, support, diamond, homology, and long C++ audit artifacts with recorded checks and digests.ProofAtlas did not execute any submitted attachment during intake. Every reported finite result therefore remains source-reported pending separately authorized reproduction and independent review. · reported unreproduced
  • Narrowed routeStatic aligned-scaffold contradictionThe source records that pure aligned factorial equations are globally consistent and that static fixed complexes repeatedly cone off. Use a sibling-aware invariant tied to actual query histories rather than another static formal restriction.
  • Narrowed routePure total edge orderingThe current work records explicit orderings that avoid the simplest last-two selector pattern and one-variable extensions that collapse the universal nonet. Track both answers, colored partial assignments, overlapping frames, and exact remaining depth in a parity adversary, relative-homology calculation, or bounded query-tree search.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeProve the exact actual-node sibling-synchronization interface for at least one certified shell family.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Supply a complete argument with every imported premise identified.
  • Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointProve the exact actual-node sibling-synchronization interface for at least one certified shell family.

Aanderaa–Karp–Rosenberg Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Must every nontrivial monotone graph property sometimes inspect every possible edge before deciding whether the property holds?

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references3 cited works · next context review by Nov 25, 2026

The mathematical context was checked on Aug 25, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    Evasiveness of Graph Properties and Topological Fixed-Point Theoremssurvey or monograph · Carl A. Miller · Foundations and Trends in Theoretical Computer Science · 2013 · ARXIV 1306.0110 · DOI 10.1561/0400000055 · accessed Aug 25, 2026
  2. 2
    Transitive graphs in counterexamples to Karp's conjecturepreprint · Alexander Engström · arXiv · 2005-12-17 · ARXIV math/0512421 · accessed Aug 25, 2026
  3. 3
    Elusive properties of infinite graphspreprint · Tamás Csernák, Lajos Soukup · arXiv · 2021-12-29 · ARXIV 2112.14689 · accessed Aug 25, 2026

Important qualifications

  • The bounded primary-source search establishes the finite conjecture's open status and representative partial results, not an exhaustive history.
  • The infinite-vertex paper concerns a different domain and is included only to mark that distinction.
  • No packet attachment, submitted URL, or source-reported computation was used as independent external status authority.
  • No statement-aligned formalization or independently reproduced computation was established by this scoped search.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image