A Class Of Kruskal-Katona Type Problems And Related Problems In Linear Spaces And Symmetry Group

The research of this thesis mainly revolves around a central result in combinatorics on finite sets—the Erd?s-Ko-Rado theorem.This theorem provides a model for an extremely broad class of extremal problems:in graph-theoretic terms,the EKR problem for a graph is to determine the orders and structures of the maximum independent sets of this graph.The resulting theorem is called the EKR theorem for this graph.An independent set of a graph is said to be non-trivial if it is not contained in any maximum independent set.The HM problem(Hilton-Milner problem)of a graph is to determine the order and structure of its maximum non-trivial independent sets,and the result is called the HM theorem of the graph.Inspired by the Daykin’s proof of the EKR theorem,we hope to obtain a simple proof for the EKR theorem in linear spaces and symmetric groups by a similar approach.For the purpose,we introduce the so-called“Kruskal-Katona type problem of graphs”,that is,given a finite simple graph G,we characterize the family of subsets H(G)of V(G),which consists of all subsets A of V(G),where A satisfies:for any vertex set B of G,if |B|≥ |A|,then the number of neighbors of B is no less than the number of neighbors of A,or if the number of neighbors of B is as large as the number of neighbors of A,then |B| ≤ |A|.The answer to this question is the so-called“Kruskal-Katona type theorem for the graph G".The main result of this thesis gives the Kruskal-Katona type theorem for two typical graphs in extremal combinatorics.One is the q-Kneser graph Kq(n,k),defined on all k-dimensional subspaces of an n-dimensional linear space over a q-element field,where n>2k;the other is the derangement graph G(n),defined on the symmetric group S(n)of degreen.These two theorems can be used to give a“Daykin’s proof" for the corresponding EKR theorems.Several famous scholars have given partial answers to the HM problem of these two types of graphs,and the methods they used are not combinatorial.Our theorem provides a complete and combinatorial proof of the HM theorem for these two types of graphs.In addition,we obtained the solution to the HM problem in graph q-Kt(n,k)for n≥ 2k+2,k≥t+2 through direct computation and estimation,which corresponds to the solution of the maximum nontrivial t-intersecting family problem in linear spaces.