In this thesis we answer questions in two related areas of combinatorics: Ramsey theory and asymptotic enumeration. In Ramsey theory we introduce a new method for finding desired structures. We find a new upper bound on the Ramsey number of a path against a kth power of a path. Using our new method and this result we obtain a new upper bound on the Ramsey number of the kth power of a long cycle. As a corollary we show that, while graphs on n vertices with maximum degree k may in general have Ramsey numbers as large as ckn, if the stronger restriction that the bandwidth should be at most k is given, then the Ramsey numbers are bounded by the much smaller value. We go on to attack an old conjecture of Lehel: by using our new method we can improve on a result of Luczak, Rodl and Szemeredi [60]. Our new method replaces their use of the Regularity Lemma, and allows us to prove that for any n > 218000, whenever the edges of the complete graph on n vertices are two-coloured there exist disjoint monochromatic cycles covering all n vertices. In asymptotic enumeration we examine first the class of bipartite graphs with some forbidden induced subgraph H. We obtain some results for every H, with special focus on the cases where the growth speed of the class is factorial, and make some comments on a connection to clique-width. We then move on to a detailed discussion of 2-SAT functions. We find the correct asymptotic formula for the number of 2-SAT functions on n variables (an improvement on a result of Bollob´as, Brightwell and Leader [13], who found the dominant term in the exponent), the first error term for this formula, and some bounds on smaller error terms. Finally we obtain various expected values in the uniform model of random 2-SAT functions.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:543116 |
| Date | January 2008 |
| Creators | Allen, Peter |
| Publisher | London School of Economics and Political Science (University of London) |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://etheses.lse.ac.uk/60/ |
Page generated in 0.0015 seconds