I just added an article on Fibonacci cubes to Wikipedia. As the first sentence states, these are graphs that resemble hypercubes but have a Fibonacci number of vertices. Their vertices can be labeled by bitstrings that have no two consecutive one-bits in them, and two vertices are adjacent when their labels differ by one bit.

Something I didn't put in the article, because I didn't find it in any of the published papers I found on these graphs: the Fibonacci cube is the graph of a distributive lattice. If x and y are bitstrings in the Fibonacci cube, the join of x and y can be found by taking their bitwise or in even positions of the bitstring and their bitwise and in odd positions. The meet is the reverse operation, taking the bitwise and in even positions and the bitwise or in odd positions. The top element of the lattice has all ones in the even positions, and the bottom element of the lattice has all ones in the odd positions. And x ≤ y in the lattice ordering if x has a 1 in every odd position that y does and a 0 in every even position that y does.

By Birkhoff's representation theorem, this lattice comes from a partial order. This partial order appears to consist of the bitstrings that (1) have a 1 in an even position, and 1's in all nonadjacent odd positions, or (2) have a 0 in an odd position, and 1's in all other odd positions. Its Hasse diagram is a zigzag path:

10010101    00100101    01001001    01010010
       \     /     \     /     \     /     \
      00010101    01000101    01010001    01010100

It's easy to see from this picture that the number of lower sets in the partial order, and therefore the number of elements of the distributive lattice, satisfies the Fibonacci recurrence: the lower sets that include the final element of the zigzag are defined by a zigzag with one fewer element, and the lower sets that don't include it also don't include the element above it and are defined by a zigzag with two fewer elements.

ETA: Stanley has an article on “The Fibonacci Lattice” in a 1975 Fibonacci Quarterly paper. I was hoping it was the same lattice, since he's defining lattices from posets via Birkhoff and he gets a lattice with a Fibonacci number of elements. But it's not the same poset so it's not the same lattice. I've renamed the title of this post to avoid confusion with his paper.

ETA2: In arXiv:math.CO/9801066 Jim Propp mentions the lattice of independent sets of a bipartite graph. The zigzag lattice is what you get when you apply this construction to a path graph. In general the poset underlying Propp's lattice is formed by directing the edges of the bipartite graph from one side of the bipartition to the other, which in the case of a path graph results in the zigzag poset.

ETA3: It is Stanley after all. Enumerative Combinatorics, exercise 3.23.




Comments:

brooksmoses:
2009-02-20T19:12:05Z
On a different note but one I thought you might be interested in, I just came across this press release about a paper on an efficient algorithm for counting ways to color nodes in a graph. I'd be interested if you could comment on whether it's really as remarkable a discovery as the glowing words in the press release imply.
11011110:
2009-02-20T22:32:44Z
It's a new exponential algorithm for a problem that previously was solved in exponential time and is unlikely to be solved more quickly than exponential, computing the chromatic polynomial of a graph. What I can't tell from the writeup is whether it's an asymptotic improvement on previously known algorithms for the same problem or whether it's only a practical improvement on the strawman brute force algorithm they used to test it against. The Wikipedia article on the Tutte polynomial (a generalization of the chromatic polynomial that can be used to compute chromatic polynomials) says, of the deletion-contraction method that they compare themselves against, “In practice, branch and bound strategies and graph isomorphism rejection are employed to avoid some recursive calls. This approach works well for graphs that are quite sparse and exhibit many symmetries.” It's not clear whether they used these strategies in their comparison.
None:
2009-02-23T01:32:06Z
it wouldn't be the first time: http://everything2.com/node/1262632
11011110:
2009-02-23T01:39:19Z
Fascinating, in a watching-the-trainwreck sort of way. But of course physicists do not have a monopoly on bad reinventions of the wheel.
None: Great one!
2009-02-26T00:52:24Z
I came across this blog while searching for something completely different, but I have to say, I'm impressed. I'll definetely subscribe to the RSS feed.