Minimum Graded Discrepancy of Graphs

Source abstract

In this paper, we study the graded discrepancy of graphs. We show that for any fixed $p$ in $(0,1),$ there exists a sequence of $n$-vertex graphs $\{G_n\}$ with edge densities tending to $p$ such that $G_n$ admits a vertex ordering whose graded discrepancy is bounded by a constant independent of $n.$ The construction combines a structured graph layout with a round-robin vertex ordering and blockwise interleaving.