### Extremal Combinatorics

#### Course Description

#### General Competencies

Fundamental knowledge of classical combinatorics with applications for extremal problems in discrete mathematics. Fragments of extremal set theory, Ramsey theory, as well as two recent methods: the probabilistic method and the linear algebra method. Experience in linking different areas of mathematics (combinatorics, probability and linear algebra) and applying recent mathematical techniques with striking applications in computer science.

#### Learning Outcomes

- analyze various combinatorial identities.
- apply the basics of classical combinatorics to solve extremal problems.
- identify the theory and some applications of extremal set theory.
- recognize the fundamentals and some applications of Ramsey theory.
- recognize the fundamentals and some applications of the probabilistic method.
- recognize the fundamentals and some applications of the linear algebra method.

#### Forms of Teaching

**Lectures**Lectures are organized through two cycles. The first cycle consists of 6 weeks of classes and mid-term exam, a second cycle of 7 weeks of classes and final exam. Classes are conducted through a total of 15 weeks with a weekly load of 3 hours.

**Exams**Mid-term exam in the 7th week of classes and final exam in the 15th week of classes.

**Consultations**Consultations are held one hour weekly according to arrangement with students.

**Other Forms of Group and Self Study**Solving homework assignment

#### Grading Method

Continuous Assessment | Exam | |||||
---|---|---|---|---|---|---|

Type | Threshold | Percent of Grade | Comment: | Percent of Grade | ||

Homeworks | 0 % | 10 % | 0 % | 10 % | ||

Mid Term Exam: Written | 0 % | 45 % | 0 % | |||

Final Exam: Written | 0 % | 45 % | ||||

Exam: Written | 0 % | 90 % |

#### Week by Week Schedule

- CLASSICAL COMBINATORICS. Basic concepts of combinatorics. The binomial theorem. Identities involving binomial coefficients. Duble counting. Asimptotic formula for binomial coefficients. Binomial coefficients for real numbers. The multionomial theorem.
- Distribution of "n" objects in "k" boxes. Weak composition of "n". Composition of "n". Set partitions. Stirling numbers of the second kind. Bell number. Integer partitions.
- Permutations. Cycles in permutations. Number of n-permutations with a given number of cycles. Stirling numbers of the first kind. Connection between Stirling numbers of the first and Stirling numbers of the second kind. Handshaking lemma. Euler's theorem. Turan's number.
- The averaging principle. Jensen's inequality and applications for the binary trees and prefix-free codes. Bounds on intersection size. The principle of inclusion and exclusion for sets and for arbitrary set functions. Application for the derangements. Application for the Stirling numbers of the second kind.
- The pigeonhole principle. Some applications for graphs. Erdos-Szekeres theorem. Mantel's theorem. Turan's theorem. Dirichlet's theorem of rational approximations of irrational numbers. The weight shifting argument.
- Systems of distinct representatives. Hall's marriage theorem. Application for Latin rectangles. Application for decomposition of doubly stohastic matrices. Min-max theorems.
- Mid-term exam.
- EXTREMAL SET THEORY. Sunflower lemma. Modifications: relaxed core, relaxed disjointness. Application for the number of minterms of a Boolean function. Application for small depth formulas.
- Intersecting families. The Erdos-Ko-Rado theorem. Finite ultrafilters. Maximal intersectiong families. A Helly type result.
- Posets. Chains and antichains. Decomposition of posets. Symmetric chains in power sets. Application for memory allocation problem. Sperner's theorem for antichains in power sets. LYM inequality. Bollobas's theorem.
- FRAGMENTS OF RAMSEY THEORY. Colorings and Ramsey numbers. Ramsey's theorems for finite graphs. Generalizations. Ramsey's theorem for sets. Shur's theorem. Geometric applications: Erdos-Szekeres theorem for convex polygons and some applications in combinatorial geometry.
- FRAGMENTS OF THE PROBABILISTIC METHOD. Applications of counting sieve: for Ramsey numbers, Van der Waerden's theorem, tournaments, 2-edge coloring of bipartite graphs, 2-coloring of hypergraphs, Erdos-Ko-Rado theorem.
- Applications of linearity of expectation: Hamilton paths in tournaments, graphs splitting, sum-free sets, the independence number of a graph. Probability inclusion–exclusion principle. The second moment method: estimating the middle binomial coefficient. Treshold for cliques. Alterations and applications of Markov's inequality.
- FRAGMENTS OF THE LINEAR ALGEBRA METHOD. Spaces of incidence vectors. Fisher's inequality. Spaces of polynomials. Two-distance sets. Combinatorics of linear spaces. Orthogonality and rank arguments.
- Final exam.

#### Study Programmes

##### University graduate

#### Literature

*Extremal Combinatorics With Applications in Computer Science*, Springer

*A Walk Through Combinatorics*, World scientific

*Extremal Combinatorial Problems and Their Applications*, Kluwer Academic Publishers

*A course in combinatorics*, Cambridge University Press

*Combinatorial Problems and Exercises*, AMS Chelsea Publishing

#### Lecturers in Charge

#### Grading System

**ID**72538

**4**ECTS

**L1**English Level

**L1**e-Learning

**45**Lecturers

**0**Exercises

**0**Laboratory exercises

#### General

**85**Excellent

**70**Very Good

**55**Good

**45**Acceptable