The Graph of the Hypersimplex

Details The Graph of the Hypersimplex The Graph of the Hypersimplex

2008-11-18

arxiv.org/abs/0811.2981v1

Mathematics

Combinatorics

8 pages

Scientific paper

The (k,d)-hypersimplex is a (d-1)-dimensional polytope whose vertices are the (0,1)-vectors that sum to k. When k=1, we get a simplex whose graph is the complete graph with d vertices. Here we show how many of the well known graph parameters and attributes of the complete graph extend to a more general case. In particular we obtain explicit formulas in terms of d and k for the number of vertices, vertex degree, number of edges and the diameter. We show that the graphs are vertex transitive, hamilton connected, obtain the clique number and show how the graphs can be decomposed into self-similar subgraphs. The paper concludes with a discussion of the edge expansion rate of the graph of a (k,d)-hypersimplex which we show is at least d/2, and how this graph can be used to generate a random subset of {1,2,3,...,d} with k elements.

Affiliated with

Also associated with

No associations

Rating

The Graph of the Hypersimplex does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Graph of the Hypersimplex, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Graph of the Hypersimplex will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-428692