Discrepancy and Sparsity

Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez +2

We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs $H$ of a gra…