Topics in Extremal Structures and Random Graphs

We mainly studied several problems in random graphs. Random graphs is one of the biggest fields in Probabilistic combinatorics with applications to various fields in Mathematics and Computer Science. We will look at a variety of problems in this area such as the Game Chromatic Number for Hypergraphs, Rainbow matching, Colorful Hamiltonian Cycles and Random Graph Isomorphism. Extremal combinatorics studies how large or how small a collection of finite objects can be, if it has to satisfy certain restrictions. We will look at a problem of saturation in bipartite graphs in that context.

In Chapter 2, we generalize the notion of game chromatic number of a graph to hypergraphs. There are q colors available and two players Alice (A) and Bob (B) take turns to color vertices of a graph. A partial coloring is proper if no edge is monochromatic. One player, A, wishes to color all the vertices and the other player, B, wishes to prevent this. The game chromatic number χ_g(H) is the minimum number of colors for which A has a winning strategy. We consider this in the context of a random k-uniform hypergraph and prove upper and lower bounds that hold w.h.p.

In Chapter 3, we study a question posed by Prof. Frieze in [35] related to the existence of a patterned perfect matching in a randomly colored graph.

In Chapter 4, we study the isomorphism problem for random hypergraphs. We show that it is polynomially time solvable for the binomial random k-uniform hypergraph H_n,p;k, for a wide range of p, and for random r-regular, k-uniform hypergraphs where r is a constant.

In Chapter 5, we study a similar problem as in chapter 3 but for Hamilton cycles.

Finally in Chapter 6, we study the problem of edge saturation in Bipartite graphs. One of the most interesting and natural questions in this area is to determine the saturation number for the complete bipartite graph. When s = t, the saturation number and its extremal structures were determined long ago but nothing else is known for the general case. Half a decade ago, Gan, Kor´andi, and Sudakov [37] gave an asymptotically tight bound that was only off by an additive constant. We show that with some additional techniques, how the bound can be improved to achieve tightness for the case when s = t − 1.