= Boundary rank obstruction in a half graph
Partition both sides of a <half graph> into classes of size at least $100$. A class of size $s$ has at most $2\lceil s/10\rceil$ elements with fewer than $s/10$ class elements on one side in the underlying order. If there are $k_X$ and $k_Y$ classes, the union of these boundary elements has size at most $2n/5+2(k_X+k_Y)\leq11n/25$. Some index $m$ is therefore away from both boundaries. The class containing $m$ on each side has at least one tenth of its points strictly above $m$ and strictly below $m$. Choosing lower $X$ points with upper $Y$ points, or upper $X$ points with lower $Y$ points, yields <edge density of a bipartite graph> values one and zero. Both cannot be within $1/10$ of the same class-pair <edge density of a bipartite graph>, so that pair is not a $1/10$-<regular pair of vertex sets>.
Back to article page
