Description
TitleTwo problems in random graph theory
Date Created2019
Other Date2019-05 (degree)
Extent1 online resource (vii, 67 pages)
DescriptionThis thesis discusses three problems in probabilistic and extremal combinatorics.
Our first result examines the structure of the largest subgraphs of the Erdos-Renyi random graph, G(n,p), with a given matching number. This extends a result of Erdos and Gallai who, in 1959, gave a classification of the structures of the largest subgraphs of K_n with a given matching number. We show that their result extends to G(n,p) with high probability when p> 8ln(n)/n or p << 1/n, but that it does not extend (again with high probability) when $4ln(2e)/n < p< ln(n)/(3n).
The second result examines bounds on upper tails for cycles counts in G(n,p). For a fixed graph H define X_H= X_H^{n,p} to be the number of copies of H in G(n,p). It is a much studied and surprisingly difficult problem to understand the upper tail of the distribution of X_H, for example, to estimate
P(X_H > 2 E(X_H)).
The best known result for general H and p is due to Janson, Oleszkiewicz, and Rucinski, who, in 2004, proved
exp[-O_{H, eta}(M_H(n,p) ln(1/p))] (1+eta)E(X_H))
Thus they determined the upper tail up to a factor of ln(1/p) in the exponent. (The definition of M_H(n,p) can be found in Chapter 4.) There has since been substantial work to improve these bounds for particular H and p. We close the ln(1/p) gap for cycles, up to a constant in the exponent. Here the lower bound given by JOR is the truth for l-cycles when p> ln^{1/(l-2)}(n)/n.
Finally, we exhibit a counterexample to a strengthening of the Union-Closed Sets conjecture. This conjecture states that if a finite (non-empty) family of sets A is union-closed, then there is an element which belongs to at least half the sets in A. In 2001, Reimer showed that the average size of a set in a union-closed family, A, is at least (1/2) log_2 |A|. In order to do so, he showed that all union-closed families satisfy a particular condition, which in turn implies the preceding bound. Here, answering a question raised in the context of Gowers' polymath project on the union-closed sets conjecture, we show that Reimer's condition alone is not enough to imply that there is an element in at least half the sets.
NotePh.D.
NoteIncludes bibliographical references
Genretheses, ETD doctoral
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.