## Friday, April 30, 2010

### Homework #6 correction

I had the numbers wrong in the additional problem that was assigned. The correct problem is now listed in the homework (I changed the 'b' vector from [-323,1035,654] to [-323,389,8]).

## Monday, April 26, 2010

### Homework #6

Sorry for the delay in assigning the homework. Posting the problem set completely slipped my mind until Sunday evening. The due date for this homework will be May 6th to account for the delayed assignment time.

6.1: 4

6.2: 4

6.3: 5,7,10

7.1: 5,8

1. Find an optimal integer solution to the following integer programming problem using the cost function c(s_1,s_2,s_3,s_4,s_5) = 10s_1+100s_2+100s_3+10s_4+s_5, where

2s_1+5s_2-3s_3+s_4-2s_5=-323

s_1+7s_2+2s_3+3s_4+s_5=389

4s_1-2s_2-s_3-5s_4+3s_5=8

6.1: 4

6.2: 4

6.3: 5,7,10

7.1: 5,8

1. Find an optimal integer solution to the following integer programming problem using the cost function c(s_1,s_2,s_3,s_4,s_5) = 10s_1+100s_2+100s_3+10s_4+s_5, where

2s_1+5s_2-3s_3+s_4-2s_5=-323

s_1+7s_2+2s_3+3s_4+s_5=389

4s_1-2s_2-s_3-5s_4+3s_5=8

## Wednesday, April 21, 2010

### HW 5, what to hand in

I have received questions about what needs to be hand in for the computer problems. Here is what I think you need FOR ALL THREE PROBLEMS: The input (hypothesis, conclusions, edges, etc), the output, and a few sentences explaining what the output means and why it gives you (or not) what you want. It would be nice if you mark these clearly, so it is easier for me to find. Also, it is perfectly find to hand in printouts of what the input/output (no need to write them down with your own handwriting).

Good luck with your HW.

Saúl

## Monday, April 19, 2010

### Homework #5 correction

There was a slight problem with question #2. Here is the corrected version:

2. a) Using a computer algebra system, show that the graph with edges

{(1,2),(1,4),(1,5),(1,6),(2,3),(2,5),(2,7),(3,4),(3,6),(3,9),(5,6),(6,8),(6,9),(7,8),(8,9)}

is 3-colorable. Use the Grobner basis you find to give an explicit 3-coloring. How many colorings are there?

b) Show that if you add edge (1,3) to the graph, it is still 3-colorable, and that the coloring is now unique up to permutation of the colors.

2. a) Using a computer algebra system, show that the graph with edges

{(1,2),(1,4),(1,5),(1,6),(2,3),(2,5),(2,7),(3,4),(3,6),(3,9),(5,6),(6,8),(6,9),(7,8),(8,9)}

is 3-colorable. Use the Grobner basis you find to give an explicit 3-coloring. How many colorings are there?

b) Show that if you add edge (1,3) to the graph, it is still 3-colorable, and that the coloring is now unique up to permutation of the colors.

## Wednesday, April 14, 2010

### Homework 5 due date

I said in class, yet forgot to post on the blog, that homework #5 is due on April 22nd. By the way, I think I will assign one more homework on the 22nd that will be due May 4th. The final will also be assigned on May 4th, and will be due on the day the final is scheduled to be for our class, which is Thursday May 13th.

Also, here is the Macaulay2 file that illustrates the automated geometric proving and colorability of graphs applications from class.

I have also placed the book An Introduction to Grobner Bases by Adams and Loustaunau on reserve in the math library. The material on colorability of graphs, as well as the applications to linear programming are covered in chapter 2 of that book.

Also, here is the Macaulay2 file that illustrates the automated geometric proving and colorability of graphs applications from class.

I have also placed the book An Introduction to Grobner Bases by Adams and Loustaunau on reserve in the math library. The material on colorability of graphs, as well as the applications to linear programming are covered in chapter 2 of that book.

## Friday, April 9, 2010

### Homework #5

Problems from the text:

4.5: 3,8,11,12

4.6: 9

6.4: 3,8

Additional problems:

1. Using the Grobner basis technique from class (and of course, a computer algebra system), prove that Euler's nine point circle theorem is true. You may use either the fraction field method, or the saturation method to do this problem, but since the conclusions do not follow strictly from the hypotheses, you must use one or the other. A nice picture and discussion of the theorem is available here.

The statement is the following. Let ABC be a triangle. Then the midpoints of the sides, the feet of the altitudes, and the midpoints of the line segments joining the orthocenter (which is the intersection of the altitudes) and the vertices of the triangle, all lie on a single circle. The circle theorem of Appolonius is Euler's theorem in the case of a right triangle.

When I worked this problem out, I had 3 'u' variables, and 20 'x' variables, and therefore 20 'hypotheses'. There should be six 'conclusions' that you have to check. One way to proceed would be to consider the circle that goes through the midpoints of the sides, and show that the other 6 points are on this circle.

2. a) Using a computer algebra system, show that the graph with edges {(1,2),(1,4),(1,5),(1,6),(2,3),(2,5),(2,7),(3,6),(3,9),(5,6),(6,8),(7,8),(8,9)} is 3-colorable. Use the Grobner basis you find to give an explicit 3-coloring.

b) Show that if you add a new edge {(1,3)} to the graph, it is still 3-colorable, and that the coloring is now unique up to permutation of the colors.

3) Use the method of linear programming we learned in class to solve the following system of equations in the nonnegative integers:

3s_1+2s_2+s_3+2s_4=10

4s_1+3s_2+s_3=11

2s_1+4s_2+2s_3+s_4=10

4.5: 3,8,11,12

4.6: 9

6.4: 3,8

Additional problems:

1. Using the Grobner basis technique from class (and of course, a computer algebra system), prove that Euler's nine point circle theorem is true. You may use either the fraction field method, or the saturation method to do this problem, but since the conclusions do not follow strictly from the hypotheses, you must use one or the other. A nice picture and discussion of the theorem is available here.

The statement is the following. Let ABC be a triangle. Then the midpoints of the sides, the feet of the altitudes, and the midpoints of the line segments joining the orthocenter (which is the intersection of the altitudes) and the vertices of the triangle, all lie on a single circle. The circle theorem of Appolonius is Euler's theorem in the case of a right triangle.

When I worked this problem out, I had 3 'u' variables, and 20 'x' variables, and therefore 20 'hypotheses'. There should be six 'conclusions' that you have to check. One way to proceed would be to consider the circle that goes through the midpoints of the sides, and show that the other 6 points are on this circle.

2. a) Using a computer algebra system, show that the graph with edges {(1,2),(1,4),(1,5),(1,6),(2,3),(2,5),(2,7),(3,6),(3,9),(5,6),(6,8),(7,8),(8,9)} is 3-colorable. Use the Grobner basis you find to give an explicit 3-coloring.

b) Show that if you add a new edge {(1,3)} to the graph, it is still 3-colorable, and that the coloring is now unique up to permutation of the colors.

3) Use the method of linear programming we learned in class to solve the following system of equations in the nonnegative integers:

3s_1+2s_2+s_3+2s_4=10

4s_1+3s_2+s_3=11

2s_1+4s_2+2s_3+s_4=10

## Friday, April 2, 2010

Subscribe to:
Posts (Atom)