MA 4143/6143 - Home

Home
Syllabus
Schedule

Homework

# Home

MA 4143/6143, Spring 2014

#### Friday, May 2

The final exam will be cumulative, with the material since the last exam weighted somewhat more heavily.

I'll have formal office hours (in my office) Monday 12 - 2pm.
I'll be in 929 Coffee Shop Wednesday 9am - 12pm for informal office hours.
I can also arrange to meet by appointment.

#### Friday, April 4

The schedule is updated with everything we've covered through today.

Topics for the exam include:
walks, paths, and cycles in graphs
degrees and degree sequence of graphs (incl. the Handshake Lemma)
Eulerian tours
2-connected graphs, and their 2 characterizations
Trees, tree characterizations, and the Tree Growing Lemma
Spanning trees and spanning tree algorithms

#### Friday, April 4

On Problem A for this week, you may assume that you have subroutines to handle common linear algebra tasks such as row-reduction, etc.

#### Thursday, February 27

Hint on p117 #5d: Let {u, v} be your favorite edge. Let U be the set of all vertices that can be sent to u by an automorphism, and V be similar for v. Show that there are no edges inside U or V.

#### Tuesday, February 25

Note that every vertex having the same degree is not sufficient for a graph to be vertex-transitive. For a counterexample, consider the disjoint union of C4 and C5. To show the Petersen graph is vertex-transitive, you're actually going to have to exhibit automorphisms...

#### Monday, February 24

I was amused to see a graph-theoretic analysis of the role of the Ukraine in the game of Risk. The analysis is (tranlated into more formal terms) that the Ukraine vertex has high degree; and moreover that there are a large number of vertices within a walk of length 2 of Ukraine.

#### Saturday, February 15

Here are some previous exams in upper level courses that I've taught:
Exam 1 from MA 4163 Spring 2013
Exam 2 from a 4000-level Probability course
Both were in class, approximately 50-minute exams. Many of the problems are variants on results proved in class or on the homework.

Topics for the exam are simple:
Counting, and counting techniques
Induction, combinatorial bijection
Inclusion-exclusion
Binomials, permutations, and functions
Graph theory basics
Definitions: graph, isomorphism, subgraph, adjacency matrix
Basic graphs
Counting graphs (up to isomorphism)

#### Monday, February 10

For Exercise 1 on p106, assume that both married couples and dancing pairs are mixed gender.
The table arrangement problem that I mentioned is in a paper entitled "A new version of the Ménages Problem".

#### Thursday, February 6

By the way:
70! = 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000.

#### Tuesday, January 28

On 6b, note that "complement" means complement among order pairs (i,j) with i<j. That is, all i < j such that \pi(i) < \pi(j)

#### Saturday, January 25

The star on problem 6ab applies to both a and b.

#### Tuesday, January 21

On the Fibonacci problem, while it is connected with a deeper result from Chapter 12.3 (and you might find this very interesting), please don't use any unproved results in solving the problem. I recommend a fairly-straightforward mathematical induction, instead!

#### Wednesday, January 15

The first homework is now posted, as promised.
Office hours, as discussed the first day, will be Tuesdays 1-4pm, starting next week. I hope to see many of you come by.
I've added the exams to the schedule, as well as what we covered the first couple of days.

By the way, Matoušek is pronounced roughly as matt-ooo-shek. Nešetřil is pronounced roughly as nesh-et-reel. (Any actual Czech speakers reading this page, please don't make too much fun of my approximations :-) ).

#### Monday, January 13

Welcome to MA 4143/6143! The syllabus is linked at the left.