Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Discrete Random Structures (17.DOM65L)

Native organizations units: No data

Type of studies	Title
Doctoral Academic Studies	Mathematics in Engineering (Godina: 1, Summer)
Doctoral Academic Studies	Mathematics in Engineering (Godina: 1, Summer)

General information:

Category	Scientific-professional
Scientific or art field	Teorijska i primenjena matematika
Interdisciplinary	Yes
ECTS	10

Educational goal:

Introduction of advanced discrete probability theory, and its application on discrete structures and combinatorial problems.

Educational outcome:

Upon completion of the course, the student should master the basic concepts of discrete probability theory, as well as basic methods for its application in solving combinatorial problems. Special attention will be devoted to random graphs.

Course content:

Basics of the probabilistic method. Applications of linearity of expectation and the first moment method, graph subdivision, Ramsey numbers, independent set of vertices, colorings. The second moment method. Concentration of a parameter. Chernoff bounds. Random graphs. Appearance of a fixed subgraph, connectivity, largest clique, chromatic number, giant component, phase transition. Positional games on random graphs. Pseudo-random graphs. Lovasz-Local-Lemma, applications. Discrepancy, linear and hereditary. Coding, game theory, Liar game. Derandomization, small sample spaces. Random walks. Entropy.

Teaching methods:

Lectures, with active participation of the students, discussion, etc. A student is supposed to write a seminar paper.

Literature:

Authors	Title	Year	Publisher	Language
M. Mitzenmacher, E. Upfal	Probability and computing: Randomized algorithms and probabilistic analysis	2005	Cambridge Uinversity Press	English
Noga Alon, Joel Spencer	The Probabilistic Method	2015	John Wiley & Sons, Inc	English
Svante Janson, Tomasz Luczak, Andrzej Rucinsky	Random Graphs	2000	Wiley & Sons, Inc.	English