PROBABILISTIC METHODS IN COMBINATORICS
| Title | ΠΙΘΑΝΟΘΕΩΡΗΤΙΚΕΣ ΜΕΘΟΔΟΙ ΣΤΗ ΣΥΝΔΥΑΣΤΙΚΗ / PROBABILISTIC METHODS IN COMBINATORICS |
| Code | ΣΜΥ016 |
| Faculty | Sciences |
| School | Mathematics |
| Cycle / Level | 2nd / Postgraduate |
| Teaching Period | Winter/Spring |
| Coordinator | Christos Pelekis |
| Common | Yes |
| Status | Active |
| Course ID | 600025953 |
Programme of Study: PMS Tmīmatos Mathīmatikṓn (2025-2030)
Registered students: 0
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| STATISTIKĪ, MONTELOPOIĪSĪ KAI YPOLOGISTIKES METHODOI | Elective Courses belonging to the selected specialization | Spring | - | 10 |
| Academic Year | 2025 – 2026 |
| Class Period | Spring |
| Faculty Instructors | |
| Weekly Hours | 3 |
| Total Hours | 39 |
| Class ID | 600268434
|
Type Of Offer
- Disciplinary Course
Course Type 2021
Specialization / Direction
Mode of Delivery
- Face to face
- Distance learning
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600268434
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
- Greek (Instruction, Examination)
Prerequisites
General Prerequisites
Basic notions of Probability Theory and Discrete Mathematics
Learning Outcomes
Upon successful completion of the course, students will:
1. know fundamental tools from Probability Theory and Combinatorics.
2. be able to solve mathematical problems using randomness.
3. practice in the design and analysis of randomized algorithms.
General Competences
- Retrieve, analyse and synthesise data and information, with the use of necessary technologies
- Adapt to new situations
- Make decisions
- Work autonomously
- Work in teams
- Generate new research ideas
- Be critical and self-critical
- Advance free, creative and causative thinking
Course Content (Syllabus)
The course aims at introducing the "probabilistic method", which is a fundamental and powerful technique for problems in discrete mathematics, among others. The basic idea behind the method is that, in order to prove the existence of an "object" having certain "desired properties", it is enough to show that a "suitable" random experiment generates the desired "object" with positive probability. We focus on methods as well as in the applications of the method in various problems of discrete mathematics.
We cover topics such as: the basic method, linearity of expectation, the second moment method, branching processes and phase transitions in random graphs, concentration inequalities, Lovász Local Lemma, entropy methods, and applications thereof in combinatorics, discrete geometry and algorithms.
Keywords
probabilistic method, concentration inequalities, combinatorics
Educational Material Types
- Notes
- Slide presentations
- Multimedia
- Book
Use of Information and Communication Technologies
Use of ICT
- Use of ICT in Course Teaching
Description
Online exercise hours.
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 39 | ||||
| Reading Assigment | 183 | ||||
| Tutorial | 13 | ||||
| Project | 20 | ||||
| Written assigments | 40 | ||||
| Exams | 5 | ||||
| Total | 300 |
Student Assessment
Description
The final grade for this course will be calculated as follows:
1. Midterm: 40%
2. Final exam: 60%.
Student Assessment methods
- Written Exam with Short Answer Questions (Formative, Summative)
- Written Exam with Extended Answer Questions (Formative, Summative)
- Written Assignment (Formative, Summative)
- Performance / Staging (Formative, Summative)
Bibliography
Additional bibliography for study
N. Alon, J. Spencer, The Probabilistic Method, 3rd Edition, John Wiley & Sons, 2008.
B. Bollobás, Random Graphs, 2nd Edition, Cambridge University Press, 2001.
S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley, 2000.
M. Molloy and B. Reed, Graph Coloring and the Probabilistic Method, Springer, 2002.
S. Roch, Modern discrete probability: An essential toolkit, Cambridge University Press, 2024.
Last Update
07-05-2025
