Nontrivial independent sets of bipartite graphs and cross-intersecting families

摘要

Let G(X, Y) be a connected, non-complete bipartite graph with |X| ≤ |Y|. An independent set A of G(X, Y) is said to be trivial if A; X or A; Y. Otherwise, A is nontrivial. By α(X, Y) we denote the maximum size of nontrivial independent sets of G(X, Y). We prove that if the automorphism group of G(X, Y) is transitive and primitive on X and Y, respectively, then α(X, Y) = |Y| - d(X) + 1, where d(X) is the degree of vertices in X. We also give the structures of maximum-sized nontrivial independent sets of G(X, Y). Consequently, these results give the sizes and structures of maximum-sized cross- t-intersecting families of finite sets, finite vector spaces and permutations, as well as the sizes and structures of maximum-sized cross-Sperner families of finite sets and finite vector spaces.