The authors work out the order of the number of queries needed to find complete graphs of up to five vertices in a random graph, and prove general bounds.

The paper

The paper's details are OpenAlex's; the citation count is OpenAlex's, 13 Oct 2026. The line on the paper is machine-written, as noted under Why it matters.

Why it matters

Written by Claude (claude-sonnet-5-5) on 13 Oct 2026 from the paper's abstract (as arXiv publishes it) and its OpenAlex record. Machine-written context to help a reader: it is not evidence, it moves no number, and it may be wrong. The quoted sentence is the claim; where it stands is computed from the record. If it misreads the paper, tell the stewards.

The story so far

1. 1

   What the authors did

   This is a mathematical study. The authors prove results about the Subgraph Query Problem, in which a target graph must be found in a large unknown Erdős–Rényi random graph by asking whether particular pairs of vertices are adjacent.

   Machine-written from the paper's abstract, as noted under Why it matters.

2. 2

   What they found

   • Analysing a random Painter gives an exponential improvement to the lower bound on the diagonal online Ramsey number, and a matching improvement in the off-diagonal case for fixed m≥3.
   • A different randomised Painter strategy shows that the online Ramsey number r̃(3,n) is of order n^3 up to a polylogarithmic factor.
   • The paper determines the order of the number of queries for complete graphs up to five vertices and proves general bounds for the Subgraph Query Problem.

   Machine-written from the paper's abstract, as noted under Why it matters.

3. 3

   What has been checked on Ecdysis

   Exuvia registered the claim on 13 October 2026, with a test written from the paper. No check has been filed yet.

What would check it

How far it has been checked

1. 1
   Same data, same methodverification · not yet

   Not yet: re-run the paper's analysis on its own data, where the authors have published it.

2. 2
   New data, same methodreproduction · not yet

   Not yet: the same method on new data covering the claim's population and period. Established needs one.

3. 3
   The designrobustness tests and arguments · not yet

   Nothing yet: change the method or the data and see whether it holds (a robustness test), or argue that the method does not test what the claim says.

How sure is the record?

Share this finding

Ready-made posts, written from the record. You post them yourself, from your own account; nothing is ever posted for anyone.

Click a post's text to select all of it. Both posts give the claim's standing on the record, and the longer one says what the checks show and what they do not; the wording changes when the record does. The longer post quotes the paper first, then gives the machine-written headline, marked as such; edit it as you like. To cite the claim, see Cite this claim.

What would prove it wrong

Refuted if for any k∈{3,4,5} there exists a rigorous proof that the asymptotic order of queries required to find K_k in G(N,p) differs by more than a constant factor from the order claimed in the paper, or if a counterexample demonstrates that either the general upper or lower bound for the Subgraph Query Problem is violated.

The test as Exuvia registered it on 13 Oct 2026, written from the paper's words.

The wider literature

Other claims from the same paper

• uncheckedAnalysing a Painter who colours edges at random gives a new, exponentially larger lower bound on the online Ramsey number, 2^((2−√2)n+O(1)) on the diagonal.“By analyzing the special case where Painter plays randomly, we obtain an exponential improvement \[ \tilde{r}(n,n) \ge 2^{(2-\sqrt{2})n + O(1)} \] for the lower bound on the diagonal online Ramsey nu…”

Headlines are machine-written from the paper's abstract, or from the quote and the paper's title where no abstract is open; each claim's own words are quoted beneath its headline.