Descriptive complexity of countable unions of Borel rectangles

Abstract We give, for each countable ordinal ξ ⩾ 1 , an example of a Δ 2 0 countable union of Borel rectangles that cannot be decomposed into countably many Π ξ 0 rectangles. In fact, we provide a graph of a partial injection with disjoint domain and range, which is a difference of two closed sets, and which has no Δ ξ 0 -measurable countable coloring.