discipline

Pure Math

subject

Random structures

lecturers

György Elekes

credits

2

period

2

curriculum

Mean and second moment method. (Lower bound for R(k,k), transitive sub-tournament, Van der Warden) Algorithmic improvement of a random structure.  Construction of graphs without short cycles and with a large chromatic number.

Random graphs: threshold function, evolution around p=1/n. Largest clique, mean of chromatic number.

Quasi-random graphs (Chung-Graham-Wilson) and their spectral characterization.

Local lemma and its applications. Van der Warden numbers, lower bounds for Ramsey numbers, 2-colouring of hypergraphs.

Discrepancy. The Beck-Fiala theorem, the “6-fold variance” theorem of Spencer.

Vapnik-Cervonenkis' fundamental therem for  dimension.

literature

N. Alon, J. Spencer, The probabilistic method, Acad Press, 1992.

Form of tuition

lectures

mode of assessment

oral exam