A generalization of the Erdös-Ko-Rado theorem

In this note, we investigate some properties of local Kneser graphs defined in [János Körner, Concetta Pilotto, Gábor Simonyi, Local chromatic number and sperner capacity, J. Combin. Theory Ser. B 95 (1) (2005) 101-117]. In this regard, as a generalization of the Erdös-Ko-Rado theorem, we characterize the maximum independent sets of local Kneser graphs. Next, we provide an upper bound for their chromatic number.     

An Erd?s-Ko-Rado theorem for partial permutations

Let [n] denote the set of positive integers {1,2,…,n}. An r-partial permutation of [n] is a pair (A,f) where A⊆[n], |A|=r and f:A→[n] is an injective map. A set A of r-partial permutations is intersecting if for any (A,f), (B,g)∈A, there exists x∈A∩B such that f(x)=g(x). We prove that for any intersecting family A of r-partial permutations, we have .It seems rather hard to characterize the case of equality. For 8?r?n-3, we show that equality holds if and only if there exist x₀ and ε₀ such that A consists of all (A,f) for which x₀∈A and f(x₀)=ε₀.     

The Erd?s-Ko-Rado properties of various graphs containing singletons

Let G=(V,E) be a graph. For r≥1, let be the family of independent vertex r-sets of G. For v∈V(G), let denote the star. G is said to be r-EKR if there exists v∈V(G) such that for any non-star family A of pair-wise intersecting sets in . If the inequality is strict, then G is strictlyr-EKR.Let Γ be the family of graphs that are disjoint unions of complete graphs, paths, cycles, including at least one singleton. Holroyd, Spencer and Talbot proved that, if G∈Γ and 2r is no larger than the number of connected components of G, then G is r-EKR. However, Holroyd and Talbot conjectured that, if G is any graph and 2r is no larger than μ(G), the size of a smallest maximal independent vertex set of G, then G is r-EKR, and strictly so if 2r<μ(G). We show that in fact, if G∈Γ and 2r is no larger than the independence number of G, then G is r-EKR; we do this by proving the result for all graphs that are in a suitable larger set Γ^′?Γ. We also confirm the conjecture for graphs in an even larger set Γ^″?Γ^′.     

Erdos-Ko-Rado Theorems of Labeled Sets

For k = (k1, ··· , kn) ∈ Nn, 1 ≤ k1 ≤···≤ kn, let Lkr be the family of labeled r-sets on k given by Lkr := {{(a1, la1), ··· , (ar, lar)} : {a1, ··· , ar} ■[n],lai ∈ [kai],i = 1, ··· , r}. A family A of labeled r-sets is intersecting if any two sets in A intersect. In this paper we give the sizes and structures of intersecting families of labeled r-sets.     

Intersecting antichains and shadows in linear lattices

We establish a homomorphism of finite linear lattices onto the Boolean lattices via a group acting on linear lattices. By using this homomorphism we prove the intersecting antichains in finite linear lattices satisfy an LYM-type inequality, as conjectured by Erd?s, Faigle and Kern, and we state a Kruskal-Katona type theorem for the linear lattices.     

EKR type inequalities for 4-wise intersecting families

Let 1?t?7 be an integer and let F be a k-uniform hypergraph on n vertices. Suppose that |A∩B∩C∩D|?t holds for all A,B,C,D∈F. Then we have if holds for some ε>0 and all n>n₀(ε). We apply this result to get EKR type inequalities for “intersecting and union families” and “intersecting Sperner families.”     

Erd?s-Ko-Rado theorem for irreducible imprimitive reflection groups

Let Ω be a finite set, and let G be a permutation group on Ω. A subset H of G is called intersecting if for any σ, π ∈ H, they agree on at least one point. We show that a maximal intersecting subset of an irreducible imprimitive reflection group G(m, p, n) is a coset of the stabilizer of a point in {1, …, n} provided n is sufficiently large.