Text

theses

This 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))<exp[-Omega_{H, eta}(M_{H}(n,p))].
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.

ETD_9581

Ph.D.

Includes bibliographical references

doi:10.7282/t3-3kvc-dd38

ETD doctoral

The author owns the copyright to this work.