Sunday, May 30, 2010
Monday, May 24, 2010
Graphs and Donuts
I think I wrote a couple posts ago that I would post something about some stuff that I am fooling around with in a mental sense, so I will do that.
I came across a book about Topological Graph theory and since that sounded good and weird and like I wouldn't need to find a bunch of inequalities to do it, I started reading it, and came upon a problem involving planar graphs. A little explanation, though not anything rigorous:
First you have to know what a graph is. It is essentially a set of points connected by line segments. The points are called vertices, and the segments are called edges. Technically, graphs are sets which contain two sets, an edge set and a vertex set, where the vertex set is basically single numbers (generally integers), and edges are pairs of numbers, where both of the integers in the pair appear in the vertex set. But for our purposes, they are just dots with lines connecting them.
For most purposes, simple graphs will suffice, which are graphs where only one edge can appear between any two vertices, and no edge can connect a vertex to itself. If you are inclined to chemistry, you can think of them as molecule diagrams where no double bonds are allowed, but any number of bonds can be made between atoms. Actually, there is an interesting problem in graph theory of counting isomers of carbon chains of arbitrary length, but I digress.
The next thing you have to understand is what is meant by planar graphs. A planar graph is a graph that can be drawn in the plane without any edges intersecting. The analyst in my office would complain about that definition, but my tensor professor would love it because he insists that "R^2 is not a plane; a plane is a plane. R^2 is a set of pairs of numbers. What is a plane? I can't tell you, but I know what it is." That isn't an exact quote, but it is close. He also says things like, "There's no such thing as integration by parts. There is only the product rule." (^_^)
I will now give examples, like a good textbook:
This graph is K4 (the 4 is supposed to be a subscript, but blogs...). That is shorthand for the complete graph on four vertices, meaning that it has every edge that can exist on four vertices. Exercise: how many edges does Kn (the complete graph on n vertices) have?
Is K4 planar? One is tempted to say "no," since those two edges in the box intersect, and that's a no-no according to our definition. However, what if we draw it like this:
Now we have the same graph drawn in the plane, with no edges intersecting, so the answer above should actually be "yes." Technically, these graphs are not the same, they are only "isomorphic," but all that means is that if you treat graphs as they should be treated, as sets, and make a renaming function (i.e., an isomorphism) between the sets, all the relationships are preserved.
A better question is what graphs are (not) planar? A dude named Kuratowski essentially answered that question all at once and very neatly. He said (and proved) that all the non-planar graphs contain a copy of K5 or K3,3 (the bipartite graph on 3 and 3 vertices; a picture will follow). Technically, they just have to contain a subdivision of one of these two graphs. That is, if you take one of those graphs and add vertices on already established edges, you also can't draw that on the plane, but the important point is that we can tell, in a certain sense, very easily if a graph can be drawn in the plane.
K5
K3,3
The second one is called the complete bipartite graph because it has two subsets of vertices {1,2,3} and {4,5,6} that have no edges inside them, but all the other edges are there.
So, how do we know that things are planar/not planar? To show that something is planar, it's easy enough to just draw it in the plane, though in practice this could be staggeringly difficult for large graphs. To show something is non-planar, you can't just show one non-planar representation; you have to show that no planar representation is possible. Here's a bare-bones proof that K5 is non-planar, using the concept that that previous planar representation of K4 is "unique" up to bending, stretching and renaming, none of which affects planarity.
Now try putting the fifth vertex in any of the regions we've created and see if you can draw an edge to all the other vertices. So K5 isn't planar! I'll leave a proof of K3,3 up to you, but it can be done in much the same way.
Now, a mind that likes puzzles might wonder what is so special about the plane? What about other shapes, like a ball? Well, that question has been asked, but not totally answered. From now on I'm going to call "shapes" "surfaces" because that is the actual term. I'm not going to give you a real definition of a surface, but it essentially boils down to adding loops and crosscaps to the sphere.
The first part of the question is are there "planar" graphs and "non-planar" graphs for other surfaces, and the first answer is yes. In fact, some dude showed that for any surfaces, there is a finite set like {K5, K3,3} that generates all the non-embeddable graphs. However, except for the sphere, nobody knows what they are, so that is what I am messing with, but it is pretty complex. Let's consider the sphere:
There's our good buddy K4 drawn on the surface of a sphere. It shouldn't come as a surprise that anything we can embed on a plane we can embed on a sphere, since a sphere is what's called "locally Euclidean;" it looks like a plane as long as you only look in a little disk. But is that drawing still unique, as it was in the plane?
Oh, ho, ho! What if we wrap the last edge around the back? Well, it turns out that that doesn't change anything at all, because wrapping around the back is the same as stretching back and back and back. So, well, the sphere isn't too interesting. It's the same as a plane, but we like to use a sphere to judge from because it's what's called "compact." Don't worry about that much.
So what's the next simplest thing? A doughnut, or donut to normal people. Mathematicians of course call it a torus because we are contrarians by nature. Let's try drawing K4 again:
Try and draw the fifth vertex and you'll run into the same problem as before. But does this mean that K5 is non-embeddable on the torus? You should know by now that that isn't the case. What if we start by drawing the box in more natural ways?
Now try to draw that fifth vertex and you'll find that not only can you draw K5, but you can draw it in more than one way! So a donut has a little more freedom than a ball.
So, I'm not really sure which graphs can and can't be embedded yet, but I've managed to embed K5 but not K6 on the torus, as well as K3,4. I don't know if I embedded K4,4 yet, as I have tons of scrap paper with drawings on them now. Anyway, that's what I've been up to.
I came across a book about Topological Graph theory and since that sounded good and weird and like I wouldn't need to find a bunch of inequalities to do it, I started reading it, and came upon a problem involving planar graphs. A little explanation, though not anything rigorous:
First you have to know what a graph is. It is essentially a set of points connected by line segments. The points are called vertices, and the segments are called edges. Technically, graphs are sets which contain two sets, an edge set and a vertex set, where the vertex set is basically single numbers (generally integers), and edges are pairs of numbers, where both of the integers in the pair appear in the vertex set. But for our purposes, they are just dots with lines connecting them.
For most purposes, simple graphs will suffice, which are graphs where only one edge can appear between any two vertices, and no edge can connect a vertex to itself. If you are inclined to chemistry, you can think of them as molecule diagrams where no double bonds are allowed, but any number of bonds can be made between atoms. Actually, there is an interesting problem in graph theory of counting isomers of carbon chains of arbitrary length, but I digress.
The next thing you have to understand is what is meant by planar graphs. A planar graph is a graph that can be drawn in the plane without any edges intersecting. The analyst in my office would complain about that definition, but my tensor professor would love it because he insists that "R^2 is not a plane; a plane is a plane. R^2 is a set of pairs of numbers. What is a plane? I can't tell you, but I know what it is." That isn't an exact quote, but it is close. He also says things like, "There's no such thing as integration by parts. There is only the product rule." (^_^)
I will now give examples, like a good textbook:
This graph is K4 (the 4 is supposed to be a subscript, but blogs...). That is shorthand for the complete graph on four vertices, meaning that it has every edge that can exist on four vertices. Exercise: how many edges does Kn (the complete graph on n vertices) have?
Is K4 planar? One is tempted to say "no," since those two edges in the box intersect, and that's a no-no according to our definition. However, what if we draw it like this:
Now we have the same graph drawn in the plane, with no edges intersecting, so the answer above should actually be "yes." Technically, these graphs are not the same, they are only "isomorphic," but all that means is that if you treat graphs as they should be treated, as sets, and make a renaming function (i.e., an isomorphism) between the sets, all the relationships are preserved.
A better question is what graphs are (not) planar? A dude named Kuratowski essentially answered that question all at once and very neatly. He said (and proved) that all the non-planar graphs contain a copy of K5 or K3,3 (the bipartite graph on 3 and 3 vertices; a picture will follow). Technically, they just have to contain a subdivision of one of these two graphs. That is, if you take one of those graphs and add vertices on already established edges, you also can't draw that on the plane, but the important point is that we can tell, in a certain sense, very easily if a graph can be drawn in the plane.
K5
K3,3
The second one is called the complete bipartite graph because it has two subsets of vertices {1,2,3} and {4,5,6} that have no edges inside them, but all the other edges are there.
So, how do we know that things are planar/not planar? To show that something is planar, it's easy enough to just draw it in the plane, though in practice this could be staggeringly difficult for large graphs. To show something is non-planar, you can't just show one non-planar representation; you have to show that no planar representation is possible. Here's a bare-bones proof that K5 is non-planar, using the concept that that previous planar representation of K4 is "unique" up to bending, stretching and renaming, none of which affects planarity.
Now try putting the fifth vertex in any of the regions we've created and see if you can draw an edge to all the other vertices. So K5 isn't planar! I'll leave a proof of K3,3 up to you, but it can be done in much the same way.
Now, a mind that likes puzzles might wonder what is so special about the plane? What about other shapes, like a ball? Well, that question has been asked, but not totally answered. From now on I'm going to call "shapes" "surfaces" because that is the actual term. I'm not going to give you a real definition of a surface, but it essentially boils down to adding loops and crosscaps to the sphere.
The first part of the question is are there "planar" graphs and "non-planar" graphs for other surfaces, and the first answer is yes. In fact, some dude showed that for any surfaces, there is a finite set like {K5, K3,3} that generates all the non-embeddable graphs. However, except for the sphere, nobody knows what they are, so that is what I am messing with, but it is pretty complex. Let's consider the sphere:
There's our good buddy K4 drawn on the surface of a sphere. It shouldn't come as a surprise that anything we can embed on a plane we can embed on a sphere, since a sphere is what's called "locally Euclidean;" it looks like a plane as long as you only look in a little disk. But is that drawing still unique, as it was in the plane?
Oh, ho, ho! What if we wrap the last edge around the back? Well, it turns out that that doesn't change anything at all, because wrapping around the back is the same as stretching back and back and back. So, well, the sphere isn't too interesting. It's the same as a plane, but we like to use a sphere to judge from because it's what's called "compact." Don't worry about that much.
So what's the next simplest thing? A doughnut, or donut to normal people. Mathematicians of course call it a torus because we are contrarians by nature. Let's try drawing K4 again:
Try and draw the fifth vertex and you'll run into the same problem as before. But does this mean that K5 is non-embeddable on the torus? You should know by now that that isn't the case. What if we start by drawing the box in more natural ways?
Now try to draw that fifth vertex and you'll find that not only can you draw K5, but you can draw it in more than one way! So a donut has a little more freedom than a ball.
So, I'm not really sure which graphs can and can't be embedded yet, but I've managed to embed K5 but not K6 on the torus, as well as K3,4. I don't know if I embedded K4,4 yet, as I have tons of scrap paper with drawings on them now. Anyway, that's what I've been up to.
Now that Lost has supposedly ended (I did not watch it, but it's all over the internet), I'm expecting a bevy of posts from the Losties soon, but maybe not. It seems the consensus is that the finale was lame and didn't answer any interesting questions (again, I don't know which those are).
For my part, I just watched Superman: Doomsday, which was pretty good. In a way, it is disappointing because it's just a little story. When DC killed Superman, it was a big deal (like even non-comic nerds bought those issues). Then there is a long saga of four dudes claiming to be Superman taking over and us finding out who they all are, and eventually it segues into Hal Jordan, the Green Lantern, becoming Parallax and all this junk. Anyway, it's a huge deal, not just for Metropolis, but for people in general. In this movie, we don't get to see anything but Metropolis, and that is almost distracting, since I couldn't help thinking that when a somewhat evil Superman shows up and starts laying down the law, it seems unlikely to me that somebody like Batman would just let it happen and not try to Kryptonite the guy. There are just so many things that could happen, but we get a little story about Lex Luthor and then Superman just unceremoniously comes back to life and we get a battle Royale, which would be way more entertaining if it was with Captain Marvel or something. Ah, just limitations on movies.
Anyway, there's not much going on here. It's just muggy and gross. That's it for me.
For my part, I just watched Superman: Doomsday, which was pretty good. In a way, it is disappointing because it's just a little story. When DC killed Superman, it was a big deal (like even non-comic nerds bought those issues). Then there is a long saga of four dudes claiming to be Superman taking over and us finding out who they all are, and eventually it segues into Hal Jordan, the Green Lantern, becoming Parallax and all this junk. Anyway, it's a huge deal, not just for Metropolis, but for people in general. In this movie, we don't get to see anything but Metropolis, and that is almost distracting, since I couldn't help thinking that when a somewhat evil Superman shows up and starts laying down the law, it seems unlikely to me that somebody like Batman would just let it happen and not try to Kryptonite the guy. There are just so many things that could happen, but we get a little story about Lex Luthor and then Superman just unceremoniously comes back to life and we get a battle Royale, which would be way more entertaining if it was with Captain Marvel or something. Ah, just limitations on movies.
Anyway, there's not much going on here. It's just muggy and gross. That's it for me.
Thursday, May 20, 2010
Half-Post 350?
350 isn't an important number, is it? I don't know; I'm not too good with numbers. Maybe that's why lately I've been fascinated with embeddings of graphs on surfaces. Maybe I will post about that when I have time to draw some pictures.
In other news, I think Holiday picked up a hit the other day, even if we lost. At least the Reds lost, too.
In other news, I think Holiday picked up a hit the other day, even if we lost. At least the Reds lost, too.
Friday, May 7, 2010
Lol-iday
Matt Holliday needs to learn to hit a pitch. I went to two of those games and he was awful. Pujols was barely better. If we can't be Kendrick, then there is something wrong with the club. Hopefully we can pick up a few wins against the Buccos.
Also, can we not pick up a shortstop who bats above .200?
Also, can we not pick up a shortstop who bats above .200?
Sunday, May 2, 2010
野球
On Friday I went with a couple dudes to watch the Mets absolutely destroy the Phillies. Too bad, but I can't say I care that much. At least it's not the Yankees doing the winning. It was pretty crazy, though, since the Mets are the Phillies biggest rivals and this was their first meeting of the season. The stadium was packed and the parking lots (all the stadiums are right next to each other, so the parking lots can all be used at once) were full of people tailgating. So, that was cool. Alright, that's it.
Subscribe to:
Posts (Atom)
Posts
