Kneser ranks of random graphs and minimum difference representations

A k-min-difference representation of a graph G is an assignment of a set Ai to each vertex i∈V(G) such that ij∈E(G)⇔min⁡{|Ai\Aj|,|Aj\Ai|}≥k. The smallest k such that there exists a k-min-difference representation of G is denoted by fmin(G). Balogh and Prince proved in 2009 that for every k there is a graph G with fmin(G)≥k. We prove that there are constants c1″,c2″>0 such that c1″n/(log⁡n)