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 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>