Extremal problems in pseudo-random graphs and asymptotic enumeration

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 meta-problem of describing the structure and properties of large random and pseudo-random graphs. Given a positive constant c, we call an n-vertex graph G c-Ramsey 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 pseudo-random 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 state-of-the-art result of Alon and Kostochka. For a positive integer n and a real number p in [0,1], one defines the Erdos-Renyi 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 H-free 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 non-bipartite H, the number of labeled H-free graphs on a fixed n-vertex 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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2010

Author dc:creator

• Samotij, Wojciech

Contributors dc:contributor

• Balogh, József
• West, Douglas B.
• Kostochka, Alexandr V.
• Vijay, Sujith

• combinatorics
• graphs
• graph theory
• Extremal Graph Theory
• probability
• random
• pseudo-random
• quasi-random
• random graphs
• pseudo-random graphs
• Ramsey
• Ramsey theory

Statement dc:rights

• Copyright 2010 Wojciech Samotij

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/15574

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/15574