Topics in Advanced Combinatorics

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.

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

1. 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.
2. We will have 2 closed-book written tests (for each course). You need to pass them.

PART 1: RANDOM GRAPHS By Carlos Buitrago

1. 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.
2. 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.
3. Evolution of a random graph. Emergence of giant component and its size.
4. Chromatic number of dense random graphs.

PART 2: GAME THEORY By Diego Buitrago

1. 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.
2. 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.
3. 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.
4. Sequential games of imperfect information. Game: Russian roulette. Equilibria in Sequential Games. Game: The Centipede Game.

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