An Erdös-Ko-Rado theorem for restricted signed sets

A restricted signed r-set is a pair （A, f）, where A lohtain in [n] = {1, 2,…, n} is an r-set and f is a map from A to [n] with f（i） ≠ i for all i ∈ A. For two restricted signed sets （A, f） and （B, g）, we define an order as （A, f） ≤ （B, g） if A C B and g｜A ： f A family .A of restricted signed sets on [n] is an intersecting antiehain if for any （A, f）, （B, g） ∈ A, they are incomparable and there exists x ∈ A ∩ B such that f（x） = g（x）. In this paper, we first give a LYM-type inequality for any intersecting antichain A of restricted signed sets, from which we then obtain ｜A｜≤ （r-1^n-1）（n-1）^r-1 if A. consists of restricted signed r-sets on [n]. Unless r = n = 3, equality holds if and only if A consists of all restricted signed r-sets （A, f） such that x0∈ A and f（x0） =ε0 for some fixed x0 ∈ [n], ε0 ∈ [n] ／ {x0}.     

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 theorem for twisted Grassmann graphs

We present a “modern” approach to the Erdös-Ko-Rado theorem for Q-polynomial distance-regular graphs and apply it to the twisted Grassmann graphs discovered in 2005 by Van Dam and Koolen.     

The exact bound in the Erdös-Ko-Rado theorem

This paper contains a proof of the following result: ifn≧(t+1)(k?t?1), then any family ofk-subsets of ann-set with the property that any two of the subsets meet in at leastt points contains at most \(\left( {\begin{array}{*{20}c} {n - t} \\ {k - t} \\ \end{array} } \right)\) subsets. (By a theorem of P. Frankl, this was known whent≧15.) The bound (t+1)(k-t-1) represents the best possible strengthening of the original 1961 theorem of Erdös, Ko, and Rado which reaches the same conclusion under the hypothesisn≧t+(k?t) \(\left( {\begin{array}{*{20}c} k \\ t \\ \end{array} } \right)^3 \) . Our proof is linear algebraic in nature; it may be considered as an application of Delsarte’s linear programming bound, but somewhat lengthy calculations are required to reach the stated result. (A. Schrijver has previously noticed the relevance of these methods.) Our exposition is self-contained.     

An Erdős-Ko-Rado theorem for finite classical polar spaces

Consider a finite classical polar space of rank \(d\ge 2\) and an integer n with \(0<n<d\). In this paper, it is proved that the set consisting of all subspaces of rank n that contain a given point is a largest Erd?s-Ko-Rado set of subspaces of rank n of the polar space. We also show that there are no other Erd?s-Ko-Rado sets of subspaces of rank n of the same size.     

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.     

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.     

An extension of the Erdős-Stone theorem

LetK _p(u₁, ..., u_p) be the completep-partite graph whoseith vertex class hasu _i vertices (lip). We show that the theorem of Erds and Stone can be extended as follows. There is an absolute constant >0 such that, for allr1, 0<1 and=">1/r, every graphG=G ⁿ of sufficiently large order |G|=n with at least

Erd?s-Ko-Rado for three sets

Fix integers k?3 and n?3k/2. Let F be a family of k-sets of an n-element set so that whenever A,B,C∈F satisfy |A∪B∪C|?2k, we have A∩B∩C≠∅. We prove that with equality only when ?_F∈FF≠∅. This settles a conjecture of Frankl and Füredi [2], who proved the result for n?k²+3k.     

The Erdös-Kac theorem for additive arithmetical semigroups

We show that the Erdös-Kac theorem for additive arithmetical semigroups can be proved under the condition that the counting function of elements has the asymptotics G(n) = q ⁿ (A + O(1/(lnn)^k) as n → ∞ with A > 0, q > 1, and arbitrary k ∈ ? and that P(n) = O(q ⁿ /n) for the number of prime elements of degree n. This improves a result of Zhang.     

An extension of the Landau-Kolmogorov inequality. Solution of a problem of Erdös

For any fixed finite interval [a, b] on the real line, an arbitrary natural numberr and σ>0, we describe the extremal function to the problem $\left\| {f^{(k)} } \right\|L_p \left[ {a,b} \right]^{ \to \sup } \left( {1 \leqslant k \leqslant r - 1, 1 \leqslant p< \infty } \right)$ over all functionsf ∈W _∞ ^r such that |f ^(r)(x)| ≤σ, |f(x)|≤1 on (?∞, ∞). Similarly, we solve the problem, raised by Paul Erdös, of characterizing the trigonometric polynomial of fixed uniform norm whose graph has maximal arc length over [a, b].     

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.