Kneser graph is a graph whose vertices are the subsets of {1,2,..., n} with k elements, two of them being adjacent if the corresponding subsets are disjoint.
In the thesis, we define independent set, the independence number of a graph and the independence ratio of a graph. We explore how the independence number can be determined in any graph and define the maximum independent set problem. We then define Kneser graph and examine its independent sets. We present and prove the Erdős-Ko-Rado theorem, which gives an upper bound on the size of an independent set in Kneser graph. We show that this bound can always be met, which allows us to determine the independence number and independence ratio of Kneser graph. Further, we define Kneser-type graphs, which generalize Kneser graph, and, based on these, we offer an alternative definition of Kneser graph. Finally, we state and prove a theorem that establishes a lower bound on the independence ratio of Kneser-type graph. We show that in Kneser graph the lower bound from the theorem is equal to its independence ratio.
|
