Premium
Dependent random choice
Author(s) -
Fox Jacob,
Sudakov Benny
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20344
Subject(s) - struct , combinatorics , simple (philosophy) , random graph , probabilistic logic , mathematics , graph , discrete mathematics , extremal graph theory , computer science , voltage graph , line graph , statistics , philosophy , epistemology , programming language
We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this survey we discuss some of them. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011