Kneser ranks of random graphs and minimum difference representations

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$\mathrm{.}Thesmallestsuch$k$iscalledtheKneserrankof$G$anddenotedby$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\mathrm{/}(\log n)<f_{\mathrm{K}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{r}}(G)<c_{2}n\mathrm{/}(\log n)\mathrm{.}$$ 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)\iff \min \{\mathrm{\mid }{A}_i\setminus A_j\mathrm{\mid },\mathrm{\mid }{A}_j\setminus A_i\mathrm{\mid }\}\ge k\mathrm{.}$$ 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)\ge k$. We prove that there are constants $c_1^{\mathrm{\prime }\mathrm{\prime }},c_2^{\mathrm{\prime }\mathrm{\prime }}>0$ such that $c’‘1 n/(\log n)< f{\min}(G) < c’'_2n/(\log n)$holdsforalmostallbipartitegraphs$G$on$n+n$ vertices.