A binary bipartite graph - reference request - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:24:23Z http://mathoverflow.net/feeds/question/59164 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59164/a-binary-bipartite-graph-reference-request A binary bipartite graph - reference request Seva 2011-03-22T10:32:48Z 2011-03-23T10:25:01Z <p>Consider the bipartite graph whose partite sets are two disjoint copies of <code>\$\{0,1\}^n\$</code>, with an edge joining \$u\$ and \$v\$ if and only if there is no position in which both \$u\$ and \$v\$ have \$1\$; that is, no carrying occurs if \$u\$ and \$v\$ are added as binary numbers. Up to the edge joining the two zeroes, this graph is a double cover of the graph on the vertex set <code>\$\{0,1\}^n\$</code> in which two vertices are adjacent whenever they meet the condition just mentioned.</p> <p>The graph just described has <code>\$2^{n+1}\$</code> vertices and <code>\$3^n\$</code> edges; for \$n=1\$ it is just the path of length \$4\$.</p> <p>My question is: Has this graph ever been studied? Does it have a name?</p> <hr> <h2>EDIT</h2> <p>Addressing Zsbán's (highly relevant) remark, here is, essentially, a re-statement of my question. </p> <p>The <em>Kneser graph</em> \$KG_{n,k}\$ is the graph whose vertices are the \$k\$-element subsets of a fixed \$n\$-element set, with two vertices adjacent whenever the corresponding subsets are disjoint. What if we consider instead the graph whose vertices are <strong>all</strong> subsets of our \$n\$-element set (and the adjacency condition is left intact)? Has this graph been studied? Does it have a name?</p>