# Topics in Advanced Combinatorics

#### Overview

This course is divided into 2 parts. Random graphs is taught by * Carlos Buitrago*, and Game theory is taught by

*.*

*Diego Buitrago*The goal of this course is to offer our 4th year BSc students in Computer Science a brief introduction to topics in advanced combinatorics. These topics are tipically the main research areas in which the members of our department are currently working on.

## Attendance & Marks

Attendance list.

#### Course guidelines and grading system

This is a Pass/fail course. You need to fulfill the following conditions to pass the course.

- You can not miss more than 3 lectures (medical excuse, with its respective document, is not included of course) of each of the parts of this course.
- We will have 2 closed-book written tests (for each course). You need to pass them.

#### Syllabus

PART 1: ** RANDOM GRAPHS** By Carlos Buitrago

- Models of random graphs and random sets. Properties of subsets. Monotone properties. Asymptoticalequivalence of the uniform and binomial models. Threshold probabilities. Relations between thresholdsin uniform and binomial models.
- Density of a graph. Strictly balanced and balanced graphs. Threshold probabilities for containment properties. Method of moments. Poisson limit theorem for the number of small subgraphs.
- Evolution of a random graph. Emergence of giant component and its size.
- Chromatic number of dense random graphs.

PART 2: ** GAME THEORY** By Diego Buitrago

- Two-Person Matrix Games. Example: The Prisoner’s Dilemma. Nash Equilibrium of a matrix game. Strategic Games. Definition of a strategic game. Example: Harvard’s game. Dominant and Dominated Strategies. Definition of strictly and weakly strategies. Examples.
- Nash Equilibrium. Theorem: The Elimination of Dominated Strategies. Game: Guess the number. Solving Matrix Games with Mixed Strategies. Game: Hide-and-seek. Game: Poker in jail. Game: Pionery and Vodka.
- Sequential games. Game: Choosing mayor. Game tree. Well-ordering theorem (Zermelo’s theorem). Game: Pirates and Gold Bars. Sequential games of perfect information. Binary games.
- Sequential games of imperfect information. Game: Russian roulette. Equilibria in Sequential Games. Game: The Centipede Game.

#### Recommended literature

**Random graphs:**

- N. Alon and J. H. Spencer, The probabilistic method, 2nd ed., Wiley-Interscience, New York, 2000.
- A. Frieze and M. Karonski, Introduction to random graphs, Cambridge University Press, 2016.
- S. Janson, T. Łuczak, and A. Rucinski, Random graphs, Wiley-Interscience, New York, 2000. M
- M. E. Zhukovskii and A. M. Raigorodskii, “Random graphs: models and asymptotic characteristics”, Uspekhi Mat. Nauk 70:1(421) (2015), 35–88.

**Game Theory**

- Games and Decision Making - Charalambos D. Aliprantis and Subir K. Chakrabarti
- A Course in Game Theory - Martin J. Osborne and Ariel Rubinstein