| CODE | MAT5415 | ||||||
| TITLE | Combinatorics of Finite Sets | ||||||
| UM LEVEL | 05 - Postgraduate Modular Diploma or Degree Course | ||||||
| MQF LEVEL | Not Applicable | ||||||
| ECTS CREDITS | 12 | ||||||
| DEPARTMENT | Mathematics | ||||||
| DESCRIPTION | • Systems of distinct representatives and matchings in graphs • Chains and antichains • Saturated hypergraphs • Hereditary families: Berge's decomposition and Chvatal's Conjecture, levels, Kleitman's lemma • The Four Functions Theorem • Projections (including the Sauer-Shelah Lemma for dense families and Bondy's Theorem on witness sets) • Shadows: the Kruskal-Katona Theorem • Harper's isoperimetric inequality for the discrete cube • Blocking sets, flowers and sunflowers • Intersecting families: the Erdos-Ko-Rado Theorem and beyond • Cross-intersecting families • Exact intersections and designs • Independent sets and colourings • Further topics Study-unit Aims: • To expose the student to the main results, methods and ideas in combinatorics of finite sets. • To provide the student with the necessary basic tools and training for doing independent research in combinatorial mathematics. Learning Outcomes: 1. Knowledge & Understanding: By the end of the study-unit the student will be able to: • Grasp combinatorial and set-theoretical arguments. • Understand the nature of a combinatorial problem, especially one that concerns finite sets. • See the links among certain combinatorial problems and results. 2. Skills: By the end of the study-unit the student will be able to: • Formulate and investigate original problems in the field. • Apply methods and ideas covered in the study-unit to obtain new results. • Write mathematical material confidently, accurately and efficiently, making good use of basic set theory. • Understand articles and books in discrete mathematics and some other branches of mathematics. Main Text/s and any supplementary readings: - Ian Anderson, "Combinatorics of Finite Sets". - Bela Bollobas, "Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability". - Stasys Jukna, "Extremal Combinatorics (with applications in computer science)". - Konrad Engel, "Sperner Theory". |
||||||
| ADDITIONAL NOTES | Pre-requisite Qualifications: B.Sc. with Mathematics as a main area Pre-requisite Study-units: MAT1411, MAT2413, MAT3413 |
||||||
| STUDY-UNIT TYPE | Lecture and Independent Study | ||||||
| METHOD OF ASSESSMENT |
|
||||||
| LECTURER/S | Peter Borg |
||||||
|
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints. Units not attracting a sufficient number of registrations may be withdrawn without notice. It should be noted that all the information in the description above applies to study-units available during the academic year 2025/6. It may be subject to change in subsequent years. |
|||||||