Kneser ranks of random graphs and minimum difference representations

Füredi, Zoltán and Kántor, Ida (2017) Kneser ranks of random graphs and minimum difference representations. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 61. pp. 499-503. ISSN 1571-0653

Preview

Text 1701.08292v1.pdf Download (425kB) | Preview

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↦Av to the vertices v∈V such that Au and Av are disjoint if and only if uv∈E. The smallest such k is called the Kneser rank of G and denoted by fKneser(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 ci=ci(p)>0, i=1,2 such that with high probability c1n/(log⁡n)<fKneser(G)<c2n/(log⁡n). We apply this to other graph representations defined by Boros, Gurvich and Meshulam. 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)<fmin(G)<c2 ″n/(log⁡n) holds for almost all bipartite graphs G on n+n vertices. © 2017

Actions (login required)

Edit Item