Extremal Set Systems With Different Restrictions

Extremal set theory, which is a branch of combinatorics, deals with the set systems given some conditions (or properties). It has applications in various branches of Mathematics and Computer Science, such as Discrete Geometry, Probability Theory and so on. The study on this subject can be traced back to 1928, when Sperner published a simply theorem. Sperner's theorem asserts that if you want to find as many subsets of an n-element set as possible, subject to the condition that no subset is contained in another, then you cannot do better than to choose all the subsets of size [n/2]. Later, Erdos, Ko, and Rado gave the tight upper bound of the set system with the property that any pair of distinct subsets of this set system has non-empty intersection, which is so-called Erdos-Ko-Rado Theorem. Both of these two theorems have been reproved in different ways and extensively studied with various kinds of objects and different kinds of restrictions. The Sperner theorem has given rise to a whole branch of the theory of partially ordered sets called Sperner theory. The Erdos-Ko-Rado Theorem, on the one hand, has led to the study on different intersection set systems by many researchers, accordingly yielded many well-known results such as Delsarte theorem, Ray Chaudhuri-Wilson theorem, Frankl-Wilson theorem, Alon-Babai-Suzuki theorem, Snevily's conjecture. On the other hand, Chvatal gave a conjecture as a generalization of Erdos-Ko-Rado theorem for the set system without a d-simplex, where a d-simplex is a collection of d+1 sets with empty intersection, but every d of which have nonempty intersection.This thesis includes two parts. The first part deals with the intersecting set systems and cross-intersecting set systems and the second part is about Chvatal's simplex conjecture.We begin Chapter 1 with basic definitions and notations for graphs and the family of subsets of n-element set or the set system on n-element set which are used throughout the thesis; then we provide a brief survey of results and some problems about various kinds of extremal set systems; at the end, we give an overview of our main results. In Chapter 2, we investigate set systems with restrictions on the set intersect-ing sizes modulo a prime number. We prove two results about cross-intersecting families, one is an extension of one result by Frankl in 1984; the other gives a stronger upper bound for two cross-intersecting families with specific intersection sizes and subset sizes. By changing the conditions slightly we derive a result of Chen and Liu in 2009. As consequence, we obtain a result aboutκ-wise inter-secting families, which gives an substantial improvement of the existing upper bounds.We consider set systems with restrictions on the set intersecting sizes mod-ulo prime powers in Chapter 3. By using separating polynomial and (p-adic) valuation, we study set systems including cross-intersecting families, uniform in-tersecting families, families on set-difference and set-symmetric-difference, and obtain the polynomial bound on their sizes. In addition, we give an improving bound for codes which will be used to derive one of our results on families with given symmetric difference sizes.Chapter 4 is devoted to Chvatal's simplex conjecture. We will prove the conjecture for the case n=κ+2. We begin with certain complementary argu-ments, then we transform the original problem into a problem on simple graphs and provide a close connection between the corresponding problem and matching theory.