|
HU Credits:
3
Degree/Cycle:
1st degree (Bachelor)
Responsible Department:
Mathematics
Semester:
1st Semester
Teaching Languages:
English
Campus:
E. Safra
Course/Module Coordinator:
Prof Eran Nevo
Coordinator Office Hours:
Teaching Staff:
Dr. Yuval Peled
Course/Module description:
Extremal problems in combinatorics: Turan’s theorem and Turan’s problem, graphs with no 4-cycles, applications of finite geometries, Erdos-Ko-Rado theorem, Sunflower theorem and conjecture, Sauer-Shelah theorem, Sperner’s theorem, simplicial complexes and Kruskal-Katona theorem, Dilworth’s theorem, symmetric chain decomposition, other partitions.
Generating functions: Basic operations on formal power series, applications to combinatorial enumeration, Catalan numbers, Mobius inversion, recurrences of finite length with constant coefficients, counts of trees and Cayley’s formula.
Partitions: Ferrers diagrams, Young tableaux, hook length formula, Robinson-Schensted correspondence, partitions of different kinds.
Permutation groups: Burnside lemma and Polya enumeration theory, the symmetric group, Stirling numbers.
Designs and codes: Steiner systems, BIBDs, existence of designs, error correcting codes – bounds and constructions.
Algebraic methods in Graph theory:
Tree-Matrix theorem, enumeration of Euler circuits (deBEST theorem) in digraphs and graphs, application to de-Bruijn sequences, Cayley’s formula revisited, the Laplacian, Gallai-Silvester theorem.
Course/Module aims:
Learning outcomes - On successful completion of this module, students should be able to:
Ability to prove and apply the theorems presented in the course.
Ability to apply correctly the mathematical methodology in the context of the course.
Acquiring the fundamentals as well as basic familiarity with the field which will assist in the understanding of advanced subjects.
Ability to understanding and explain the subjects taught in the course.
Attendance requirements(%):
0
Teaching arrangement and method of instruction:
Course/Module Content:
Extremal problems in combinatorics: Turan’s theorem and Turan’s problem, graphs with no 4-cycles, applications of finite geometries, Erdos-Ko-Rado theorem, Sunflower theorem and conjecture, Sauer-Shelah theorem, Sperner’s theorem, simplicial complexes and Kruskal-Katona theorem, Dilworth’s theorem, symmetric chain decomposition, other partitions.
Generating functions: Basic operations on formal power series, applications to combinatorial enumeration, Catalan numbers, Mobius inversion, recurrences of finite length with constant coefficients, counts of trees and Cayley’s formula.
Partitions: Ferrers diagrams, Young tableaux, hook length formula, Robinson-Schensted correspondence, partitions of different kinds.
Permutation groups: Burnside lemma and Polya enumeration theory, the symmetric group, Stirling numbers.
Designs and codes: Steiner systems, BIBDs, existence of designs, error correcting codes – bounds and constructions.
Algebraic methods in Graph theory:
Tree-Matrix theorem, enumeration of Euler circuits (deBEST theorem) in digraphs and graphs, application to de-Bruijn sequences, Cayley’s formula revisited, the Laplacian, Gallai-Silvester theorem.
Required Reading:
none
Additional Reading Material:
N.L. Biggs, Discrete Mathematics, Revised Version, Oxford, 1985
R.P. Stanley, Enumerative Combinatorics, Vol.I-II, Cambridge University
Press, 1997.
J.H. Van Lint and R.M. Wilson, A Course In Combinatorics, Cambridge University Press, 1992.
Course/Module evaluation:
End of year written/oral examination 80 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 20 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %
Additional information:
|
