Induction. Basic count and count by inclusion-exclusion, recurrence (Catalan numbers) and generating functions. Sums, binomial numbers, asymptotic notation and estimates. Double Counting (Sperner's Theorem + Littlewood-Offord Problem). Graphs (basic notions, trees, cycles, bipartite graphs, pairings, Eulerian and Hamiltonian graphs, planar graphs). Introduction to the extreme theory of graphs (Mantel, Turán and the extreme number of the size 4 cycle). Introduction to Ramsey's theory (party with 6 people, higher quota for Ramsey numbers). Introduction to the discrete probability and the probabilistic method (lower quota for the Ramsey number).
Basic Information
Mandatory:
- Matousek, J; Nesetril, J, Invitation to Discrete Mathematics, Oxford University Press, 2nd edition, 2008.
- Bonn, M; A walk Through Combinatorics: An introduction to Enumeration and Graph Theory, WSPC, 4th edition, 2016.
- Graham, R; Knuth, D; Patashnik, O.; Concrete Mathematics. Fundamentals for Computer Science. Technical and Scientific Books, 1995.
Complementary:
1. Cameron, P; Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1st edition, 1994.
2. Diestel, R .; Graph Theory, Springer, 5th edition, 2017.
3. van Lint, J. H; Wilson, R. M; A Course in Combinatorics, Cambridge University Press, 2nd edition, 2001.
4. Bollobás, B; Modern Graph Theory; Springer, 1st edition, 1998.
5. Bondy, J.A .; Murty, U. S. R; Graph theory; Springer, 2008