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

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.     

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.     

Multiple cross-intersecting families of signed sets

A k-signed r-set on[n]={1,…,n} is an ordered pair (A,f), where A is an r-subset of [n] and f is a function from A to [k]. Families A₁,…,Ap are said to be cross-intersecting if any set in any family Ai intersects any set in any other family Aj. Hilton proved a sharp bound for the sum of sizes of cross-intersecting families of r-subsets of [n]. Our aim is to generalise Hilton's bound to one for families of k-signed r-sets on [n]. The main tool developed is an extension of Katona's cyclic permutation argument.     

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.     

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

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.     

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.     

Erdős–Ko–Rado and Hilton–Milner theorems for two-forms

The celebrated Erd?s–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of $\{1,\dots ,n\}$ was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erd?s–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines.