Kneser representations of graphs (2008)

Originators: Peter Hamburger, Attila Por, and Matt Walsh    (presented by Ida Svejdarová - REGS 2008)

Definitions: An (n,k)-Kneser representation of a graph G is an assignment f of distinct k-subsets of [n] to vertices of G such that u is adjacent to v if and only if f(u)∩f(v)=∅. The Kneser index &iota(G) is the minimum k such that there exists an (n,k)-Kneser representation for some n.

Motivation: We want to store graphs in a computer efficiently, in such a way that just by looking at the representations of two vertices we can tell instantly whether they are adjacent. This is one of several representation parameters of interest. For others, see for example [EIN], [LNP], or [KM].

Question 1: What are extremal values of the Kneser index on various classes of graphs?

Comments: Every graph has a Kneser representation, and in fact ι(G)≤Δ(G^c), since one can give the edges of G^c distinct labels and assign each vertex a set containing its incident labels. [HPW] contains some results about the Kneser index of paths, cycles, and hypercubes. In particular, ι(G) is known within log log log n for P_n and C_n, while ½(d-5)+¼lg(d-2)≤ι(Q_d)≤d-1.

For a general lower bound, &iota(G)>k when G has an induced matching with more than (_k^2k) edges. This bound follows easily from the Bollobás Inequality stating that if A₁,...,A_r and B₁,...,B_r are sets with |A_i|=a and |B_i|=b for all i, and A_i∩B_j=∅ if and only if i=j, then r is at most (_a^a+b).

Definitions: Let N(G,k) denote the least positive integer n such that G has a (n,k)-Kneser representation. A graph G is twin-free if no two vertices have the same (open) neighborhood.

Question 2: Let G be a twin-free graph. What is the smallest n for which there exists a k such that G has an (n,k)-Kneser representation? Is it always the same as N(G,ι(G))?

Comments: The question is when n and k can be minimized simultaneously? They cannot when G is a star, but this is not an interesting example, because the extra labels are forced only by the requirement that the representing sets be distinct. This motivates the requirement that G be twin-free. It is known that n and k can be minimized simultaneously when ι(G)=2 (see [HPW]).

References: [HPW] P. Hamburger, A. Por, M. Walsh. Kneser representation of graphs (to appear).
[EIN] A. B. Evans, G. Isaak and D. A. Narayan. Representations of graphs modulo n, Discrete Math 223 (2000) 109-123.
[LNP] L. Lovász, J. Nešetřil and A. Pultr. On a product dimension of graphs, J. Combin. Theory B 29 (1980), 47-67.
[KM] J. Korner, A. Monti. Compact representations of the intersection structure of families of finite sets, SIAM J. Discrete Math. 14(2) (2001) 181-192.