MATH 363 Discrete Mathematics

email: firstname.lastname@ens.fr

 // home


Last two weeks

Tutorial


1.Would you like to have a "tutorial" session (where solutions to the assignment are explained and/or more examples of material covered in class is given) instead of office hours for the last two weeks?
Yes
Yes, but only April 14, not April 7.
No
Abstained

If you did not answer "yes" above, skip the next two questions.

2.If you would like to come to the tutorial, are you able to attend (Wednesday 2:30pm-4 pm)?
Yes
No

3.Would a different time be better (even if you are able to attend)?
Yes
No

Extra topics

In the last few classes, we will see some results from other areas of discrete mathematics (all non-examinable). Which of the following would most interest you (see the table at the bottom of this page for a brief description)?

Combinatorial game theory
Four colour theorem
Counting labelled trees
Combinatorial design
Other

Combinatorial game theoryNim is a 2 player game. At the start of the game, there are 3 piles of tokens. Players take turn choosing one pile and removing a positive number of tokens from the chosen pile. The player to taken the last token wins.

In a variant of this game, there is only one pile of tokens but players must remove either 1, 7 or 10 tokens from the pile when it is their turn

We look at how to win at these and other turn based full information games.
Four colour theoremThe four colour theorem is a famous problem in graph theory. The theorem states that the regions of any map can be coloured with four colours so that regions sharing a border receives different colours

Although the theorem is simple to state. Its proof is surprisingly difficult. An interesting, but less well know, fact about this proof is that it is computer assisted. That is at some points in the proof, a computer is used to check hundreds of cases.

We look at the proof on a high level and see just how a computer is used.
Counting labelled trees Determining the number of (unlabelled) graphs with n vertices is difficult. However, determining the number of labelled graphs is easy. Suppose instead we want to determine the number of labelled trees. It turns out that there is a very nice bijection for counting labelled tree. This is know as the Prüfer sequence.

We look at the simple algorithm which turns a tree into a number and back.
Combinatorial designSuppose we building large complex system which has many "switches" which can be individually set to "on" or "off". We want to make sure our system does not break but it would take too much time to test all combination of switch states. It was noticed that if the system breaks, it is due to a combination of a small number of switches. We would like to design a series of tests (in each test, we set each switch to some state "on" or "off").

We use combinatorial designs to show that few tests are needed.

Website design modified from Sliqua taken from OSWD