|
HU Credits:
4
Degree/Cycle:
1st degree (Bachelor)
Responsible Department:
Mathematics
Semester:
1st Semester
Teaching Languages:
Hebrew
Campus:
E. Safra
Course/Module Coordinator:
Dr. A Gurevich
Coordinator Office Hours:
Tue, 14-15
Teaching Staff:
Dr. Alex Gourevich
Prof Alex Lubotzky
Ilan Karpas
Avraham Morgenstern
Course/Module description:
1. Basic notions from set theory. Boolean operations,
relations and functions. Equivalence relations.
2. Combinatorics: counting problems. Binomial and multinomial
coefficients and their properties. Combinatorial identities. The binomial theorem and Newton's multinomial formula. Selection problems.
Andre's reflection method. Catalan numbers. Inclusion-exclusion principle with examples and applications: enumeration of permutations without fixed points, enumeration of maps from M onto N. Euler's phi function.
3. Recurrence relations (mainly linear). Fibonacci numbers.
Generating functions.
4. Partially ordered sets: chains, independent sets, Dilworth
theorem.
5. Graphs: paths, cycles. Eulerian paths and cycles. Detecting
graphs with Eulerian cycles. Hamiltonian paths and cycles. Degree sequence of a graph.
6. Matchings: the marriage theorem of P. Hall with applications
and extensions.
7. Trees: characteristics, properties and enumeration
(Cayley's theorem).
8. Planar graphs. Euler's formula.
9. Ramsey theorem on graphs. Upper and lower estimates on
Ramsey number.
10. Stable matchings.
Note: Not all the above topics will be covered every year.
Course/Module aims:
Providing basic notions of Discrete Math and developing the ability to solve problems.
Learning outcomes - On successful completion of this module, students should be able to:
Familiarity with fundamental concepts in Set Theory such as Cartesian Product, equivance relation.
Familiarity with ideas and fundamental concepts in Combinatorics such as permutations, transposes and combinations with or without repetitions.
Ability to deduce from the pigeon-hole principle, mathematical induction, and recursive formulas.
Familiarity with fundamental notions in Graph Theory such as connected component. the Euler sphere and the Hamilton sphere.
Ability to solve elementary problems in Set Theory, Combinatorics, and Graph Theory.
Attendance requirements(%):
none
Teaching arrangement and method of instruction:
Lecture + exercise
Course/Module Content:
1. Basic notions from set theory. Boolean operations,
relations and functions. Equivalence relations.
2. Combinatorics: counting problems. Binomial and multinomial
coefficients and their properties. Combinatorial identities. The binomial theorem and Newton's multinomial formula. Selection problems.
Andre's reflection method. Catalan numbers. Inclusion-exclusion principle with examples and applications: enumeration of permutations without fixed points, enumeration of maps from M onto N. Euler's phi function.
3. Recurrence relations (mainly linear). Fibonacci numbers.
Generating functions.
4. Partially ordered sets: chains, independent sets, Dilworth
theorem.
5. Graphs: paths, cycles. Eulerian paths and cycles. Detecting
graphs with Eulerian cycles. Hamiltonian paths and cycles. Degree sequence of a graph.
6. Matchings: the marriage theorem of P. Hall with applications
and extensions.
7. Trees: characteristics, properties and enumeration
(Cayley's theorem).
8. Planar graphs. Euler's formula.
9. Ramsey theorem on graphs. Upper and lower estimates on
Ramsey number.
10. Stable matchings.
Note: Not all the above topics will be covered every year
Required Reading:
none
Additional Reading Material:
Nati Liniel, Michal Parnas,
Discrete Mathematics (Hebrew)
Course/Module evaluation:
End of year written/oral examination 90 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 10 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %
Additional information:
none
|
