| Due Date |
Assignment |
| Feb 2. |
- We will start our discussion of graph theory today in
class.
- Be sure to complete the beginning of semester survey online. (See
the "Tests and Quizzes" link on ella.)
- Tamar Wilson will be holding workshops to help you get up to speed with LaTex tonight and tomorrow
night in Clapp 420. She will be available at 7pm on both nights to help students with laptops install the LaTex
software on their computers. Students who do not need help installing LaTex should arrive at 7:30.
- I added a message board to our class ella site. I think this will be a good way to get LaTex questions
answered. You can ask questions and/or paste in LaTex code that is problematic.
|
| Feb 4. |
- We will explore some basic notions in graph theory and start a discussion of how to write proofs.
- Read the introduction to our book as well as the chapter
"The Colorings of Graphs" through section 1.2.2. All
course readings appear as pdf files under the "Resources" link on ella.
- You should come to class with a hard copy of a LaTex-ed document
including the following:
- The definition of a graph and of a graph
coloring.
- One real world example of a graph.
- An example of a graph that requires exactly 3 colors.
- An example of a graph on 10 vertices that requires
exactly 2 colors.
You may wish to use the following LaTex template. To see the picture you will
also need to download graph.pdf to the same
file folder as the template file. Here
is another template
file containing a more comprehensive set of examples of what you can
do
in LaTex. I would also like you to upload the LaTex source code to your ella drop box for this course.
- Please read Annalisa Crannell's Guide
to Writing in Mathematics
Classes. I think that you will find it to be a helpful resource!
|
| Feb 9. |
- We will discuss the algorithm for counting colorings in our
text. You will also begin using the computer to experiment with graph
colorings and formulate some conjectures.
- Read the rest of chapter
"The Colorings of Graphs".
- You should come to class ready to hand in your solutions to the worksheet from class on
Feb. 4. (This does not need to be LaTex-ed.)
|
| Feb 11. |
- Come to class with your conjectures witten down as precisely as possible. You will work on refining and proving them today.
- A LaTex-ed document containing the items below is due on Friday, February 13th. Please slip a hardcopy under my door by 1pm. Upload the LaTex file
to your drop box saved as yourfirstname02_13.tex.
- Give any definitions that you need in
order to state your conjectures precisely.
- Give the definition of a tree and a proof that a tree on n vertices has n-1 edges.
- Give the definition of a complete graph and a proof that a complete graph on n
vertices has n(n-1)/2 corrected formula edges.
- Write down the statements of your conjectures about chromatic polynomials.
- Include an example to illustrate each definition, conjecture, and theorem.
|
| Feb 16. |
- You should be working on your graph theory paper due Feb.
20th. The paper should include the following sections:
- An introduction containing the definition of a graph
and of a proper coloring, examples of graphs and proper colorings,
an idea of the organization of the paper.
- A section in which you describe the properties of important
families of graphs such as cycles, trees, paths, and complete
graphs. This is where you include that a tree on n vertices has
n-1 edges and that a complete graph on n vertices has n(n-1)/2 corrected formula
edges.
- A section in which you prove the major theorems of your paper. You
should be sure to give an example illustrating each theorem as well.
- A section in which you state any conjectures that you weren't
able to prove and any questions that you think are worth further
exploration. Please provide examples here as well.
- Be sure to thank anyone who helped you with any part of your
paper.
- Today in class we will start a discussion of linear
iteration and begin working in matlab. I have uploaded a program
"iterlin.m" to the resources section of ella that you can use in your
explorations. Please begin by working through the worksheet
"Linear iteration" also in the resources section of ella.
- I will also try to meet with each of you briefly to discuss the
assignment that was due 2/13.
|
| Feb 18. |
- Your paper on chromatic polynomials is due on the 20th.
- We will continue with linear iteration today in class. Your goal is to find examples illustrating the behaviors in Questions 1-4 and
conjectures related to Questions 5-9.
|
| Feb 23. |
- A LaTex-ed document containing the following items is due.
- The definition of a sequence formed by linear iteration
plus an example.
- Conjectures describing points of Types I, II, and III
along with specific examples of each.
- A conjecture for the limit of the sequence of linear
iterates when it converges, together with examples.
- We will discuss convergence rigorously today in class.
|
| Feb 25. |
- Answers to the worksheet on convergence are due Friday by 1pm.
Please write up exactly three problems to hand in, one proof and two
geometric series problems.
- We will continue to work on the linear iteration lab today in
class.
- Your paper on linear iteration (due Friday March 6) must include the
following:
- The definition of a sequence of linear iterates illustrated
using examples.
- A section in which you define the convergence of a sequence and
illustrate convergence and divergence of sequences with examples.
- Theorems, proofs and examples describing points of types I, II, and
III.
For the opportunity to receive an A, your paper must include an
additional section. Here are some ideas for an additional section:
- As rigorously as possible, describe the different ways in which
sequences of linear iterates may diverge.
- Explore the idea of a cobweb diagram as discussed in the text.
- Explore the another sequence of iterates as discussed in the
ella document "other directions.pdf".
|
| March 2. |
- We will continue to work in class today on the linear
iteration lab paper due on Friday. This is an especially good
opportunity for you to discuss ideas and questions about the proofs
classifying points (a,b) as one of the three types described in the
text.
|
| March 4. |
- We will being the Euclidean algorithm lab today in
class. Your paper on linear iteration is due Friday March 6 at 1pm.
|
March 9. |
- You should come to class with a LaTex document
including the following:
- The definition of gcd(a,b).
- A description of the Euclidean algorithm together
with an example illustrating how it works.
- A conjecture for the number of steps needed to
compute the gcd of consecutive Fibonacci numbers. (Include a proof if
you've got one!)
- Your thoughts on an upper bound for the number of
steps needed to compute gcd(a,b).
| March 11. |
- The revision of your graph theory paper is due Friday,
March 13th, at 1pm.
- Here are our goals for the day:
- Make sure that you understand the upper bound
for the number of steps taken by the Euclidean Algorithm.
- Be able to use the Euclidean Algorithm to
solve a Diophantine linear equation.
- Be able to use and understand at least one of
the matlab programs dealing with the Euclidean Algorithm.
|
| March 23. |
- We will continue our analysis of the solution to a Diophantine linear equation
given by the Euclidean Algorithm. By the end of the day you should have completed the
following things:
- You should be able to show that the integer solution of ax+by=1 given by the EA is
the integer solution closest to the origin for a specific choice of integers a and b
with gcd(a,b)=1.
- You should be able to write down the set of all integer solutions of ax+by=1 when a
and b are arbitrary integers with gcd(a,b)=1.
- You should be able to give a strategy for explaining why the EA solution is
closest to the origin in general. (You might not be able to fill in all of the
details, but you should be able to point to the places where you need to do more work
to fill in gaps.)
|
| March 25. |
- Come to class with a copy of your linear iteration paper that your classmates can
read. We will do a paper exchange today in class. I think it will be helpful for
everyone to see what other students' papers look like. This exercise should help
you get the revision of your linear iteration paper started.
- Please prepare a LaTex-ed proof of the upper bound on the number of steps needed by
the EA due Friday, March 27 at 1pm. You may wish to incorporate this into the EA
assignment which dealt with the
number of steps needed to compute the gcd of consecutive Fibonacci numbers. Can you
treat the two parts as pieces of one bigger mathematical story?
|
| March 30. |
- A LaTex-ed document discussing the use of the EA to solve a Diophantine linear
equation is due today in class. Write out as much as you can about why the EA solution
is the integer solution closest to the origin.
- We will start exploring questions about primes today in class and preparing
short oral presentations about your conjectures.
- Instructions for the lab are here.
|
| April 1. |
- We will listen to conjectures about primes from each group today.
- Your linear iteration paper redos are due this Friday, April 3 at 1pm.
|
| April 6. |
- We will start the lab on cyclic difference sets today in class.
|
| April 8. |
- Your papers on the EA are due this Friday, April 10 at 1pm. Here
are some things to think about for your paper.
- Explain how to perform the EA using your own examples.
- Give examples using the EA on consecutive Fibonacci numbers. Use
these examples to formulate a conjecture. Can you prove your
conjecture?
- Can you find an upper bound for the number of steps needed by
the EA and prove it?
- Explain how to use the EA to solve a linear Diophantine
equation using examples.
- In a specific example, show that the EA solution is closest to
the origin. Can you prove this in general?
- Remember, the goal of the paper is for you to explain what you
understand and to get feedback on what you did not understand, not for
you to write down everything we did in class. Writing down things
that you think are true but do not truly understand is not helpful.
- We will think about the set of squares mod m today in class.
You should prepare the following to hand in on Monday:
- A description of how to perform modular arithmetic, with
examples.
- Computations of the sets of squares mod m for m = 3,..., 10.
- Conjectures about patterns that you've seen in the sets of
squares mod m, stated as precisely as possible.
|
| April 13 |
- We will discuss the background necessary to prove the
conjectures that you have made about squares mod m.
|
| April 15 |
- We will wrap up our class discussion of the cyclic
difference sets lab today.
- The cyclic difference sets lab is due April 24. It should
include:
- The definition of modular arithmetic, together with examples.
- Examples of sets of squares modulo m. Choose these examples
carefully and explain how they lead you to make your conjecture
about when this set has size (m-1)/2.
- Can you prove a theorem of the form: If there are exactly (m-1)/2
nonzero squares mod m, then m is ... ? If you can prove the
theorem be sure to include all of the background that you need to
prove it. If you cannot, just write down as much of the ideas that
you know you understand for sure. This may mean that you just pick some
good examples and explain them well.
- Can you prove a theorem of the form: If D = {nonzero squares mod m}
has size (m-1)/2 and D is a cyclic difference set, then m is ... ?
|
| April 20 |
- We will start talking about polytopes today in class. By the end of the day you should know:
- the definition of a V-polytope
- the definition of an H-polytope
- the definition of a face of a polytope
-
We will begin to explore the following questions:
-
What is a 2-d analogue of the unit interval? a 3-d analogue? an n-dimensional analogue?
- Let P be a polytope and F be a face. What can we say about the normal vector of a supporting hyperplane of F? Think
about this question for the polytopes that you come up with in the question above.
|
| April 22 |
-
We will define the inner normal fan of a polytope.
- We will define the face lattice of a polytope and try to determine the face lattices of familiar polytopes.
-
We will begin to explore the following question: Let S be a set with n elements and A be its power set with partial ordering by
inclusion. Is there a polytope whose face lattice is isomorphic to A?
|
| April 27 |
- The final paper for the class will be on polytopes. It is due by noon on May 14th.
- You may choose any subset of the questions from the polytopes handouts to write up for your paper. You should clear your plan with me to make sure that you are
tackling a project of the right size and scope. To get a B-grade you need to state your conjectures carefully and clearly, giving all necessary definitions and
examples that illustrate
your logic. To receive an A-grade, your paper must also include at least some proofs.
- In our last four class periods you may work with other students to explore examples, conjectures, and proofs. You may also try building 3-d models of polytopes.
I suggest using the instructions at Jim Plank's Origami Page. You may use the models
that you build as references in your paper if they are helpful.
|
| April 29 |
- Papers on cyclic difference sets received on time will be given back today. Revisions must be received by May 6.
|