Files in this item
Files  Description  Format 

application/pdf Samotij_Wojciech.pdf (912kB)  (no description provided) 
Description
Title:  Extremal problems in pseudorandom graphs and asymptotic enumeration 
Author(s):  Samotij, Wojciech 
Director of Research:  Balogh, József 
Doctoral Committee Chair(s):  West, Douglas B. 
Doctoral Committee Member(s):  Kostochka, Alexandr V.; Balogh, József; Vijay, Sujith 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  combinatorics
graphs graph theory Extremal Graph Theory probability random pseudorandom quasirandom random graphs pseudorandom graphs Ramsey Ramsey theory 
Abstract:  This dissertation tackles several questions in extremal graph theory and the theory of random graphs. It consists of three more or less independent parts that all fit into one bigger picture  the metaproblem of describing the structure and properties of large random and pseudorandom graphs. Given a positive constant c, we call an nvertex graph G cRamsey if G does not contain a clique or an independent set of size greater than c*log(n). Since all of the known examples of Ramsey graphs come from various constructions employing randomness, several researchers have conjectured that all Ramsey graphs possess certain pseudorandom properties. We study one such question  a conjecture of Erdos, Faudree, and Sos regarding the orders and sizes of induced subgraphs of Ramsey graphs. Although we do not fully resolve this conjecture, the main theorem in the first part of this dissertation, joint work with Noga Alon, Jozsef Balogh, and Alexandr Kostochka, significantly improves the previous stateoftheart result of Alon and Kostochka. For a positive integer n and a real number p in [0,1], one defines the ErdosRenyi random graph G(n,p) to be the probability distribution on the set of all graphs on the vertex set {1,...,n} such that the probability that a particular pair {i,j} of vertices is an edge in G(n,p) is p, independently of all other pairs. In the second part of this dissertation, we study the behavior of the random graph G(n,p) with respect to the property of containing large trees with bounded maximum degree. Our first main theorem, joint work with Jozsef Balogh, Bela Csaba, and Martin Pei, gives a sufficient condition on p to imply that with probability tending to 1 as n tends to infinity, G(n,p) contains all almost spanning trees with bounded maximum degree, improving a previous result of Alon, Krivelevich, and Sudakov. In the second main theorem of this part, joint work with Jozsef Balogh and Bela Csaba, we show that G(n,p) almost surely contains all almost spanning trees with bounded maximum degree even after an adversary removes asymptotically half of the edges in G(n,p). Given an arbitrary graph H, we say that a graph G is Hfree if G does not contain H as a subgraph. Edros, Frankl, and Rodl generalized a famous theorem of Erdos and Stone by proving that for every nonbipartite H, the number of labeled Hfree graphs on a fixed nvertex set, f_n(H), satisfies log_2f_n(H) < (1+o(1))ex(n,H). The case when H is bipartite has proved to be much harder. For all such H, apart from the cycles of length 4 and 6, it is not even known whether log_2f_n(H) < C*ex(n,H). The main result of the last part of this thesis, joint work with Jozsef Balogh, proves such a bound for `almost all' complete bipartite graphs. This result and the methods used to prove it have many interesting applications, some of which we study in the last chapter. 
Issue Date:  20100514 
URI:  http://hdl.handle.net/2142/15574 
Rights Information:  Copyright 2010 Wojciech Samotij 
Date Available in IDEALS:  20100514 20120515 
Date Deposited:  201005 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics