n/polylog(n) bound for ordered pure pairs

Status open medium confidence

Conjecture 1.7 (due to Korándi, Pach, and Tomon) asserts that $f_H(n)$ is linear in $n$ for every acyclic matrix $H$. Scott, Seymour, and Spirkl informally believe this conjecture is false and suggest $n/\operatorname{polylog}(n)$ as a plausible correct bound; their paper establishes the weaker result $f_H(n) = n^{1-o(1)}$ for every acyclic $H$. No subsequent work found in the indexed literature has resolved either Conjecture 1.7 or the informal $n/\operatorname{polylog}(n)$ belief.

Reviewer notes. Conjecture 1.7 is by Korándi, Pach, and Tomon (linear bound for $f_H(n)$ for every acyclic $H$). The informal belief reviewed here is the authors' meta-conjecture that 1.7 is false and $n/\operatorname{polylog}(n)$ is the right bound. The source paper itself proves $f_H(n)=n^{1-o(1)}$, which is an intermediate result. No follow-up paper was found in the indexed literature resolving either question. Confidence is medium rather than high because the conjecture is now 4+ years old and absence of follow-up may reflect difficulty rather than lack of activity.

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