| An independent set in a hypergraph is a subset of the vertices which contains none of the edges. The dissertation discusses the general problem of proving the existence or nonexistence of an independent set of a certain size, based on properties of H..;The new results presented fall into two categories: combinatorial and probabilistic. On the combinatorial side, we present several theorems which give degree-sequence bounds on the independence number, improving previously known theorems.;The first of these constructions is algebraic in nature. The second employs an algorithm known as the "Nibble Method'" which has been used widely in the literature. Originally it was used to prove the existence of an ( n,r,l)-system having asymptotically the maximum number of edges; our construction additionally provides an upper bound for the size of an independent set in this system.;On the probabilistic side, we give two different randomized constructions for an (n,r,l)-system, which is an r-graph in which no two edges intersect in l or more vertices. It is shown that each of these constructions, with high probability, contains no independent set of size C r,l(nr-l log n), where Cr,l is a particular constant which we conjecture is the best possible. This improves the previous bound in [V. Rodl and E. Sinajova, Note on independent sets in Steiner systems, Random Structures and Algorithms, 1994] which uses an arbitrary constant. |
