Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates

Mathew C. Francis, Atrayee Majumder, Rogers Mathew

A graph $G$ on $n$ vertices is a \emph{threshold graph} if there exist real numbers $a_1,a_2,\dots ,a_n$ and $b$ such that the zero-one solutions of the linear inequality $\sum \…