Topics in Extremal and Random Discrete Structures

We study several problems in extremal combinatorics, random graphs, and asymptotic convex geometry. Extremal combinatorics is the area of mathematics studying the behavior of the \best" discrete structure among a family of structures with respect to certain parameter, whereas probabilistic combinatorics often study the \average"

behavior shown by the most of the structures. Random graphs is one of the biggest fi?elds in probabilistic combinatorics. Asymptotic convex geometry, on the other hand, deals with geomteric problems on convex sets in \large" dimensional Euclidean space. In Chapter 2, we systematically study a natural problem in extremal graph theory, to minimize the number of edges in a graph with a ?fixed number of vertices, subject to a certain local condition: each vertex must be in a copy of a ?fixed graph H. We completely solve this problem when H is a clique, as well as more generally when H is any regular graph with degree at least about half its number of vertices. We also

characterize the extremal graphs when H is an Erdos-Renyi random graph. In Chapter 3, we consider two important questions in the well-studied theory of graphs that are F-saturated. We ?first resolve the most fundamental question of

minimizing the number of cliques of size r in a Ks-saturated graph for all sufficiently large numbers of vertices, con?rming a conjecture of Kritschgau, Methuku, Tait, and Timmons. We then make partial progress in the negative direction on a central and longstanding conjecture in graph saturation made by Tuza. In Chapter 4, we determine the maximum number of cliques of a fi?xed order in a graph with ?fixed number of edges and bounded maximum degree with complete characterization of extremal graphs, resolving a conjecture by Kirsch and Radcliffe. In Chapter 5, we generalize the notion of game chromatic number of a graph

to hypergraphs. We analyze the game chromatic number of a random k-uniform hypergraph and prove upper and lower bounds that hold w.h.p. In Chapter 6, we study a question posed by Frieze in [67] related to the existence

of a patterned perfect matching in a randomly colored graph.

In Chapter 7, we study the isomorphism problem for random hypergraphs. We show that it is polynomially time solvable for the binomial random k-uniform hypergraph Hn;p;k, for a wide range of p, and for random r-regular, k-uniform hypergraphs. Finally in Chapter 8, we study the expected volume of random polytopes generated by taking the convex hull of independent identically distributed points from a given

distribution.