The Erdős-Ko-Rado theorem for finite affine spaces

In [W.N. Hsieh, Intersection theorems for finite vector spaces, Discrete Math. 12 (1975) 1–16], Hsieh obtained the Erd?s-Ko-Rado theorem for finite vector spaces. This paper generalizes Hsieh’s result and obtains the Erd?s-Ko-Rado theorem for finite affine spaces.     

Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs

Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255-271] introduced the width w and the dual width w^* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w^*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erd?s-Ko-Rado theorem in full generality for the first two families of graphs.     

On cross t-intersecting families of sets

For all p, t with 0<p<0.11 and 1?t?1/(2p), there exists n₀ such that for all n, k with n>n₀ and k/n=p the following holds: if A and B are k-uniform families on n vertices, and |A∩B|?t holds for all A∈A and B∈B, then .     

A short proof of a cross-intersection theorem of Hilton

Families A₁,…,A_k of sets are said to be cross-intersecting if for any A_i∈A_i and A_j∈A_j, i≠j. A nice result of Hilton that generalises the Erd?s-Ko-Rado (EKR) Theorem says that if r≤n/2 and A₁,…,A_k are cross-intersecting sub-families of , then

     

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.     

Theorems of Erd?s-Ko-Rado type in polar spaces

We consider Erd?s-Ko-Rado sets of generators in classical finite polar spaces. These are sets of generators that all intersect non-trivially. We characterize the Erd?s-Ko-Rado sets of generators of maximum size in all polar spaces, except for H(4n+1,q²) with n?2.     

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.     

The Erd?s-Ko-Rado properties of set systems defined by double partitions

Let F be a family of subsets of a finite set V. The star ofFatv∈V is the sub-family {A∈F:v∈A}. We denote the sub-family {A∈F:|A|=r} by F^(r).A double partitionP of a finite set V is a partition of V into large sets that are in turn partitioned into small sets. Given such a partition, the family F(P)induced byP is the family of subsets of V whose intersection with each large set is either contained in just one small set or empty.Our main result is that, if one of the large sets is trivially partitioned (that is, into just one small set) and 2r is not greater than the least cardinality of any maximal set of F(P), then no intersecting sub-family of F(P)^(r) is larger than the largest star of F(P)^(r). We also characterise the cases when every extremal intersecting sub-family of F(P)^(r) is a star of F(P)^(r).     

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.     

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.”     

Setwise intersecting families of permutations

A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza-Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3]. Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.     

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-Ginzberg-Ziv theorem with units

Let x₁,…,x_r be a sequence of elements of Z_n, the integers modulo n. How large must r be to guarantee the existence of a subsequence x_i1,…,x_in and units α₁,…,α_n with α₁x_i1+?+α_nx_in=0? Our main aim in this paper is to show that r=n+a is large enough, where a is the sum of the exponents of primes in the prime factorisation of n. This result, which is best possible, could be viewed as a unit version of the Erd?s-Ginzberg-Ziv theorem. This proves a conjecture of Adhikari, Chen, Friedlander, Konyagin and Pappalardi.We also discuss a number of related questions, and make conjectures which would greatly extend a theorem of Gao.     

Erd?s-Ko-Rado theorems for simplicial complexes

A recent framework for generalizing the Erd?s-Ko-Rado theorem, due to Holroyd, Spencer, and Talbot, defines the Erd?s-Ko-Rado property for a graph in terms of the graph's independent sets. Since the family of all independent sets of a graph forms a simplicial complex, it is natural to further generalize the Erd?s-Ko-Rado property to an arbitrary simplicial complex. An advantage of working in simplicial complexes is the availability of algebraic shifting, a powerful shifting (compression) technique, which we use to verify a conjecture of Holroyd and Talbot in the case of sequentially Cohen-Macaulay near-cones.