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".

On the other hand, at the end of every segment of this course (we have 3 in total), we will invite a professor from our department to talk to the students about their currently research (depending on thesituation, this meeting could take place online, given the conditions of each invited professor). Hopefully, these meetings could result in some students finding their academic advisor, or at least, understanding the kind of problems that they would like to work on their thesis.

Lecture 1. [29/09] Binomial and uniform random graph models. P(G(4,1/3) is connected). Method of moments. Threshold probability for containing a triangle in G(n,p). Increasing and decreasing properties. Threshold probability and sharp threshold. Sharp threshold of the property= "containing an isolated vertex".

Lecture 2. [06/10] Theorem on the threshold probability for containing the copy of a graph with proof.

Lecture 3. [13/10] Lemmas on the convergence on distribution for a sequence of random variables using their moments. k-th factorial moment of Poisson distribution. Lemma on computing the k-th factorial moment for sum of indicators. Theorem [Bollobas] on convergence to Poisson distribution with complete proof. Evolution of G(n,p) and notion of giant component.

Lecture 4. [20/10] Lower bound for the chromatic number of dense random graphs (p=const).

At the end of this course, you will get a grade from 1 to 10 (you need at least 3 to pass) according to the following parameters:

• Max of 1 point for class attendance (1 if you missed no more than 1. And 0,5 if you missed no more than 2)
• Max of 3 points for homeworks (3 homeworks in total)
• Max of 6 points for final exam on theory

IMPORTANT: You must pass the exam on theory in order to pass the course.

At the theoretical exam, while preparing your solutions (and only at this moment), you are permitted to use any written material (lecture and seminar notes, printed notes or books) but not electronic devices (phones, laptops). In both cases, it is not permitted to help in any way to your classmates.

The number of points you get for each activity, is either an integer x or x+0.5.

If your final grade (after the final exam) is not an integer (z+0,5), you can solve an extra problem to raise your grade to z+1. Otherwise you get just z.

PART 1: RANDOM GRAPHS (4 Lectures) 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 (4 Lectures) 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.

PART 3: DISCRETE GEOMETRY (4 Lectures) By Carlos Buitrago

1. Examples of combinatorial geometry in the line and in the plane. Covering, coloring, and piercing. Basicnotions of convex geometry.
2. The Hahn–Banach separation theorem (finite-dimensional case for closed sets).
3. Basic results of combinatorial geometry in arbitrary dimension. Caratheodory’s, Radon’s, and Helly’stheorems.
4. Kirchberger’s theorem about separation by hyperplanes.

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.