Title: Kneser ranks of random graphs and minimum difference representations,
Abstract: 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 that $A_u$ and $A_v$ are disjoint if and only if $uv\in
E$. The smallest such $k$ is called the Kneser rank of $G$ and denoted by
$f_{\rm Kneser}(G)$. As an application of a result of Frieze and Reed
concerning the clique cover number of random graphs we show that for constant
$0< p< 1$ there exist constants $c_i=c_i(p)>0$, $i=1,2$ such that with high
probability \[ c_1 n/(\log n)< f_{\rm Kneser}(G) < c_2 n/(\log n). \] We apply
this for other graph representations defined by Boros, Gurvich and Meshulam. A
{\em $k$-min-difference representation} of a graph $G$ is an assignment of a
set $A_i$ to each vertex $i\in V(G)$ such that \[ ij\in E(G) \,\,
\Leftrightarrow \, \, \min \{|A_i\setminus A_j|,|A_j\setminus A_i| \}\geq k. \]
The smallest $k$ such that there exists a $k$-min-difference representation of
$G$ is denoted by $f_{\min}(G)$. Balogh and Prince proved in 2009 that for
every $k$ there is a graph $G$ with $f_{\min}(G)\geq k$. We prove that there
are constants $c''_1, c''_2>0$ such that $c''_1 n/(\log n)< f_{\min}(G) <
c''_2n/(\log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.