The golden ratio, Fibonacci numbers, and independent sets in graphs

Mathematics was once again in the news recently, when a high school student Joseph Rosenfield discovered an error in the expression for the golden ratio in the Museum of Science in Boston. This is the photo that Joseph took in the museum:


The “error” was the negative sign in the expression of the golden ratio. In fact, this is not an error, but just the multiplicative inverse of what is usually referred to as the golden ratio. Note the exhibit correctly refers to this number as capital Phi, which is 0.618…, rather than lower case phi, which is 1.618…

Error or not, the teen’s story went viral, and he should be commended for his willingness to question authority. All mathematicians are secretly rebels!

The golden ratio plays an interesting role in Mathematics and nature, arising in painting, architecture, geometry, and patterns in nature (ranging from sea shells to sunflowers). It is akin to other important constants such as pi or e, but not as highly popularized in a typical mathematical education. Kepler noticed that the golden ratio appears naturally when considering Fibonacci numbers, which are formed by adding the previous two numbers in the sequence (starting with 0 and 1):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Fibonacci numbers have a closed form expression in terms of powers of the golden ratio, and are nice doorway to research in combinatorics and number theory.

My own interest in Fibonacci numbers comes from the study of the number of independent sets in graphs. A set of vertices in a graph is independent if it contains no edges. A fun exercise is that in the path with n vertices, the number of independent sets (counting the empty set) is (n+2)th Fibonacci number. The Fibonacci number of a graph G is the number of independent sets in G.

With my collaborators, we investigated independence densities of graphs, which are the ratios of the Fibonacci number of a graph to its total number of subsets. By using chains of finite sets of vertices, one can define the independence density of countably infinite graphs, and by simple properties one can show this limiting density always exists and is independent of the chain.  To our surprise, we proved that independence densities are always rational in a strong sense.  We generalized this in a subsequent work to independence densities of hypergraphs.

 Anthony Bonato

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s