Showing the Kneser graph is vertex transitive

[a1010711]

Homework Statement

the kneser graph KG(n:k) is the graph whose vertices are all of the k-subsets of {1,2,...,n} with 2 vertices beign adjacent if they are disjoint.

show KG(n:k) is vertex transitive

Homework Equations

a graph G is vertex transitive if for any 2 vertices x,y in G, there is an automorphism f:X-->Y st f(x)=y

The Attempt at a Solution

i know the aut exists, but how do i show its bijective?

if i find the aut i can show that a permutation does exist so that f(x)= y
so f(x1,...,xk) = (y1,...,yn)

let my permutation be Z that map all the x's to all the y's

Z (x1...xk others not x )
(y1...yk others not y)

please guide me through this, I am confused..

i also need to show its arc transitive:
so for ex given any 2 pairs of vertices (say u1,v1 u2,v2) there is an aut f:v(g)-->v(g) such that f(u1)=u2 and f(v1)=u2

 

[mighty2000]

To show that a graph is vertex transitive, we need to show that for any two vertices x and y, there exists an automorphism f that maps x to y. In this case, we can define our automorphism f as follows:

Let x = {x1, x2, ..., xk} and y = {y1, y2, ..., yk} be two vertices in KG(n:k). We can define f as a permutation that maps each element in x to the corresponding element in y. In other words, f(x1) = y1, f(x2) = y2, ..., f(xk) = yk.

To show that this is a bijective mapping, we can note that since x and y are both k-subsets of {1, 2, ..., n}, they both have the same number of elements (k). Therefore, each element in x will be mapped to a unique element in y, and vice versa. This shows that f is a bijection, and thus an automorphism.

To show that KG(n:k) is arc transitive, we need to show that for any two pairs of vertices (u1, v1) and (u2, v2), there exists an automorphism f that maps (u1, v1) to (u2, v2). We can use a similar approach as above, defining f as a permutation that maps each element in u1 to the corresponding element in u2, and each element in v1 to the corresponding element in v2. This will again be a bijection, showing that KG(n:k) is also arc transitive.