Graded discrepancy of graphs and hypergraphs

Abstract

This paper studies the following question of Bollobás and Scott: Let $G$ be a graph with $n$ vertices and $p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges. What is the smallest $c(p,n)$ such that there is an ordering $v_1,\dots ,v_n$ of the vertices in $G$ with $\left|e(\{v_1,\dots ,v_i\})-p\left(\genfrac{}{}{0ex}{}{i}{2}\right)\right|\le c(p,n)$ for all $i\in \{1,\dots ,n\}$ ? We obtain upper and lower bounds for $c(p,n)$ that are both linear in $n$. Furthermore, we generalize the result to $k$-uniform hypergraphs.