Kneser ranks of random graphs and minimum difference representations

Zoltán Füredi, Ida Kantor

Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v\mapsto A_v$ to the vertices $v\in V$ such tha…