| CODE | MAT3415 | ||||||||
| TITLE | Probabilistic and Extremal Combinatorics | ||||||||
| UM LEVEL | 03 - Years 2, 3, 4 in Modular Undergraduate Course | ||||||||
| MQF LEVEL | 6 | ||||||||
| ECTS CREDITS | 4 | ||||||||
| DEPARTMENT | Mathematics | ||||||||
| DESCRIPTION | Probabilistic Combinatorics: - Finite probability spaces - Independent events and independent random experiments - Random variables: expectation, variance, independence - Alterations and randomised algorithms - Lovasz local lemma - Threshold Functions - Applications in combinatorics: Ramsey numbers, van der Waerden numbers, 2-colourable uniform families, (r,s)-systems, bipartite random graphs, bipartite sub-graphs, tournaments, Turan's theorem, independence numbers, domination numbers. Extremal Combinatorics: - Chains and antichains - Shadows - Intersecting and cross-intersecting families - Exact intersections and designs - Hereditary families Study-unit Aims: - To demonstrate how tools from probability theory can be used to prove combinatorial results. - To equip the student with knowledge of important ideas and results in extremal set theory (the study of how large/small a system of finite sets can be under certain constraints), especially ideas and results that gave rise to various combinatorial results. Learning Outcomes: 1. Knowledge & Understanding: By the end of the study-unit the student will be able to: - Grasp combinatorial and set-theoretical arguments. - Know the nature of a combinatorial problem, especially one that concerns finite sets. - See links among certain combinatorial problems and results. - Have a foundation to follow articles and books in discrete mathematics and some other branches of mathematics. 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. Main Text/s and any supplementary readings: - Mitzenmacher M. and Upfal E., Probability and Computing (Randomized Algorithms and Probabilistic Analysis), Cambridge University Press, 2005. - Alon N. and Spencer J.H., The Probabilistic Method, John Wiley & Sons, 2011. - Ian Anderson, Combinatorics of Finite Sets, Courier Dover Publications, 1987. - Bela Bollobas, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, 1986. - Konrad Engel, Sperner Theory, Cambridge University Press, 1997. - Stasys Jukna, Extremal Combinatorics (with applications in computer science), Springer, 2011. |
||||||||
| ADDITIONAL NOTES | Follows from: MAT2413 and MAT1411 Leads to: MAT3411 |
||||||||
| 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 2023/4. It may be subject to change in subsequent years. |
|||||||||