Timeline for Is the following graph well known?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2010 at 22:22 | comment | added | Vaughn Climenhaga | It doesn't look to me as though any value of s makes the generalised Kneser graph fit Tyson's criteria. They fail on two counts: (1) the vertex sets should be ordered tuples, not subsets, as already observed, and (2) the adjacency criterion would need to be specify the size of the intersection exactly (as $k-1$) rather than merely giving an upper bound ($\leq s$). | |
| Dec 15, 2010 at 19:51 | comment | added | Tyson Williams | Yes, I read that. Are you saying that the graph I described and the Kneser graph have the same number of vertices? | |
| Dec 15, 2010 at 19:48 | comment | added | Igor Rivin | The below is a paste from the wikipedia article: The generalized Kneser graph KGn,k,s has the same vertex set as the Kneser graph KGn,k, but connects two vertices whenever they correspond to sets that intersect in s or fewer items (Denley 1997). Thus KGn,k,0 = KGn,k. | |
| Dec 15, 2010 at 19:42 | comment | added | Tyson Williams | Are you sure? The graph the I am looking for has n!/(n-k)! vertices, but the Kneser graph (and its generalization) have (n choose k). | |
| Dec 15, 2010 at 19:31 | history | answered | Igor Rivin | CC BY-SA 2.5 |