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_{\mathrm{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)\ge k$. We prove that there are constants $c_1^{\prime \prime },c_2^{\prime \prime }>0$ such that $c_1^{\prime \prime }n/(\log n)<f_{\min }(G)<c_2^{\prime \prime }n/(\log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.