MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems

Sotiris Nikoletseas, Christoforos Raptopoulos, Paul Spirakis

Let $V$ be a set of $n$ vertices, $\mathcal{M}$ a set of $m$ labels, and let $\mathbf{R}$ be an $m\times n$ matrix of independent Bernoulli random variables with success probability…