**** Last updated ****
Wed. Dec. 17, 2003 (11:40 pm)
**********************
=======================================================================
Please turn in projects, if at all possible, by Wed. evening. I need them in hardcopy (printed), not just e-mail; thanks.
If you absolutely need more time, I'll extend by one extra day (Thursday) when I'll be around in the afternoon and evening. I may be here on Friday afternoon, too, but since grades are due on Friday, please hand in your projects by Thurs. When you turn in your project, it will be best to let me see it so that there aren't any surprises. If I have approved it and you are finished, the hardcopy can be put in my mailbox in the math dept office on Friday morning before noon.
In writing your papers, please (1) list your references, including from the web, following some reasonable and consistent format, (2) divide the paper into sections according to content, and (3) write the introduction of the paper last and at the end of the intro outline the remainder of the paper so that an interested reader can dive in to some specific part without having to wade through the entire paper to look for it. Don't write sentences like the last one. ;-)
I'm looking for papers that explore connections between mathematics, biology, and modeling. Show me that you got _interested_ in some problem and that you then followed up on your interest by intelligently searching for suitable information, assimilating such information when found, and then explaining how it is related to the problem. The paper should demonstrate your understanding and imagination.
For Thurs. 20 Nov., let t_n be the number of cubic plane rooted trees with n branchpoints. So t_0 is 1 (the only such tree consists of two vertices joined by an edge), t_1 is 1 (the only such tree looks like the letter "Y"), t_2 is 2 (assuming that the bottom is the root vertex, take either of the two top endpoints of the "Y" and attach a copy of Y so that the bottom glues onto the endpoint - that is, from the root, go to its unique neighboring vertex. From there, either going clockwise or counterclockwise from the root edge, you find the edge leading to the second branch point.) I drew the 5 trees that show that t_3 is 5. The exercise is to find t_4. If you can, also find a recursion for t_n (i.e., express it as a function of the other values of t_j for j less than n). Even better, find an explicit formula for t_n. (These latter two problems are much harder but give them a try just for fun ;-) Remember: no class on Tues. Nov. 25.
For Tues. the 18th (collected). Show that a tree always has exactly one more vertex than it has edges. Hint: Use induction! (You'll also need the result below that for every nontrivial tree there exists an endpoint - in fact, two, but we only need one ;-) The same argument can be used to show that every tree is planar - but I'm not assigning it.
For Thurs. Nov. 13, show that in any nontrivial tree, there must be at least two endpoints. I defined a tree in class as a graph which is connected with the additional property that if any edge is removed, the graph becomes disconnected. Note that we also need to assume that the graph has _finitely many_ vertices, which is a reasonable assumption. Note that without the finiteness assumption, my claim would be false. Let G be the (infinite) graph with vertices the integers and with [v,w] an edge if and only v and w differ by 1. Then G is a tree since it is connected but removing any edge [n,n+1] disconnects the graph: there is no path from any integer less than or equal to n to any integer greater than or equal to n+1. But every vertex in G has degree 2 - i.e., every integer is joined by an edge to the two integers which differ from it by adding or subtracting 1. So your argument should use finiteness.
For Tues. Nov. 11, show that the digraph D I drew in class (with 5 vertices) cannot be embedded in Q_4. You need to think about the structure of Q_4 to see why this can't be done. We went over this in class using my e-mail as a draft. The e-mail pointed out a missing hypothesis: Whenever there is a path from phi(v) to phi(w) in the hypercube, then there must already be a path from v to w in G. Hence, the two top vertices of D must go to distinct vertices of the hypercube each with "weight" three (i.e,, each cube vertex has exactly three 1s). We then showed that the three bottom vertices all go to vertices of the hypercube with weight not exceeding one.
Since there are six distinct edges connecting the bottom to the top of D and since each of the corresponding paths in Q_4 cross the layer of weight-2 vertices, we require that these 6 vertices should all be distinct. This is because the paths cannot conflict in any embedding. Now there are indeed 6 vertices on layer-2 since the number of 2-element subsets of a 4=element set is 6. But I still claim that there is a contradiction lurking here. Find it! Hint (Tues. at 3:30-ish): if there is a path from a vertex v_1 to another v_2 in any cube, there can never be a "1" in some coordinate of v_1 when there is a zero in the same coordinate of v_2. Show (using this) that one of the six vertices with weight 2 cannot be on any path to the two top vertices, which we agreed to call 1101 and 1110.
Also, please look through the new material. If you missed Thurs. class, come by my office for the handout = and definitely try the problem!
For Tuesday, Oct. 14, from the handout, do problems 1 and 14 on pp. 245 and 246. Also, if you haven't done the two problems below on convexity, do them, too.
For Thursday, Oct. 16, how many boxes do you need to pack the weights 9/10,1/2,1/3,1/5,1/5,1/5,1/10 given that each box has capacity 1? The heuristic I suggested in class is to first order the weights in decreasing order (already done) and then to put each weight into the first box which is not yet filled. This is a simple exercise designed to show the working of the heuristic.
For Tuesday Oct. 7, show that a subset of R^2 which is not connected is not convex and also that a subset with a "hole" must be nonconvex. These two (easy!) problems are to be written up and turned in. For Thursday, take a look at DNA, RNA, and all that jazz ;-) More seriously, we'll start to look at the kind of information which is considered in molecular biology - both strings (of what?) and configurations (of what?). Since we don't have a text, you can use whatever references you find. We'll have an interactive class where we all contribute to sketching out what is known. THose with good background in biology are especially welcome!
For Thurs. Oct. 2, do the following: Let (0,-1) be a point in R^2 (2-dimensional space), and let M be the line y = x. Find the set P_M (0,-1) of points in M which are closest to (0,-1) under two different notions of distance - the Euclidean distance (square root of sum of squares of coordinate differences) and the "l_1" distance (sum of absolute values of coordinate differences). In the Euclidean case, you may use your knowledge of analytic geometry and a bit of calculus, too. For the l_1 case, remember that the set P_M (0,-1) is the intersection of the ball in the l_1 norm centered at (0,-1), which "just reaches" M, with M. If you can, also find the set P_M(x_0,y_0) where (x_0,y_0) is any point in R^2 and M is the line with equation alpha*x + beta*y = c, with respect to Euclidean distance.
The assignment for Tuesday the 30th was given in class. If you didn't do the one below, then do the corresponding problem in 3 dimensions.
For Thurs. 25 Sept., please show the following: (note new last line where I make it easier below!)
The absolute value of the inner product of two vectors is at most the product of their norms, when the vectors are in R^n. This means the following: First vectors are just elements of vector spaces ;-) And R^n, as I mentioned in class, is a vector space (check it!) whose elements are n-tuples of real numbers with coordinate-wise sum and scalar multiplication. The inner product of x and y in R^n is denoted x . y (x "dot" y) and is defined as the sum x_1 y_1 + ... + x_n y_n The norm ||x|| of a vector x is defined as the square root of x . x, so ||x|| = (x_1^2 + ... + x_n^2)^(1/2) Thus, the exercise is to show |x . y| <= ||x||*||y||, where I'm writing "*" for multiplication when juxtaposition might be confusing and "<=" means "less than or equal". My hint in class is to square both sides and do the algebra. (I had previously added another remark but we don't need it here.) Let me give you a break: show this when n=2.
Old homework
Exercises due Tues. (I had left "Thurs" for a couple of days - sorry)
Sept. 23 (deferred due to hurricane):
A vector space X over a field k (imagine the reals if you prefer)
is a nonempty set with two operations: sum (or "+") which maps
X x X to X by sending (x,x') to x + x', and scalar multiplication
which maps k x X to X by sending (a,x) to ax (a any element in k);
sum is required to endow X with the structure of a commutative group
and scalar multiplication is required to be distributive over the
group operation. This means the following: There is an element 0
in X for which for all x, x + 0 = x; for all x and x', x + x' = x' + x;
for all x,x',x'', (x + x') + x'' = x + (x' + x''); for all a,x,x',
a(x + x') = ax + ax'; and finally for all a,a',x, (aa')x = a(a'x).
For the time being, we will take k to be the reals (necessary for
the definitions and properties below to make sense) but there are
many places where other fields are used - e.g., the one with two
elements, but we'll get to them later! So for now, assume that
"vector space" means "real vector space" - i.e., that k = R.
Recall that a subset A of a vector space X is convex if whenever it
contains two points a and b, it contains the entire line segment [a,b],
where [a,b] is the set of all points x_t = (1-t)a + tb, t in [0,1].
So x_0 = a, x_(1/2) = (a + b)/2 (the midpoint), and x_1 = b. In
R^2, which is a perfectly good vector space (right?), [a,b] just
means the ordinary line segment you can draw between the two points.
Show that if A is a convex subset of vector space X, then A contains
any point in the triangle spanned by any three points in A.
Also show that the intersection of two convex sets is convex.
I mentioned in class that a subset A of the real numbers is convex
if and only if it is an interval.
There are many interesting properties of convex sets. For instance,
here is one more you might like to show (as it would make a nice
quiz problem ;-) Such problems, while not required to be "written
up" for homework, should be tried as they introduce nice ideas and,
in some cases, might indeed be the topic of a quiz.
If C_1 and C_2 are subsets of a vector space X,
and let C = C_1 + C_2 be the _pointwise sum_
C = {x_1 + x_2: x_1 in C_1, x_2 in C_2};
that is, the pointwise sum is the set which contains all possible
sums of two elements, the first from C_1 and the second from C_2.
Show that if C_1 and C_2 are convex, then C_1 + C_2 is convex, too.
Exercises due on Tuesday.
For any set S, let chi_S (x) = 1 if x is in S and 0 if x is not in S. Let a < b. Recall that [a,b) is the set of all real numbers a <= t < b. Show that chi_[a,b) (x) = H(x-a) - H(x-b). Hint. Consider three cases: (i) x < a, (ii) a <= x < b, (iii) b <= x, and in each case, show that the two functions on the left and right-hand sides give the same value. The second exercise involves Heavisides composed with dot products (see the paragraph below for the definition of dot product). Let the dimension d = 2 so elements in R^d can be taken as complex numbers. For any complex number z = a + bi = (a,b), z . (1,0) = a*1 + b*0 = a = Re(z). Hence, H(z . (1,0)) = 1 if Re(z) >= 0 and 0 otherwise. Exercise 2. Evaluate the function f(z) = H(z . (1,0)) - H(z . (1,0) - 3). Thanks to a question from Steve, I see that I didn't fully explain this second problem. What I mean is to find out for which z it has value 1 and for which z it has value 0 (those are the only two values possible here).
Let me add a word about dot products. If w and x are both d-vectors, then w . x = sum(i = 1 to d) w_i * x_i. For any vector w, the set of all x for which w . x is nonnegative is exactly the set of all vectors in the orthogonal halfspace which contains w. Thus, if w is orthogonal (i.e., at right angles to) the blackboard and pointing into the wall, then all x on or behind the blackboard have nonnegative dot product with w. Of course, all other x have negative dot product with w. Hence, H(w . x) is 1 for all vectors x in halfspace and 0 elsewhere. The trick that works in one dimension fails here since it gives a "slab".
Your grade in the class depends on doing homework and being here for at least most of the quizzes (which are not announced in advance ;-) In addition, your project will be the other key factor.
I described a nice argument by Feller (on 9/4) showing that the variance of the sum of n random 0/1 variables is _largest_ when the variables are identically distributed. Thus, the lack of uniformity which one typically finds in biology is associated with lower variance for the overall performance of the population.
Instructor: Paul Kainen, Department of Mathematics. You can reach me at 7-2703 or kainen@georgetown.edu; I have office hours in Kober-Cogan B06 MW 2:30 to 4 pm, and in Reiss 248 on MW 6 to 7:30 pm and T 7:15 to 8 pm. For information on grading, please see the course mechanics page. For some history and related topics, see the history and references page.
A rough sketch of the syllabus is as follows:
For students at Georgetown University; other information at my home(ly) page. or my index page . Please either e-mail me, phone 7-2703, or drop by my office if you have any questions regarding the course.