UC San Diego

In this dissertation, we study problems concerning independent sets in hypergraphs. We try to determine the minimum independence number of a hypergraph in a certain family of hypergraphs. In Chapter 1, we introduce history of this kind of problems.

In Chapter 2, we analyze the outcome of a randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth. We show that the expected size of the output independent sets can be expressed as the solution of some differential equations and show that it is concentrated around its mean.

In Chapter 3, we establish an upper bound for the Ramsey numbers for nontrivial Berge cycles of even length and prove that this bound is essentially tight if a conjecture of Erd\"os and Simonovits is true.

In Chapter 4, we show an upper bound for the Ramsey numbers for 3-uniform loose 4-cycle, improving previous result on this problem.

In Chapter 5, we find a lower bound for the maximum size of a loose triangle-free subgraph in a uniform hypergraph in terms of its maximum degree. Moreover, we determine the magnitude of the maximum size of a loose triangle-free subgraph in the uniform random hypergraph.