TOPICS IN DISCRETE MATHEMATICS

MATH 149A, course information

Meetings: MTWF 3:10-4:00 PM, Wellman 226. A couple of sessions will take place in Kerr Hall 451 (computer lab) and this will be announced in class. Lectures will take place MTF and the discussion session on Wednesdays, this with the exception of next week.

Instructor: Jesús A. De Loera.

email: deloera@math.ucdavis.edu

URL: http://www.math.ucdavis.edu/~ deloera/

Phone: (530)-754-7029

Office hours: Mondays,Wednesdays from 2-3pm or Fridays 1:00-2:00pm, or by appointment. My office is 580 Kerr Hall. The TA for the course is Ms. Ruriko Yoshida. Her office hours will be Wednesdays from 2:00-3:00pm (473 Kerr). The best way to contact me is via email. Please feel free to ask questions!

Text: Biggs N. Discrete Mathematics, Oxford Univ Press, Oxford, second revised edition, 1999.

Description: This course is an introduction to Discrete Mathematics via the study of classical algebraic techniques (groups, rings, and fields). The first part (149A) focuses on finite groups. We will explore the applications of groups to combinatorics, cryptography, number theory, symmetries in geometry. The goal is that the students should developed a good understanding of the key properties of a group and how they relate to finite objects such as permutations, graphs, partitions, codes, polyhedra, etc. Here is an overview of the topics we will study:

Basic Combinatorics and essential Group Theory. (5 weeks): Modular arithmetic and computations in number theory. Counting basics, the structure of permutations (the symmetric group). 15-puzzle, subgroups, coset, quotient, Lagrange's theorem.

Groups in Symmetry and Combinatorics (5 weeks) : group actions, orbits, graphs and groups, the RSA public encryption systems. Finite groups of rigid motions, Polya's theory, Burnsides lemma.

Grading policy: The course grade will be based on 4 homeworks (40 points), one midterm exam in February 16 (30 pts) and the final exam (30 points). The final exam will be comprehensive. I will assign grades based on an statistical curve of points obtained by all students. Please note that NO late homeworks will be accepted.

Prerequisites: MAT 108, 22A, 21 or equivalent and a willingness to solve many exercises and learn some mathematical software.

FIRST HOMEWORK SET: (Due Wednesday January 24th 2001) Sec 3.7: 8,9,10,18; Sec 4.8: 5,15; Sec 5.7: 14,16,17;

IMPORTANT CORRECTION: (typo in exercise 4.8 (15)) the correct formula for n>=2 is

n!n! [(1/2!)^2+(1/3!)^2+...+(1/n!)^2+2 sum (-1)^(j+k) 1/(j! k!)]
where sum runs over all pairs j,k with j different from k and j,k between 2 and n).

SECOND HOMEWORK SET: (Due February 14th 2001) Sec 6.6 (4,7) Sec 13.2 (2), Sec 13.3 (3), Sec 13.4 (3), Sec 13.5 (1,2).Sec 13.10: (16,17), In addition, we have two problems not from the book (you should be able to start with those).

a) Every even permutation can be written as the product of 3-cycles.

b) A 3-cycle is consecutive if it is of the form (k,k+1,k+2). Prove that the consecutive cycles (1,2,3),(2,3,4),...,(n-2,n-1,n) generate An

The MAPLE subroutines used in class for studying groups of permutations are available here. More information is available from MAPLE's help.

Here is a picture of the ``scrambled'' Cheap Rubik's cube (after some moves).

Third Homework set. Due Friday March 2th 14.1 (3,5), 14.2 (2), 14.3 (2,3), 14.4 (1), 14.7 (9,14).

OPTIONAL EXERCISES (Worth 8 pts). It would be very useful if you use MAPLE's group package to carry on these calculations:

a) Find all subgroups of D_4 (the group of symmetries of a square). How many are non-Abelian? How many are normal subgroups? Draw a lattice diagram for the subgroup inclusion. Do the same for S_4.

b) What are the orbits for the cheap_Rubik group on its action of the set of facets?

c) Decide whether the configuration shown in picture above is reachable from the initial situation of the cheap Rubik box by a finite sequence of moves.

d) What is the order of the subgroup of moves for the cheap Rubik box generated by moves of orders two?

e) In the RSA cryptosystem, suppose n is chosen to be 65. Find the decryption key d for e=5 and 7. For n=33 and e=3 Encrypt the following digital message M=18.

f) Prove that phi(pq)=(p-1)(q-1) when p,q are primes and phi(n) is the number of integers relatively prime with n.

The fourth and last homework. Due March 15th consists of the problems: 20.1 (3,4), 20.2 (1), 20.3 (2), 20.4 (1,3,4), 20.6 (2,3).