| Abstract: | Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets ({{S(v): vin V(G)}}) such that u and v are adjacent in G if and only if min{|S(u)?S(v)|, |S(v)?S(u)|} ≥ k. Define ρ min(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρ min(G)} is unbounded. In particular, we prove that for every k there is an n 0 such that for n > n 0 ‘almost all’ graphs of order n satisfy ρ min(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs. |
