Combinatorics

So I stressed myself out a little too much preparing for the combinatorics exam. Mostly because well I didn’t really feel like I had a grasp on what was going to be on the exam. In the end I had completed the two hour exam in about 45 min and I am pretty sure I got a perfect score or close to it.

The format of the exam was kind of strange there were 5 problems worth 40 points of which we had to chose 2 and 5 problems worth 30 points of which we had to chose 4. I can’t remember what all the first 5 problems were. There was one to prove the binomial theorem which I almost did, one dealing with one-to-one correspondences, something strange that I can’t seem to recall, and then the two that I did.

The first one I did was to show that the Ramsey number R(3,3)=6. I was honestly surprised that this was on there. I knew there was going to be a problem dealing with Ramsey numbers, but I expected something more difficult. Truthfully I expected that a problem to show that R(3,3,3)=17.

Like I said I was going to do the prove the binomial theorem problem, but I read the 5th problem and it seemed like it would be easier to do without making a mistake so I went with it. Problem 5 defined relation (Q, \le ) to be transitive and reflexive and another relation (Q, ~) such that R~T iff R \le T  and T \le R and we were asked to show that (Q, ~) was an equivalence relation. Like I said this test seemed really easy.

The other 5 problems I was just going to do the first 4, but one had some sum of binomial coefficients and asked for a binomial coefficient that it was equal to and I thought I might mess up the algebra on that one so I skipped it. The 4 problems I did were a direct application of the pigeon-hole principle, a direct application of the binomial theorem, a counting problem related to poker hands, and provide the definition of reflexive, symmetric, antisymmetric, transitive, partial order, and equivalence relation.

The exam was yesterday afternoon so I didn’t expect them to graded by this morning and they weren’t, but we did discuss what we were going to do for the next four weeks. He wasn’t sure if we wanted to continue on the counting stuff or work on some of the other areas of combinatorics. We finally settled on one week on inclusion/exclusion, one week on designs, and two weeks on graph theory.

 I’m glad we are going to get some graph theory since that is mainly the reason I took the class and well the professor is a graph theorist so it should be interesting. I’m not quite sure exactly what is meant by designs, but apparently that is the primary area of interest of Brualdi who authored the text so I guess it makes sense to spend some time there. It should be an interesting four weeks in combinatorics.

Stressed out

So far this week I have had homework due in analysis and an exam in algebra and anthropology. Plus on the way to class on Tuesday one of the tires fell off of my car so I have had to deal with that in addition to having homework due tomorrow in both combinatorics and algebra. Needless to say I am a little bit stressed out and slightly behind on my sleep, but at least I got an A on the algebra exam! Hopefully things will calm down a little bit after the combinatorics exam next Thursday.
I am really nervous about that exam since a lot of times on the homework I feel the exercises are really worded very well and so it takes a lot of time just to figure out exactly what the exercise is asking for. Another thing is he is giving us two hours to take the exam which makes me nervous about the number of questions that will be on the exam. I suppose I should just stop stressing myself out over it.

Algebra Exam

Yesterday was the first algebra exam and it was rather surprising how easy the exam was. There was a problem about an equivalence relations, a problem to show that a given operation and a given set defined a group, a problem to show that a given function mapping a group to itself defined an isomorphism, and finally a couple of computational problems involving isometries of R^2 .

The problem to find the reflection about a given line kind of pain in the rear since I had only bothered to memorize the formula for reflection about a line with a given angle and the line was given by its slope on the test. And of course the slope wasn’t anything that I could mentally take the arctangent of, so I had to fudge around with trig identities to find the formula to find the reflection using the slope. I did remember that the matrix was multiplied by \frac{1}{1+M^2} so at least I had an idea of what to do to find the formula. I memorized the angle formula rather than the slope since it was easier to remember, but I suppose it is probably easier to derive the angle formula from the slope formula than the slope form from the angle formula.

I had an issue showing that the defined function in the isomorphism problem was surjective and I left the exam not really certain that I had a solid proof, but today in the homework session he was talking a little about that problem and mentioned something about x being given as a fixed element of G. I must have totally misread the problem since I couldn’t tell if x was in G or not, but my hand waving about the function being invertible is actually a pretty solid proof if x is an element of G.

The only other problem I had stemmed directly from my inability to do one problem at time on a math test. I started the equivalence relation problem working with integers, went to the show this is a group problem working with reals not -1, went back to the equivalence relation problem, and then when I went back to the group problem I got that x^{-1}= \frac{x}{x+1} and I freaked out because that wasn’t an integer. So I flipped back to make sure that I was supposed to be showing that this was a group and realized that I was back to working with real numbers and so the inverse need not be an integer.

Algebra and the definition of continuity

I spent most of yesterday working on the algebra homework that was due today and once again I have to say the assignment was really well put together. The problems were mostly about showing something is a group or a subgroup, but the concept of isomorphism came up a couple of times as well. All and all I think I learned quite a bit from doing this assignment.
One of the problems required that you show that certain functions were continuous. Personally I thought this was one of the easier problems that was assigned, but near the end of the homework session yesterday I was helping a couple people with it and I told them that the proof was almost a trivial application of the definition of continuous. They both looked at me like I had two heads. Now neither of them has studied much analysis beyond the required calculus sequence and now that I think about it I can’t really remember how continuous was defined in my first calculus class.
I know we discussed continuity since I remember learning the intermediate value theorem and obviously there needs to be some understanding of continuity to discuss derivatives, but even though it has been awhile I don’t think the delta-epsilon definition of continuity was ever mentioned. So how was continuity defined?
I tried to consult my old calculus text, but I’m not exactly sure where it is at the moment. So I did a search trying to find out how AP calculus classes were defining continuity and the only thing I found was defining continuity at a point if the limit as x goes to c exists and is equal to f(c). Which is all fine and dandy, but the intermediate value theorem requires continuity over an interval. So how was continuity over an interval defined in my calculus class? I suppose someday I will find my old text and have an answer.

N+1 pigeons and only N pigeon holes

I spent most of the day yesterday working on the combinatorics homework that was due today. All of the exercises required the application of the pigeon-hole principle, but well I suppose that is to be expected after we spent the last week or so talking about the pigeon-hole principle in class. I am certainly glad that we are starting another section where not everything will have been contrived so as to make it possible to use the pigeon-hole principle. Anyway a couple of the exercises on this past homework were kind of interesting so I thought I might write about them.

In a room of 10 people, each of which has an age (in whole years) of at least 1 and not more than 60, show that you can select 2 groups with no common person such that the sum of the ages of the people in the 2 groups are equal. This problem took me a while to figure out, mostly because I was stupid and tried to construct disjoint subsets. Once I realized that I didn’t need to construct disjoint subsets since if I had 2 subsets with common elements, but equal sums I could just take out the common elements to get disjoint subsets with equal sums the problem was pretty easy.

The other problem I found interesting was probably just because it was geometric in nature. Basically there was a square with side length 2 and we had to show that if you placed 5 points within the square than the distance between them would be at most \sqrt{2} . The basic idea is that if you center the square on the origin than you can cover the entire square with circles with diameter of \sqrt{2} centered at (\pm 1/2, \pm 1/2). Now if 2 points are in the same circle than the distance between them is at most \sqrt{2} and there are 4 circles and 5 points.

Algebra

Today we had a study group meeting for my algebra class to work on the homework that is due tomorrow. I have to admit that I was apprehensive going into this since I have always shied away from studying in groups, but I have decided to give it a try at least some just to see how it works. I was pleasantly surprised that I seemed to gain a lot from being there; even though I was often in a “teacher” type of role I found that trying to explain my ideas to other people often times forced me to state them in different more clear ways.

The one problem that seemed to excite the most discussion was a problem that defined two equivalence relations on R^3 such that P and P’ are related if they are planes in R^3 that have the same normal vector and L and L’ are related if they are lines in R^3 that have proportional direction vectors. Essentially, the relations defined equivalence classes which consisted of parallel planes and lines. In fact I think this was the definition given in the statement of the problem, but I found it easier to look at the classes as sets of lines and planes defined by the same vector.

Anyway the first part seemed almost trivial. All it asked was that given a plane P in R^3 to show that there was a unique plane p_0 passing through the origin such that p_0 is an element of [P] and then to show that given a line L in R^3 there was a unique line l_0 passing through the origin such that l_0 is an element of [L].

Moving on to part b is where things got much more complicated. RP^2 was defined to be a 2-dimensional geometry whose points are equivalence classes [L] and whose lines are equivalence classes [P]. A point [L] is incident with a line [P] iff l_0 is a line in the plane p_0 . Part B asked for a proof that any two points of RP^2 lie on a unique line of RP^2 . This turned out to be not so bad once I was able to get my head around what it was asking. Pretty much it is asking you to prove that you can define a plane by two distinct lines that lie within the plane.

Part c then asked for a proof that any two lines of RP^2 intersect at a unique point in RP^2 . Most of the discussion here again took off in the direction of planes in lines in R^3 , but a couple of us found a different approach that almost seems like cheating the problem. Simply assume that there are 2 distinct lines [P] and [P’] in RP^2 that don’t intersect at a unique point. Now either [P] and [P’] don’t intersect in RP^2 or [P] and [P’] intersect at more than one point in RP^2 . But in the case of the former this implies that all elements of [P] don’t intersect any elements of [P’] which can’t happen since [P] and [P’] are distinct sets of parallel planes. In the latter case you can quickly contradict the result from part b since you now can define two distinct points in RP^2 that both lie on two distinct lines in RP^2 . Thus any two lines in RP^2 must intersect at a unique point.

Addition and multiplication

One of the problems for my algebra homework was to show that addition and multiplication are well defined on Z mod n. The addition part was pretty easy just let [a]=[a’] and [b]=[b’] and now everything pretty much follows from the definitions. a-a’=kn and b-b’=mn for some integers k and m. Now (a+b)-(a’+b’) gives some terms divisible by n and then (a-a’) and (b-b’) terms which of course are also divisible by n.
That didn’t take much time at all to figure out. Trying the same thing on multiplication didn’t seem to work out very well. (It may very well work, but I failed to accomplish anything more than making a mess.) Sadly it took me a little while to stumble on to the trick of using the division algorithm to represent a, a’, b, b’ and showing that the remainders for the congruent variables were the same. From that point it was easy to show that ab-a’b’ was divisible by n since the remainders canceled and I was left with a bunch of terms that contained n and thus were divisible by n.

Winter Quarter

Today was the third day of classes so far this quarter. I am taking five classes this quarter: Analysis, Algebra, Combinatorics, Stats, and Anthropology. Of course I wanted to take Italian, but it wasn’t to be, the waitlist wasn’t shrinking and they didn’t open another section so I ended up in Combinatorics. This should turn out to be a fun quarter.
Algebra seems really cool. Most of this quarter we are going to end up focusing on group theory, but so far we have just rehashed some set theory from the foundations class I took last quarter and defined equivalence relations and equivalence classes. The first day of class he said that the homework was going to be pretty difficult and typically that means that it will be interesting. We got the first homework assignment today, but I haven’t had a chance to even look at it yet so I can’t really comment on it. It is due on Wednesday, but the professor is holding an additional class meeting on Tuesdays to work on homework so I want to have most of it figured out by then.
Combinatorics is a hard class to get a grasp on. So far there have just been some motivating problems designed to get us to see the types of problems that combinatorics can solve, although today we did start looking at the pigeon-hole principle and how it can be applied to various combinatorial problems. The first homework is due tomorrow and I have it mostly done, there were a couple of interesting problems on there that I might comment on sometime in the future.
Stats is well stats. I’m still not sure that I am excited about the subject, but I think this quarter probably will be better than the previous. To begin with the lectures are less boring. They still more at a slower pace than I am accustomed to, but at least I don’t have to fight to stay awake. Add to that the homework appears to be if not more interesting than the homework last quarter at least shorter and less repetitive.
Analysis has been pretty annoying so far. The class has met twice and both times it has been pretty much a repeat of foundations from last quarter. The first class was mostly just induction and today it was cardinality of sets, including repeat proofs of at least 4 results from last quarter. Hopefully Friday’s class will introduce some new material since I think he is running out of stuff from last quarter to prove.
My Anthropology class has only met once thus far, but looks like it is going to have a fair amount of reading required, but other than that it doesn’t seem like there is much work involved. It was kind of funny that when I arrived to the class, probably about 20 minutes early, there were about 15 students standing outside of the empty classroom. Once I went in and sat down they all came in and sat down as well. I’m not sure if they were unable to figure out how to open the door or if they finally figured out that sitting down was probably preferable to standing. Either way it kind of scares me to be in a class with these people.
On Tuesday I went to the Reading Classics seminar. I think I am going to try and attend all of them, but I don’t think I am going to formally register for it since I don’t want to commit to anything yet, but given that one of the organizers was already suggesting topics to everyone in the room my guess is that I will probably be badgered into presenting something sometime this quarter. We are looking at Lagrange and his contemporaries and the topic yesterday and spilling over into next Tuesday was Lagrange and the three-body problem. I’ve never really been interested in this type of problem, but I do have to say is fairly interesting to see how people would go about attacking a practical problem such as this.

84 words a day

Since I eventually am considering applying to graduate schools I figured at some point, probably sometime near the end of next summer, I should probably take the GRE. I looked up the test to see exactly what all was involved and apparently the general GRE is a three part test: Analytical writing, Verbal, and Quantitative. Additionally I will have to take the math subject GRE which looks to contain a large amount of calculus, a good bit of algebra, and the rest of the test is a grab bag of other mathematical subjects.
The analytical writing part looks pretty stupid; you end up writing two essays on some pretty random topics. It reminds me a lot of the ninth grade proficiency test we had to take in high school where if you don’t structure your essay in a particular cookie cutter format you wouldn’t score well regardless of how well written the essay was. None of the sample topics looked like they would be even remotely interesting. I am definitely not looking forward to this part of the test.
The quantitative part of the general test looks to be pretty much a joke. I haven’t really delved into it very far, but I suppose that the majority of my studying for this part will just be familiarizing myself with the various types of questions that are asked within the test. Maybe I am just being arrogant, but I don’t see this portion of the test challenging my mathematical skills in the slightest.
The math subject test is probably the most important part of the test, but given the amount of time I am already going to allot to study the various subjects that are included on the exam I don’t think I am going to have to spend a large amount of time studying for this test. I do however plan to get one of those GRE math subject exam study aids that includes a few practice tests so that I have a few practice tests that I can take just so I get a feel for the type of questions that will be on there.
That leaves just the verbal section of the general test. I started taking a practice test last night before dinner and while I didn’t get very far I did find an area where I am going to be very weak: analogies. I did maybe 10 of these last night and missed about 4 and at least one of the ones I got right was just a correct guess. Most of my problems stemmed from the fact that my vocabulary doesn’t include a lot of the words that are included in a lot of the analogies so I don’t even have a clue as to where to begin.
I decided that I needed to learn the words that were going to be on the test sometime before I took the test. So I found a list of words that you should know when taking the GRE and divided them up so that I would have looked up all the words within 60 days. It worked out to be 84 words a day. So today I started with the first 84 words and it is quite a mix of words. From words like able-bodied that I wouldn’t expect to be on a test like this, to words like abdomen that I wouldn’t expect would be on a list like this, to words like abbess which I wouldn’t ever expect to have to use in my life. Of course, I guess it is entirely possible I might someday find myself in a nunnery needing to speak to someone in authority. Then I will be glad to have learned the word abbess while studying for the GRE.

Winter Quarter

My schedule for winter quarter is pretty much set. I am currently enrolled in algebra, analysis, stats, and anthropology. I am still third on the waitlist for Italian, but with 13 people still on the waitlist I am still optimistic about them opening up another section. If I don’t end up getting into Italian by the Sunday prior to the start of winter quarter I think I am going to drop from the waitlist and enroll in the combinatorics course that is offered this quarter.
The combinatorics course both counts as a math elective and is recommended to students that are considering graduate studies in mathematics. Plus I have always found combinatorics to be pretty interesting. So in short I would love to be taking that course rather than Italian, but Italian is also a requirement for me to graduate and I am very nervous about having a gap between the courses again.
I got lucky last time in that I think I was probably over prepared for Italian 102 compared to the other students that were in my class, but I still was really rusty at the beginning of the quarter. This time I will have taken Italian at the same school as the rest of the students in the class only they most likely will have taken the class just the previous quarter. I know that I can study Italian some over the course of the next quarter just to keep it fresh, but to be perfectly honest that probably won’t happen. The plan over the summer was to spend some time each day learning Italian, but that got pushed to the backburner due to more pressing demands from the classes that I was currently enrolled in. Over the summer I took only 15 hours and this winter I will end up taking either 19 or 20 hours.
The only other point of uncertainty in my upcoming schedule is a seminar that is being offered about Lagrange and contemporaries. While I am not interested in making a career out of history of mathematics, I do find it interesting to read papers by the older mathematicians. Often times I have found that reading the original work by classical mathematicians makes it easier to understand the concept since the papers aren’t bogged down with modern notation. There is a history of math class that is offered that sounds really cool, but I am pretty certain that I can’t take it due to restrictions on how many courses that I can take within the math department. The seminar would count against that total as well, but it is only one hour so I don’t think it will make as big of a difference. My main concern is that I don’t know how much work the seminar is going to end up being. Even though it is only worth 1 hour adding it would give me six courses for the quarter something that seems rather crazy to me. I guess the only thing to do is to show up to the first meeting and see how much work will be involved.