Q(s,r) asymptotics for growing s and r

Open Problem: asymptotic behavior of $Q(s,r)$ when $s$ and $r$ grow together · arXiv:1905.10483

arXiv Problem high confidence— first stated 2020-02-26

Authors: Noga Alon, Ryan Alweiss

Status open high confidence

Alon and Alweiss (2020) proved Q(s,r) = (1+o(1)) log_2 r for every fixed s as r tends to infinity, but the asymptotic behavior of Q(s,r) when both s and r grow simultaneously remains open. A wide search of arXiv and Semantic Scholar found no follow-up paper addressing this joint-growth regime. The problem appears to be genuinely open with no published progress as of May 2026.

Reviewer notes. No follow-up work found in indexed literature. The open problem concerns the joint regime s,r -> infinity simultaneously; the fixed-s regime was fully resolved in the source paper. Five web calls used: arxiv abstract fetch, ar5iv HTML fetch, Semantic Scholar page fetch, and two broad web searches.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Determine the asymptotic behavior of $Q(s, r)$ when $s$ and $r$ grow together (i.e., when $s$ is not fixed as $r \to \infty$).

Context

The paper resolves $Q(s,r) = (1+o(1))\log_2 r$ for every fixed $s$ as $r \to \infty$, but explicitly states in the abstract that the problem of determining the asymptotic behavior of $Q(s,r)$ when both $s$ and $r$ grow simultaneously remains open.

Notes. Section 4 (concluding remarks and open problems) is referenced in the introduction but its full content is not present in the extracted PDF text; additional open problems from that section may be missing.

Source paper

On the product dimension of clique factors
Noga Alon, Ryan Alweiss · 2020-02-26
https://arxiv.org/abs/1905.10483 PDF source