Tag Archives: combinatorics

Phylogenetic trees

2 Aug

I just listened to a two hour talk on phylogenetic trees, and they seem fun enough that I thought I’d share them with you!  Sorry I literally forgot to post last week, and then I realized I did not take notes on the stuff I wanted to post about (more pictures by Aaron Fenyes)- here’s a photo that I took and wanted to explain:

20160719_114650

Something twisted representation something skein algebra something unit tangent bundle

Instead, you’ll read about the basics behind the research of my friend Gillian (no website), which is being supported somehow by people who want to know about cancer.  First, some background: the field of study of phylogenetic trees is inspired by and informs applications in evolutionary biology.  All of the life-forms today (or at some slice of time) all trace back to a root life-form at time 0.  Each current life-form follows a series of branching away from the root to get to where it is now

Then we can represent this evolution via a labeled rooted binary tree: the root represents the root life-form at time 0, and each branching of the tree represents a different evolution.  The labels mark which life-form is which.  Of course this model isn’t perfect (I can’t find the word for it but it’s a thing where two different species evolve separately from the same ancestor, then meet again and make one species.  If we were to represent this information in a graph, it’d make a cycle and not be a tree), but it’s been fruitful.

Spindle_diagram

The rooted binary tree of the wikipedia picture: node 0 is the root life-form, then 1-7 are the life-forms at our current time.

Now let’s mathify this.  We’d like to encode the evolutionary information into our tree.  We’ve already decided that all life-forms will end at the same time (now), so if we just assign lengths to each of the non-leaf edges this will automatically determine the lengths of the leaf edges.  A leaf in a tree is a vertex with only one neighbor, and we call the edge leading to that vertex a leaf-edge.  Let’s call the non-leaf edges interior edges.  In the picture above, we have 5 non-leaf edges, which determine a tree with 7 leaves.  Using this exact configuration of labels and edges, we have five degrees of freedom: we can make those interior edges whatever lengths we want, as long as they are positive numbers.  So in math-terms, the set of phylogenetic trees (aka rooted, binary, labeled trees) in this configuration forms a positive orthant of \mathbb{R}^5.  You can smoothly change any one of the edges to a slightly longer or shorter length, and still have a phylogenetic tree with the same combinatorial data.

octant

This is from the paper I’m writing, but it does show that in 3D, there are 8 orthants cut by the three axes (red dot is the origin).  The pink box represents a single orthant.

What about phylogenetic trees with different combinatorial data?  Say, with different labels or different branching, but the same number of leaves and the same number of interior edges?  First we need to figure out what we mean by ‘different’.  For instance, the following picture from the seminal paper in this field shows three trees that don’t immediately look the same, but we don’t count as different:

Why aren’t they different?  Because they encode the same data for each life-form: reading from node 0 we see that first 1 branches off, then 2, then 3 and 4 in all three cases.  There’s some combinatorics here with partitions that you can do (one can label a tree with a set of partitions).  However, changing the labels so that first 2 branches off, then 1, then 3 and 4 will be a different phylogenetic tree.  In fact I can smoothly go from one to the other in the space that we’re creating: first I shrink the length of the green edge below to zero, which takes us to the middle tree (not binary!), and then extend the blue edge.

axis

Shrink the colored edges to get the same tree in the middle (not a binary tree)

We’re going to add these non-binary trees with one less edge length to our space.  Remember the tree on the left has an entire positive orthant, and the tree on the right has an entire positive orthant.  Shrinking the green length to zero means that we’re moving to one side of the left orthant: so we add this axis to our space (we have \{x,y\in \mathbb{R}^2: \ x,y\geq 0\} instead of strictly greater than 0).  We can glue the green and blue orthants together along this axis.  Here’s a picture from the paper:

spacetrees

Notice that they also have the origin filled in, with a tree with no interior edges.  This is the cone point of this space.  Now we’re finally ready to describe the space of phylogenetic trees: within each combinatorial structure/labeling, we have a Euclidean orthant in (n-2) dimensions.  Then these orthants are glued together along their axes in a specific way, and all of them are connected to the cone point.  This is called BHV(n), short for Billera-Holmes-Vogtmann space (in the paper they call it T(n) but that’s confusing to everyone else).  Here’s the picture of T(4):

t4

Each triangle represents an infinite orthant

There are 15 different orthants glued together in this picture, because the number of labelled rooted binary trees on n vertices is (2n-3)!!.  The double !! means you only multiply the odds, a.k.a. (2n-3)(2n-5)(2n-7)… This is also known as Schroeder’s fourth problem , which as far as I can tell was open for 100 years.  Pretty cool!

If you truncate BHV(n) so it’s not infinite (just pick some compact bound), then it forms a nonpositively curved cube complex, and we love those!  CAT(0) cube complexes are great.  I haven’t blogged too much about them (first terrible post and then those truncated Haglund notes) but they are the basis of all that I do and the number one thing I talk about when I give math talks.  Whoops!  The gist is that you glue cubes together in not-terrible ways, and then the resulting complex has great and fun properties (like you can cut it in half the way you want to).

That’s about all I have to say about this!  Gillian is working on some stuff about putting a probability measure on BHV(n) [you can’t do it with certain conditions], embedding it into a small enough Euclidean space that still preserves some of its features, and finding an isometrically embedded copy of the phylogenetic tree inside BHV(n) instead of just the coordinate point.  Also, fun fact to prove to yourself (actually please don’t scoop my friend), find the automorphism group of BHV(n)!  It’s just the symmetric group on some number that has to do with n (n+1 or something like that; I can’t remember and didn’t take notes).

Again, the main reference for this is the seminal paper that should also be accessible as it’s meant for biologists and statisticians.

Advertisement

Tags: , ,

Counting like Gauss, Part II

24 May

If you missed Part I, which introduces our problem, click here to read last week’s post.

Here are some pictures from last week:

level setsoctahedron

The picture on the left describes technique 1, which we did last time to count how many points are in an octahedron with vertices at (0,0,n), (0,0,-n), (0,n,0),(0,-n,0), (n,0,0), and (-n,0,0).  The edges of the octahedron are lines between vertices that live in the same octant, and the faces live in each octant (so there are eight faces).  Now we’ll do Technique 2: counting the points in each octahedral shell, which is also called the spherical number.

Let’s look at just the yz plane, that is, where x=0.  So we want the integer points in the yz plane that lie on the n-shell of the octahedron.  Let’s stop and think about what we said in the last paragraph: there are eight faces because there are eight identical octants.  What if we count up all the points in one octant, then multiply by 8, and subtract any points we double counted?  Sounds great to me!  Let’s now just focus on when x, y, and z are all greater than or equal to 0.

tech2

Octahedron, x=0 plane, one quadrant, view of that quadrant

So now we have these points on a line such that x=0, and the line runs between (0,n,0) and (0,0,n).  Well thanks to point-slope formula, or slope-intercept form, or however you want to write your equation, we know that these points satisfy the equation of the line: y+z=n.  How many ways can I cut up n into two numbers y and z such that both are at least 1?  (I’m going to say they both have to be at least one because the vertices (0,n,0) and (0,0,n) will be special in the next paragraph).  Well if I choose y, that automatically chooses z.  I have n-1 choices for y (they are {1,…,n-1}), so that means I have exactly n-1 ways to choose y and z.  Then there are n-1 points on the line.  I can either count and see I have 12 edges in my octahedron, so insides of edges contribute 12n-12 to the total count, or I can see I have three edges in my positive octant, multiply by 8 (because we have eight octants), and then divide by two since each edge lies in two octants.  Either way, we contribute 12n-12 to the final count.

By the same logic, I have exactly three vertices in my positive octant, each of which appears in 4 neighboring quadrants.  These contribute 6 to the final count (3*8/4=6 if we do the double counting method, or again we can just look at how many vertices are in an octahedron).

Now I’ve counted the edges and vertices in my octahedral shell, so I only need to figure out how many points lie inside the triangular face.  Again I can write an equation for the face: x+y+z=n.  Then I need to figure out how many ways I can partition n balls into three boxes, each with at least ball inside.  This is a partition problem.

trime

We’ve counted the outside, now we need to find the number of integer points inside the triangle.

Let’s try to tackle this the way we did the last one.  But maybe let’s use an example, like the number 6.  How many ways can I cut up 6?  Well, I can choose 3 for x, which leaves 3 leftover to split into two numbers y and z.  From above I know there are 3-1 ways to choose, which I know since I can pick 2,1 or 1,2 for y and z.  I can also choose 4 for x, which leaves 2 leftover, or 2 for x, which leaves 4 leftover, or 1 for x.  Let’s organize this into a table.

table

I’ve considered investing in a mouse, but haven’t quite bitten the bullet yet

Notice then that the number of ways I have to partition 6 into three bins, each of which has value at least 1, is 1+2+3+4.  This logic generalizes: I can pick any number from 1 to n-2 for x, and each of those options gives me n-x leftover to split into y and z, and from above that’s n-x-1 such options.  So I have \sum_{x=1}^{n-2} n-x-1=\sum_{x=1}^{n-2} x.  Thanks to nine-year-old Gauss via fable, I know how to sum up the numbers from 1 to k: it’s a formula, 1+\ldots+k=\frac{(k+1)(k)}{2}.  There’s a bunch of ways to explain this formula, here’s an easy to read collection.  So if I apply this formula to my sum, I have \frac{(n-1)(n-2)}{2}.  This is all the points inside the face that lie completely in the octant, so if I multiply this by 8 I have contributed 4(n-1)(n-2) points.

Then in the octahedral shell, I can add up all the contributions and get 6+12n-12+4(n-1)(n-2), which simplifies to 4n^2+2.

We actually want to count all the lattice points inside an octahedron.  The octahedron is a bit special, since any lattice point inside it will lie on one of these octahedral shells, like a bunch of nesting Russian dolls.  So now I need to do 1+ \sum_{k=1}^n (4k^2+2), where I added the 1 at the beginning to represent the single point (0,0,0).  Luckily I also have a formula for the sum of squares, though without fun folklore to go with it.  The formula is \sum_1^n k^2 = \frac{n(n+1)(2n+1)}{6}.  Plugging that into my formula, I have the number of points in the octahedron is 1+4(\frac{n(n+1)(2n+1)}{6})+2n = \frac{4}{3}n^3+2n^2+\frac{8}{3}n+1, which is EXACTLY WHAT WE GOT LAST WEEK!!!!

I hope this was as exciting for you as it was for me.  My friend Jeremy Kun and an anonymous number theorist commented last week about the Gauss Circle Problem and the error terms in it.  I just wanted to add that Gauss offered up the problem and the error guess, and it took 100 years until Sierpinski came up with a proof for something not that close to the error guess, and now it’s been like 200 years and we don’t quite have a proof for what we think the answer is yet.  Rumor has it that several years ago someone posted a proof to the arXiv, then quietly withdrew it.

Partner has pointed out that there’s a wikipedia entry for this problem but it doesn’t go into as much depth or have as cute pictures as my two blog posts.

Tags:

Counting points is fun! Gauss did it, why can’t we?

17 May

I’m writing to you from the Institute for Advanced Study (!!!! Starstruck!!!!  Einstein!  1930!  More importantly, Noether!)  I’m in the middle of a two week program  that’s been going on since 1994 for women and mathematics, and I wanted to share with you an easy-to-state, hard to solve combinatorics problem.

First, some two dimensional background and set up.  The Gauss Circle Problem has been around for a looong time (200+ years) and is not actually solved.  Let’s live in the xy plane, and mark points where x and y are integers in the plane.  We get a lattice of points:

integerlattice

Why didn’t I fill them all out?  Lattice find out!

The Gauss circle problem asks: if I make a circle with radius n centered at the origin, how many lattice points are inside that circle?  We can count the first few:

firstfourcircles

There’s four points on the pink circle and one point inside, so G(1)=5.  The orange circle has four points on it, and it also adds the four points between the pink and orange circles.  So G(2)=4+4+5=13.  And the beige circle has eight points on it, and also adds more inside points, so G(3)=29.  Gauss thought that G(n)=\pi n^2+ O(n).  We haven’t talked about this big O notation (it’s literally called big O notation; we’re very creative nomenclators), and I’m not going to do so here: take it as an “error term up to linearity”.  That means that while G(273) is around 74529π, it’s off by a factor that’s not “too far” from 273, a.k.a. probably closer to 273 than to 74529.

How do you count G(3)?  One way you can do it is count G(2), then count all the added points, like we did above.  You can also find a smaller region to look at, then multiply to fill in the circle and subtract double counted points.  In the example above, let’s just look at one quadrant.

quadrant

I picked the northeast quadrant because that’s where I am!

It’s pretty easy to see how many points are in there: I count 11 integer lattice points.  Now we multiply by 4 to get 44 lattice points.  But we double counted!  Imagine multiplication by two as picking up that pie slice, and rotating it, and putting it back down in the tin in the northwest corner.  I’ve overlapped the first slice by one edge, so if I want to count the number of lattice points I’ll have to subtract the four points on that edge from my total.  Similarly, multiplying by four double counts all of the edge points on the green lines, and counts the origin four times.  So I need to subtract 3 for the quadruple counted origin, and 12 for the double counted edges: that leaves 44-15=29, which is good because it’s what I had above!

For the next problem, we’re going to use a black box called Pick’s Theorem.  It’s not an extremely dark black box since there’s a proof of it on that wikipedia page, but I’m not going to explain the proof here, just say the statement: If you have a polygon with integer coordinates in the plane, then A=i+b/2-1, where A is the area of the polygon, i is the number of lattice points inside the polygon, and b is the number of lattice points on the boundary of the polygon.  Notice this works for polygons, not circles (circles is the Gauss circle problem, still unsolved).

If I let A, i, and b represent what they do for my initial polygon, I can write a formula for the number of lattice points after I scale the first polygon by n: G_P(n)=i_n+b_n=A_n+\frac{b_n}{2}+1 by Pick’s theorem.  Since A stands for area and I’m scaling linearly by a factor of n, A_n=n^2a.  Similarly, b stands for boundary which is a linear factor, so b_n=nb.  Plugging these both in to the original equation gives G_P(n)=n^2A+\frac{nb}{2}+1, which is great!  You only need to find A and b for the first polygon to find the number of lattice points in any scaling of it.

triangles

Applying Pick’s theorem to right triangles aka the triangle numbers

So here’s the next problem: Find G(n) for an octahedron in three dimensions (we’ve run into the octahedron in the poincare homology sphere posts).  For a recap, the octahedron is what happens when you draw vertices at (0,0,n), (0,n,0), (n, 0,0), (-n,0,0), (0,-n,0), (0,0,-n) and draw the edges between them and then fill it in.

 

octahedron

Octahedron from wikipedia page, link above.

So now it’s a little harder and weirder to count, but we can still do it, using a mixture of the techniques above.  I’ll show two different ways to count this.

octohagon

Because it’s messy I only drew the dots on the axes

Technique 1: use level sets!  My friend and co-author Andrew Sanchez came up with this clever idea, which uses the theorem we have above.  Imagine that we’re at the top of the octohedron, at point (0,0,n), and we start taking an elevator down the z-axis.  At the very top we see exactly one point.  At the next level, we see four points: (1,0,n-1), (0,1,n-1), and the same points with -1s instead of 1s.  At the next level we see a diamond: fixing z at n-2, we have a diamond between points (0,2),(2,0),(0,-2),and (-2,0).

level sets

Imagine the thin black line is the z axis, and we’re moving down it through the centers of these sets.

This is exactly G_D(k) where D is the diamond!  So from the formula above, we can calculate G_D(k)=2k^2+2k+1, by find the initial area (2) and number of boundary points (4) of the initial diamond.

Now we’ll need to add all of these points from all of the level sets.  The elevator starts with one point, which corresponds to z=n and k=0, and in the fattest part of the octahedron we have z=0 and k=n.  Then it gets skinny again.  So we can count all the points from z=0 to z=n, multiply by two, and subtract what we double counted (the fat base).  This shows up as follows: 2[\sum_{k=0}^n (2k^2+2k+1)] - (2n^2+2n+1).  There are a bunch of proofs that \sum_{k=0}^n k^2= \frac{n(n+1)(2n+1)}{6} and that the sum of the first n numbers is \frac{n(n+1)}{2}.  So if I go through the arithmetic (you can do it I believe in you!) I get \frac{4}{3}n^3+2n^2+\frac{8}{3}n+1.

Do you believe it?  Let’s do a second technique too!  Actually, hate to leave you on a cliffhanger, but a second technique will take a lot more words and this post is already long enough.  So you’ll have to wait til next week to see the technique I used with my friend Priyam Patel, whose current research I have previously blogged.  Preview: we use partitions!

Tags:

Combinatorics fun with complexes

5 Apr

Last weekend I spoke at the Graduate Student Combinatorics Conference in Clemson, in one of those parallel sessions, so there were two other speakers slotted for the same 25 minute slot.  But those two didn’t show up, so I ended up being a “plenary speaker”!  Everyone came to my talk, which is funny because I’m in geometric group theory, not combinatorics.  But I got a lot of compliments afterward even though I only got through 2/3 of the prepared material (oops that’s what happens when you don’t practice/finish the talk 2 hours before showtime).  Related: I don’t think this is humblebragging, I believe in real bragging- you’re awesome, shouldn’t you tell people about it?

Anyways, I enjoyed the first graduate talk I saw, by a grad student at KU named Bennet Goeckner [I still am not sure about etiquette for blogging but I think I’ll start using peoples’ names instead of just linking to their websites.  If they get mad at me for google hits then I’ll go back to just links.]  It was based on a paper he coauthored with three professors, so I thought I’d tell you a bit about it.

I didn’t know anything about combinatorics before going to this conference.  Like, I didn’t even know it was a field of study, despite posting about an open problem in it almost exactly two years ago.  So I was very happy that in this first talk he defined an abstract simplicial complex, which is a basic object of study in combinatorics (at least, it came up in a ton of later talks).  This is a subset D of the set of subsets of {1, 2, 3,…, n} that follows a rule: if a is in D, and b is a subset of a, then b is also in D.  Example: if the set {1,2,3} is in D, then that means all of these sets are in D too: {1},{2},{3},{1,2},{2,3},{1,3}.  Here’s why we call it simplicial: you can see all of this information if you draw a triangle (a.k.a. a 2-simplex)!

simplex

Big picture of triangle contains all the info on the right (+smile!)

Might as well be thorough: the set of subsets is called the power set, so the power set of {1,2,3} is what we listed above, plus the entire set and the empty set.  Note that in our example, we have 8 sets in the power set of a 3-element set.  This is not a coincidence!  In general, a power set will have 2^n elements, if the original set had n elements.

Also, a n-simplex is the convex hull of (n+1) points in n space: so 3 points in 2 space makes a triangle.  4 points in 3 space makes a tetrahedron, a.k.a. a 3-simplex.  5 points in 4 space makes a 4-simplex.

nsimplices

0,1,2, and 3-simplices

So whenever you have abstract objects that satisfy the simplicial condition, you can build an abstract simplicial complex out of them.

Here’s an example from the talk: X=<1 2 3, 2 3 4>.  Convince yourself that this is two triangles glued together along an edge labeled by 2 and 3.  We can build a lattice that encodes the subset information in a different way then the triangles picture.  I also love this example because the lattice looks like a heart, and I ❤ lattices!

heartlattice

Red lines indicate that the bottom set is contained as a subset in the top set

We say a simplicial complex is partitionable if you can cut it up into Boolean intervals that end in the top layer (but start at some layer).  The picture shows you the partitioning, and you can kind of tell by looking what a Boolean interval is (it describes the skeleton of a n-cube for some n).

partitioned.png

This simplicial complex was partitionable… but my heart isn’t (it belongs to GGT)

It’s a little hard to show that things aren’t partitionable.  Here’s an example that probably showed up in the talk but I didn’t write it down: Y= <1 2 3, 3 4 5>.

bowtie.png

Simplex and lattice, plus a happy person wearing a bowtie!

If we make one of the partitions that contains the bottom empty set and one of the top sets, we can’t make the rest into partitions that start at the top.

parting

No way to partition remaining 5 sets

Their paper answers a conjecture from 1979, which asked if all Cohen-Macaulay simplicial complexes are partitionable (Cohen-Macaulay has something to do with homology, which we haven’t done here but my friend Jeremy has a mathy post about it).  They said haha no!  They took a counterexample in something else, called Ziegler’s Ball, chopped it up a little bit, glued a bunch of copies of it to itself, and built something surprisingly nice (with 16 vertices) that is not partitionable.  This has applications in commutative algebra, besides being a fun combinatorial thing.  The paper is relatively short and approachable if you’re a grad student looking for something fun to read, and they ask three questions for further research at the end!

Tags: ,

Open problem in combinatorics: tiling a floor (no background

25 Apr

As I mentioned a few weeks ago, I recently went to the second annual Midwest Women in Mathematics Symposium (yay!  My baby conference is now a toddler!)  The organizers added a problem session to the program, which ended up being super cool- each presenter had five minutes or so to present an open question that needed answering.  The idea was to search for nearby collaborators, which is such a cool way of doing it!  I loved a bunch of them, so thought I’d write up one.

This presentation was by Pamela Harris, an assistant professor at West Point.  We also need NO BACKGROUND for it, which is awesome!  All of these notes are derived from her 5 minute presentation + wikipedia searches.

Let’s say for example that we have a rectangular floor, say one foot by three feet.  We have a bunch of tiles of size 1×1, 1×2, 1×3.  The question is, how many different ways do we have to tile the floor?  A second question might be, how many different ways are there using 2 tiles?

How many ways to tile this floor using these colored tiles?

How many ways to tile this floor using these colored tiles?

This question is pretty straightforward with a 1×3 floor: I drew all the possibilities below.

I don't know why the red tiles are so unhappy

I don’t know why the red tiles are so unhappy

Notice that in answer to our second question, there’s one way to use 3 tiles, two ways to use 2 tiles, and one way to use 1 tile.  We can encode this information in a polynomial using, say, q as a variable.  In our polynomial, we’ll have the coefficients of q^k representing the number of ways to tile using k tiles.  So to represent the configurations in our picture above, we have 1q + 2q^2 + 1q^3 = q(1+2q+q^2) = q(1+q)^2.

We can ask ourselves, is there a pattern here?  Let’s try a 1×2 floor.

CHANGING THE PARADIGM- blue is happy! Green is still envious of that happiness though

CHANGING THE PARADIGM- blue is happy! Green is still envious of that happiness though

Doing the same procedure as above, we get this polynomial: 1q + 1q^2 = q(1+q).

You can work out for yourself what happens with a 1×4 floor.  If you use some combinatorial thought (I’ll give an example below), you end up with any 1xr floor gets a polynomial of q(1+q)^{r-1}.

I haven’t thought about this problem before starting to type this, so you can have some insight into my mind right now!  Let’s try to figure out what happens when we go from a 1×2 tiling to a 1×3 tiling.  We still have the same tiles as in 1×2, but adding a red single square to them (this gives the first two configurations in our red-orange-yellow picture).  We can also add a red single square to the left side of the green picture, giving the third configuration.  Finally, we have the big 1×3 tile, which didn’t exist in the 1×2 world.

In fact, when we go from 1xn land to 1x(n+1) land, the only tiling that uses a tile not seen in 1xn is the last one, which consists of one big 1x(n+1) tile.  This adds a single q term to our polynomial (because we only used one tile).  In fact, there’s only ever one q term in any polynomial, because there’s only one big fat tile that can do it.  Similarly, there’s only every one q^{n+1} term.

We need to figure out the coefficient for q^k in the (n+1)^{th} polynomial, and based on our 1×2 to 1×3 analysis, it should be related to the coefficient for q^k in the n^{th} polynomial.  Let’s label these so we don’t have to keep writing it all out:

G(n+1,k) will be the coefficient for q^k in the (n+1)^{th} polynomial, and G(n,k) will be the same for the nth polynomial.

Claim: G(n+1,k) = G(n,k) + G(n,k-1).

Proof: Up to you!  All the thoughts from above should help out.  This is apparently a common exercise in combinatorics classes.  If I get requests I’ll put up a proof at a later post.

This recursive formula tells us exactly what the explicit formula should be, because it’s the formula for Pascal’s triangle.

From wikipedia- Pascal’s triangle

Each entry in the triangle is formed by adding the two entries above it.  If you number the entries by (row, place in line), you’ll get our exact formula G(n+1,k) = G(n,k) + G(n,k-1).  We can read off what the polynomials should be: for a 1×6 tiling, my polynomial will be q+5q^2+10q^3+10q^4+5q^5+q^6 = q(1+1)^5.

Good warm up!  So here’s the open problem: if you have the floor in the picture (so a 2xn rectangle, with a 1×1 bite taken out of the bottom left corner), and the only allowable tiles are the ones in the picture, what polynomials do you get?

How do you fill me?

How do you fill me?

A rainbow of tolerance and acceptability!

A rainbow of tolerance and acceptability!

Again, the coefficients of q^k are # of ways to tile with k tiles.

I googled “tilings with rectangles” and there were a TON of papers written on this topic.  So here are some Further reading suggestions (from least mathematical-intimidation seeming to most)

This one has the word “simple” in it and lots of pictures: http://www.inference.phy.cam.ac.uk/mackay/rectangles/

This one uses those little rods we had in middle school math: http://users.humboldt.edu/phyllis/papers/c-rodpaper2.html

This has lots of pictures and numbers (numbers are good/concrete): http://www.math.ucsd.edu/~ronspubs/82_04_tiling.pdf

This is 14 different proofs of the same theorem, using integrals, graph theory, induction, polynomials… you’ll probably like at least one of them! http://www.maa.org/sites/default/files/images/upload_library/22/Ford/Wagon601-617.pdf

This one is recent research- it was published in 2012.  It has Hausdorff spaces, discrete Morse theory, and homotopy equivalence on the first page.  I might read it for funsies.  http://arxiv.org/pdf/1204.5734v2.pdf

Tags:

%d bloggers like this: