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.     

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.     

Erdős–Ko–Rado theorems in finite classical polar spaces

Recently, Erdős–Ko–Rado theorems in finite classical polar spaces have been derived. We present the table with the results of Pepe, Storme and Vanhove on the largest Erdős–Ko–Rado sets of generators in the finite classical polar spaces, and other more recent results by De Boeck, Ihringer and Metsch.     

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 theorems in certain semilattices

Suda (2012) extended the Erds-Ko-Rado theorem to designs in strongly regularized semilattices.In this paper we generalize Suda’s results in regularized semilattices and partition regularized semilattices,give many examples for these semilattices and obtain their intersection theorems.     

Theorems of Erdős-Ko-Rado type in geometrical settings

The original Erds-Ko-Rado problem has inspired much research. It started as a study on sets of pairwise intersecting k-subsets in an n-set, then it gave rise to research on sets of pairwise non-trivially intersecting k-dimensional vector spaces in the vector space V (n, q) of dimension n over the finite field of order q, and then research on sets of pairwise non-trivially intersecting generators and planes in finite classical polar spaces. We summarize the main results on the Erds-Ko-Rado problem in these three settings, mention the Erds-Ko-Rado problem in other related settings, and mention open problems for future research.     

Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations

Science China Mathematics - Ever since the famous Erdős-Ko-Rado theorem initiated the study of intersecting families of subsets, extremal problems regarding intersecting properties of families...     

The generalized Erdős–Falconer distance problems in vector spaces over finite fields

In this paper we study the generalized Erd?s–Falconer distance problems in the finite field setting. The generalized distances are defined in terms of polynomials, and various formulas for sizes of distance sets are obtained. In particular, we develop a simple formula for estimating the cardinality of distance sets determined by diagonal polynomials. As a result, we generalize the spherical distance problems due to Iosevich and Rudnev (2007) [13] and the cubic distance problems due to Iosevich and Koh (2008) [12]. Moreover, our results are higher-dimensional version of Vu?s work (Vu, 2008 [24]) on two dimensions. In addition, we set up and study the generalized pinned distance problems in finite fields. We give a generalization of the work by Chapman et al. (2012) [2] who studied the pinned distance problems related to spherical distances. Discrete Fourier analysis and exponential sum estimates play an important role in our proof.     

On the Erdős–Falconer distance problem for two sets of different size in vector spaces over finite fields

We consider a finite fields version of the Erd?s–Falconer distance problem for two different sets. In a certain range for the sizes of the two sets we obtain results of the conjectured order of magnitude.     

Blocking sets of Rédei type in projective Hjelmslev planes

In this paper, we introduce Rédei type blocking sets in projective Hjelmslev planes over finite chain rings. We construct, in Hjelmslev planes over chain rings of nilpotency index 2 that contain the residue field as a proper subring, the Baer subplanes associated with this subring as Rédei type blocking sets. Two further examples of Rédei type blocking sets are given for planes over Galois rings generalizing familiar constructions in projective planes over finite fields.     

On the maximum size of Erdős-Ko-Rado sets in H(2d+1, q^2)

Erd?s-Ko-Rado sets in finite classical polar spaces are sets of generators that intersect pairwise non-trivially. We improve the known upper bound for Erd?s-Ko-Rado sets in \(H(2d+1, q^2)\) for \(d>2\) and \(d\) even from approximately \(q^{d^2+d}\) to \(q^{d^2+1}.\)      

The Erdős-Szekeres theorem and congruences

The following problem of combinatorial geometry is considered. Given positive integers n and q, find or estimate a minimal number h for which any set of h points in general position in the plane contains n vertices of a convex polygon for which the number of interior points is divisible by q. For a wide range of parameters, the existing bound for h is dramatically improved.     

Classifying Erdős type spaces of higher descriptive complexity

Let ${({E_n})_{n \in \omega }}$ be a sequence of zero-dimensional subsets of the reals, ?. The Erd?s type space ? corresponding to this sequence is defined by ? = {x ∈ ? ²: x _n ∈ E _n , n ∈ω}. The most famous examples are Erd?s space, with E _n equal to the rationals for each n, and complete Erd?s space, with E _n = {0} ∪ {1/m: m ∈ ?} for each n. If all sets E _n are ${G_\delta }$ and the space ? is not zero-dimensional, then ? is known to be homeomorphic to complete Erd?s space, and if all sets E _n are ${F_{\sigma \delta }}$ , then under a mild additional condition ? is known to be homeomorphic to Erd?s space. In this paper we investigate the situation where all sets E _n are Borel sets in the same multiplicative class. Many of these spaces can be linked to the Erd?s type space with all sets E _n equal to the element of that multiplicative Borel class which absorbs the class. Furthermore, we introduce coanalytic Erd?s space and we establish a link between this space and homeomorphism groups of manifolds that leave the zero-dimensional pseudoboundary invariant. The general framework that we develop gives analogous results for nonseparable Erd?s type spaces.     

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.     

The Erdős-Heilbronn problem in Abelian groups

Solving a problem of Erdős and Heilbronn, in 1994 Dias da Silva and Hamidoune proved that ifA is a set ofk residues modulo a primep,p≥2k−3, then the number of different elements of ℤ/pℤ that can be written in the forma+a′ wherea, a′ ∈A,a∈a′, is at least 2k−3. Here we extend this result to arbitrary Abelian groups in which the order of any nonzero element is at least 2k−3. Visiting the Rényi Institute of the Hungarian Academy of Sciences. Research partially supported by Hungarian Scientific Research Grants OTKA T043623 and T043631 and the CRM, University of Montreal.     

On a problem of Erdős and Lovász: Random lines in a projective plane

Letn(k) be the least size of an intersecting family ofk-sets with cover numberk, and let _k denote any projective plane of orderk–1.Theorem There is a constant A such that ifH is a random set ofm Aklogk lines from _k then P_r(H<)0(k).Corollary If there exists a _k thenn(k)=O(klogk). These statements were conjectured by P. Erds and L. Lovász in 1973.Supported in part by NSF-DMS87-83558 and AFOSR grants 89-0066, 89-0512 and 90-0008     

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 Γ^″?Γ^′.