Erdős-Ko-Rado theorems in certain semilattices (Q2441154)

From MaRDI portal
Revision as of 05:48, 29 February 2024 by RedirectionBot (talk | contribs) (‎Removed claim: reviewed by (P1447): Item:Q1740369)
scientific article
Language Label Description Also known as
English
Erdős-Ko-Rado theorems in certain semilattices
scientific article

    Statements

    Erdős-Ko-Rado theorems in certain semilattices (English)
    0 references
    0 references
    0 references
    0 references
    21 March 2014
    0 references
    For a fixed natural number \(n\), let \([n]\) denote the set \(\{1, 2, \dots, n\}\). Let \(t\leq k\) be two natural numbers. A family \(\mathcal{A}\) of subsets of \([n]\) is \(t\)-intersecting if the cardinality of the intersection of every pair of sets in \(\mathcal{A}\) is at least \(t\), and is a \(k\)-family if every set in \(\mathcal{A}\) has cardinality \(k\). A classical result in extremal set theory is the theorem of \textit{P. Erdős} et al. [Q. J. Math., Oxf. II. Ser. 12, 313--320 (1961; Zbl 0100.01902)] which asserts that the largest possible \(t\)-intersecting \(k\)-family of subsets of \([n]\) are the families of all \(k\)-subsets containing some fixed \(t\)-subset of points whenever \(n\) is sufficiently large with respect to \(t\) and \(k\) (say, whenever \(n\geq n_0(t,k)\), where we use \(n_0(t,k)\) to denote the least integer for which the theorem is valid). In 1978, P. Frankl proved that \(n_0(t,k)= (t+1)(k-t+1)\) for \(t\geq 15\) and in general that \(n_0(t, k)\leq ct(k-t)\) where \(c\) is a constant not depending on \(t\), as had been conjectured by Erdős. \textit{R. M. Wilson} [Combinatorica 4, 247--257 (1984; Zbl 0556.05039)] proved that \(n_0(t,k)= (t+1)(k-t+1)\) in the remaining cases \(t=2,3, \dots, 14\) (with a proof valid for all \(t\)). In other words he proved the following result. Assume that \(t\leq k\) are two natural numbers. Let \(n\geq(t+1)(k-t+1)\) and \(\mathcal{A}\) be a \(t\)-intersecting \(k\)-family of subsets of \([n]\). Then \(|\mathcal{A}| \leq {n-t\choose k-t}\). If \(n > (t+1)(k-t+1)\) and \(|\mathcal{A}|={n-t\choose k-t}\), then \(\mathcal{A}\) consists of all \(k\)-subsets containing a fixed \(t\)-subset of \([n]\). \textit{S. Suda} [Discrete Math. 312, No. 10, 1827--1831 (2012; Zbl 1242.05033)] extended the Erdős-Ko-Rado theorem to designs in strongly regularized semilattices. In the paper under review, the authors generalize Suda's result in regularized semilattices and partition regularized semilattices, give many examples for theses semilattices and obtain their intersection theorems.
    0 references
    Erdős-Ko-Rado theorem
    0 references
    semilattice
    0 references
    regularized semilattice
    0 references
    strongly regularized semilattice
    0 references
    partition regularized semilattice
    0 references
    partition strongly regularized semilattice
    0 references

    Identifiers