| One attractive aspect of Combinatorics is that its interesting problems are sometimes closely related to applications (e.g., in Computer Science), and can be stated in elementary language. Consequently, many important open questions probably cannot be solved by elementary means, because such attacks have already been tried by many people. Instead, solutions often require more complex machinery, sometimes borrowing elements from Probability Theory, Algebra, Fourier Analysis, or even Topology. Through a series of original research results, this thesis surveys several methods from modern Extremal Combinatorics, with particular emphasis on the probabilistic approach.;We begin by using classical arguments to prove the hypergraph version of the folklore result that every non-t-colorable graph contains a copy of every t-edge tree, answering a question of Bohman, Frieze, and Mubayi. Next, we consider two problems that we solved using less common techniques. We demonstrate a method for analyzing directed graphs due to Havet and Thomasse, based on a useful extremal ordering of the vertices called a median order. This enables us to improve a bound on Constrained Ramsey numbers. Then, we solve an old problem of Erdo&huml;s, Saks, and Sos, on bounding the size of the largest induced tree in a connected triangle-free graph. The heart of the proof is an inequality about integer-weighted bipartite graphs, which we solve in an unusual way by relaxing the setting to the continuum and applying small-perturbation arguments.;We also illustrate modern interpretations of some more established methods. Using the Rodl Nibble, we prove a tight sufficient condition for finding independent transversals in locally sparse graphs, extending a result of Reed and Sudakov. Then, we apply the Regularity/Stability method of Simonovits to an old problem of Linial and Wilf, regarding the maximum number of colorings that an n-vertex graph with m edges can have. Next, we use the Differential Equations method to investigate a Ramsey-type threshold in random graphs. We conclude by studying a more complicated random graph process which has attracted recent attention, known as the Achlioptas process. Via the Layered Induction method, we determine precise thresholds for the appearance of certain fixed graphs in this process. |
