Topics in Advanced Combinatorics

This course is divided into 3 parts. Random graphs and Discrete Geometry are 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. Moreover, this course will give our students a global idea of the subjects studied at the master’s program "Advanced combinatorics".

Lecture 1. Binomial and uniform random graph models. 

Lecture 2. General review of the evolution of random graphs. Giant component. Threshold probability for connectivity.

Lecture 3. Proof of theorem of connectivity of G(n,p)

TEST 1 - October 19

Lecture 1.

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. Details will be explained later.

PART 1: RANDOM GRAPHS and Discrete geometry 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.
5. Examples of combinatorial geometry in the line and in the plane. Covering, coloring, and piercing. Basicnotions of convex geometry.
6. The Hahn–Banach separation theorem (finite-dimensional case for closed sets).
7. Basic results of combinatorial geometry in arbitrary dimension. Caratheodory’s, Radon’s, and Helly’stheorems.
8. Kirchberger’s theorem about separation by hyperplanes.

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

Discrete Geometry

• Imre Barany, Combinatorial Convexity.
• Jiří Matoušek, Lectures on Discrete geometry.