1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Showing the Kneser graph is vertex transitive

  1. Nov 6, 2009 #1
    1. The problem statement, all variables and given/known data
    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

    2. Relevant 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

    3. 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, im 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
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted