For those of my readers who know some combinatorics and have seen graphs before, I'd like to say a little bit more on one topic from graph theory that I've been learning about. If you aren't so interested in math and don't care about graphs, then you can skip ahead and read the last two paragraphs. The topic I want to tell you about is list coloring, which is a generalization of coloring a graph.
As you may know, a graph's vertices can be colored such that no two adjacent vertices are the same color. Now let's restrict how we can color the graph: given a graph G, at each vertex v of G, put a list of colors L(v). We now properly color G such that each vertex v has a color from its list L(v); this is called a list coloring of G.
The chromatic number χ(G) is the smallest number of colors with which G can be properly colored, without list restrictions. We can define a similar notion for list colorings, considering the size of each color list. The list-chromatic number, or choice number, is the smallest r such that G can be list-colored for every possible system of lists of length r. We denote this as ch(G). Note that this number gives the length of each list, not necessarily the number of colors we use; this confused me at first.
The choice number and chromatic number are related: for any graph G, χ(G) ≤ ch(G). Do we ever have χ(G) = ch(G)? In my graph theory class we learned that, if G is the line graph of a bipartite graph, then χ(G) = ch(G). (By the way, the proof of this theorem uses the stable-marriage existence theorem!)
This theorem is applicable to an important combinatorial problem: Given an n-by-n matrix where each position carries a list of length n, is it possible to fill each position with an item from its list in such a way that each row and each column has n distinct items? If we have {1, …, n} at each position, then it is possible; such a matrix is called a Latin square. But can this be done for any system of lists?
This problem can be solved by constructing a graph with the entries of the matrix as vertices and drawing edges between two vertices if they are in the same row or column of the matrix. Then the problem becomes: is χ(G) = ch(G) for this graph? The graph is actually the line graph of the complete bipartite graph. So, by the theorem I mentioned earlier, there is a list coloring; the answer to our question is yes, we can always select items for the matrix, no matter what the lists are.
One problem on my graph theory homework this week was to prove that, if all of the positions of the matrix have length-n lists except one list which is length-(n/2), then a proper choice is not always possible. This means that we have to construct such a system of lists on the n-by-n matrix, such that it is impossible to choose n distinct items in each row and column.
This is perhaps the hardest problem that I had so far been given in graph theory, and I didn't really know where to start on this one; fortunately, neither did my two roommates. So last night, we sat down together for a few hours and tried to construct the list-system. We made lots of sketches and guesses, most of which didn't work. But over time, we got to know the problem and understand parts of it, and eventually one of us had a breakthrough. One of my roommates found a list system on the 4-by-4 matrix that worked; then the other roommate found a way to prove why it worked (using the pigeonhole principle!); and then I was able to extend the construction and the proof to the general n-by-n case. We had solved the problem—but more importantly, we had fun with it. It was exhilarating to try different approaches and finally find one that worked, and I was really happy that I had friends that shared this feeling with me.
That's what I love most about the BSM program: I always have math to do, I always have people to do the math with if I want, and we always have tons of fun doing the math. I feel like I'm swimming in math, and every day I am even more sure that this is what I want to be doing for the rest of my life.
2011-10-27
2011-10-19
Graph theory.
Everyone thinks they know what a graph is, but most people don't know what a graph is. Do you know what a graph is? You will definitely know what one is after I tell you. A graph is not the thing you had to draw in high-school algebra. A graph is also not a giraffe, contrary to popular belief. A graph is something like this:
A graph is a bunch of dots connected by lines or curves. The dots are called vertices, and the lines and curves are called edges. This is all there is to a graph. In particular, a graph is generally not concerned with distances or orientations. The above graph, the Petersen graph, is exactly the same graph as this one:
But it looks different! It doesn't matter, though; it's still the same graph. The only thing that matters for a graph is which vertices are connected by edges. It turns out that, in the pair of graphs in this paragraph, you can label each vertex with a number in such a way that the same numbers have edges between them in both versions of the graph. That's how you know they're the same graph. In fact, this was one of my first homework problems in my graph theory class.
I think graph theory is really fun. The problems I get in the class are challenging and interesting—the best possible combination. The professor gives us information in lecture, but then on the homework we have to use what we learned to discover new things, in a way that isn't always immediately clear.
The class has spent a lot of time on Hamiltonian cycles. A cycle is a path through the edges of a graph that doesn't repeat any vertices and ends where it began. A Hamiltonian cycle is a cycle that reaches each vertex once. Not every graph has a Hamiltonian cycle, and an interesting and important part of graph theory studies the question of which graphs have Hamiltonian cycles and which ones don't.
Another really cool thing I've learned about in class is graph coloring. To properly color the vertices of a graph, you assign each one a color in such a way that there is no edge between two same-color vertices—that is, the endpoints of an edge are different colors from each other. Any graph can be properly colored (just put a different color on each vertex), but sometimes we want to know the least number of colors that are needed to properly color a graph. This number is called the chromatic number of the graph.
Graphs are also used in the "stable marriage problem": given a set of people, each having a preference ranking of some of the other people, is there a way to pair off the people so that no two people both prefer the other over their partner? This problem is represented as a graph: each person is a vertex, and each pair of vertices has an edge if it is a possible partnership. Then each vertex has a ranking of the vertices that it's adjacent to. In the traditional scenario, where there are men and women that are to be married off, the answer is yes, there is a stable marriage. In this case, the algorithm for finding a stable marriage is incredibly amusing: it is best conceptualized in terms of one gender making proposals to the other, who accepts or rejects each proposal.
That's about it for giraffe theory. I'm sorry I haven't been updating my blog very often; I'll have to shape up soon, because my next entry will be about my geometry class. HA HA HA.
 |
| The Petersen graph: one of the most famous graphs. (Image from Wikipedia.) |
 |
| Also the Petersen graph. (Image from Wikipedia.) |
I think graph theory is really fun. The problems I get in the class are challenging and interesting—the best possible combination. The professor gives us information in lecture, but then on the homework we have to use what we learned to discover new things, in a way that isn't always immediately clear.
The class has spent a lot of time on Hamiltonian cycles. A cycle is a path through the edges of a graph that doesn't repeat any vertices and ends where it began. A Hamiltonian cycle is a cycle that reaches each vertex once. Not every graph has a Hamiltonian cycle, and an interesting and important part of graph theory studies the question of which graphs have Hamiltonian cycles and which ones don't.
Another really cool thing I've learned about in class is graph coloring. To properly color the vertices of a graph, you assign each one a color in such a way that there is no edge between two same-color vertices—that is, the endpoints of an edge are different colors from each other. Any graph can be properly colored (just put a different color on each vertex), but sometimes we want to know the least number of colors that are needed to properly color a graph. This number is called the chromatic number of the graph.
Graphs are also used in the "stable marriage problem": given a set of people, each having a preference ranking of some of the other people, is there a way to pair off the people so that no two people both prefer the other over their partner? This problem is represented as a graph: each person is a vertex, and each pair of vertices has an edge if it is a possible partnership. Then each vertex has a ranking of the vertices that it's adjacent to. In the traditional scenario, where there are men and women that are to be married off, the answer is yes, there is a stable marriage. In this case, the algorithm for finding a stable marriage is incredibly amusing: it is best conceptualized in terms of one gender making proposals to the other, who accepts or rejects each proposal.
That's about it for giraffe theory. I'm sorry I haven't been updating my blog very often; I'll have to shape up soon, because my next entry will be about my geometry class. HA HA HA.
2011-10-05
Learning mathematics.
Typically, a student in my program will take between three and five math classes. This semester, I am taking five math classes. This is what they are:
There are 26 math classes offered this semester (if I counted correctly). You can see the schedule and list of classes if you want. There are also a few other classes, such as: Hungarian language, some history class, and political philosophy—but of course I'm not bothering with being well-rounded.
Typically, each math class starts at n:15, goes until (n+1):00, has a fifteen-minute break from (n+1):00 to (n+1):15, and continues until (n+2):00, for n = 8, 10, or 12 depending on the class. There are a lot of cheap and good places to eat that are near the school, so sometimes during a fifteen-minutes break I go get a snack or lunch. On days when I have class from 8:00AM to 2:00PM, I've been in the habit of getting falafel to-go, from this restaurant right across the street.
This entry was supposed to be about math classes and now I'm talking about food yet again. Oops.
The classes are pretty much the same as college classes in America, with a few important exceptions. First, the chalkboards have two panels, and when one panel is lowered the other panel rises. You can write stuff on the first panel when it's in the lowered position, then lower the second panel—thus moving the stuff you already wrote out of the way—and then write more stuff on the second panel. It's really cool.
The professors aren't really available outside of class. They typically have only have one office hour each week, and it takes place during usual class time. It's not so much an office hour as it is a supplementary session of class; professors spend the hour answering questions about the class material or the homework, usually in front of the whole class. I haven't really needed one-on-one time with my professors (not yet, anyway), so this hasn't been such a big deal for me. It is nevertheless a sharp contrast to my college, where I can just walk into a professor's office and have a conversation pretty much whenever I want.
The professors are Hungarian, and they know varying amounts of English. Some professors know just enough English to give math lectures, but they can sometimes be unintelligible. Other professors have nearly perfect English, with just a slight accent. There is one professor who speaks acceptable English, but his words are obscured by his impressive moustache.
Course registration did not happen until three weeks into the semester. This is because, in the Hungarian system, students "shop around" at various classes for the first few weeks, and then they decide what to take based on actually going to the class. It's a really nice system that makes the decision a lot easier, but it also makes it extremely hectic during the first week or two when we're trying out like nine classes.
Next journal entry, I'll talk about graph theory. If you have never heard of graph theory, then you probably don't know what a graph is. But soon you will find out!
- Graph theory;
- Geometry;
- Combinatorics 2;
- Functional analysis;
- Mathematical logic.
There are 26 math classes offered this semester (if I counted correctly). You can see the schedule and list of classes if you want. There are also a few other classes, such as: Hungarian language, some history class, and political philosophy—but of course I'm not bothering with being well-rounded.
Typically, each math class starts at n:15, goes until (n+1):00, has a fifteen-minute break from (n+1):00 to (n+1):15, and continues until (n+2):00, for n = 8, 10, or 12 depending on the class. There are a lot of cheap and good places to eat that are near the school, so sometimes during a fifteen-minutes break I go get a snack or lunch. On days when I have class from 8:00AM to 2:00PM, I've been in the habit of getting falafel to-go, from this restaurant right across the street.
This entry was supposed to be about math classes and now I'm talking about food yet again. Oops.
The classes are pretty much the same as college classes in America, with a few important exceptions. First, the chalkboards have two panels, and when one panel is lowered the other panel rises. You can write stuff on the first panel when it's in the lowered position, then lower the second panel—thus moving the stuff you already wrote out of the way—and then write more stuff on the second panel. It's really cool.
The professors aren't really available outside of class. They typically have only have one office hour each week, and it takes place during usual class time. It's not so much an office hour as it is a supplementary session of class; professors spend the hour answering questions about the class material or the homework, usually in front of the whole class. I haven't really needed one-on-one time with my professors (not yet, anyway), so this hasn't been such a big deal for me. It is nevertheless a sharp contrast to my college, where I can just walk into a professor's office and have a conversation pretty much whenever I want.
The professors are Hungarian, and they know varying amounts of English. Some professors know just enough English to give math lectures, but they can sometimes be unintelligible. Other professors have nearly perfect English, with just a slight accent. There is one professor who speaks acceptable English, but his words are obscured by his impressive moustache.
Course registration did not happen until three weeks into the semester. This is because, in the Hungarian system, students "shop around" at various classes for the first few weeks, and then they decide what to take based on actually going to the class. It's a really nice system that makes the decision a lot easier, but it also makes it extremely hectic during the first week or two when we're trying out like nine classes.
Next journal entry, I'll talk about graph theory. If you have never heard of graph theory, then you probably don't know what a graph is. But soon you will find out!
Subscribe to:
Posts (Atom)