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 subtournament, 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. Quasirandom graphs (ChungGrahamWilson) and their spectral characterization. Local lemma and its applications. Van der Warden numbers, lower bounds for Ramsey numbers, 2colouring of hypergraphs. Discrepancy. The BeckFiala theorem, the “6fold variance” theorem of Spencer. VapnikCervonenkis' fundamental therem for dimension. 
literature 
N. Alon, J. Spencer, The
probabilistic method, Acad Press, 1992. 
Form of tuition 
lectures 
mode of assessment 
oral exam 