چكيده انگليسي :
Dependent Random Choice Fahimeh Rahimi f rahimi@math iut ac ir 2013 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Gholam Reza Omidi romidi@cc iut ac ir Advisor Dr Sa eh Mahmoodi mahmoodi@cc iut ac ir 2010 MSC 05C15 05C55 05C65 Keywords dependent random choice probabilistic method tight path tight cycle AbstractIn this thesis we present an expanded account of the method dependent random choice This method which is an example of the celebrated Probabilistic Method can be roughly described as follows Givena dense graph G we pick a small subset T of vertices uniformly at random Then the rich set U issimply the set of common neighbors of T Intuitively it is clear that if some subset of G has only fewneighbors it is unlikely that all the members of the random set T will be chosen among these neigh bors Hence we do not expect U to contain any such subset A vast number of problems in RamseyTheory and Extremal Graph Theory deal with embedding a small or sparse graph in a dense graph To obtain such an embedding it is sometimes convenient to nd in a dense graph a large vertex sub set U which is rich in the sense that all or almost all small subsets of U have many common neighbors The last ten years have brought several striking applications of dependent random choice to Ex tremal Graph Theory Ramsey Theory Additive Combinatorics and Combinatorial Geometry In1998 Gowers used this method to prove the Szemer di s theorem on arithmetic progressions and in2001 Kostochka and R dl used dependent random choice to obtain the upper bound for the Ramseynumber of degenerate graphs There are now a growing number of papers which use this approach In 2010 Sudakov and Foxwrote a survey about this method and gave this topic a systematic treatment They attempted todescribe most of the known variants of dependent random choice and illustrated how they can be
