View PDF HTML (experimental)

Abstract:We study monotonicity testing of real-valued functions on directed acyclic graphs (DAGs) with $n$ vertices. Let $m$ and $\ell$ be the numbers of edges in the transitive reduction and the transitive closure, respectively. For $1\le c\le d\le2$, define $u(c,d):=\min\left\{\frac12,\frac c3,\frac{c+d}{2}-1\right\}$. We show that every family of DAGs with $m=n^{c+o(1)}$ and $\ell=n^{d+o(1)}$ admits, for every fixed $\varepsilon\in(0,1)$, a non-adaptive tester with one-sided error that uses $O_\varepsilon(n^{u(c,d)+o(1)})$ queries. Conversely, we show that for every sufficiently small fixed $\varepsilon>0$ and every fixed $(c,d)$, there are families of DAGs satisfying $m=n^{c+o(1)}$ and $\ell=n^{d+o(1)}$ on which every randomized non-adaptive tester, even with two-sided error, requires $n^{u(c,d)-o(1)}$ queries, making the upper bound tight up to a factor $n^{o(1)}$. Our main technical contribution is a lower-bound technique based on Ruzsa--Szemerédi families of positive matchings.

Submission history

From: Yuichi Yoshida [view email]
[v1] Tue, 17 Feb 2026 04:14:41 UTC (120 KB)
[v2] Sun, 22 Mar 2026 10:40:28 UTC (120 KB)
[v3] Thu, 16 Jul 2026 00:38:26 UTC (99 KB)