Erdős-Ko-Rado theorems for permutations and set partitions (Q941314): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.jcta.2007.12.004 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2022917003 / rank
 
Normal rank

Revision as of 21:17, 19 March 2024

scientific article
Language Label Description Also known as
English
Erdős-Ko-Rado theorems for permutations and set partitions
scientific article

    Statements

    Erdős-Ko-Rado theorems for permutations and set partitions (English)
    0 references
    0 references
    0 references
    4 September 2008
    0 references
    \(\text{Sym}([n])\) consists of all permutations of \([n]=\{1,2,\dots,n\}\); \({\mathcal A}\subseteq\text{Sym}([n])\) is \textsl{\(t\)-intersecting} if any \(g,h\in{\mathcal A}\) have at least \(t\) positions in common, and \textsl{\(t\)-cycle-intersecting} if any \(g,h\in{\mathcal A}\) have, when written in disjoint cycle decomposition, at least \(t\) cycles in common. \({\mathcal B}(n)\) denotes the set of all set partitions of \([n]\). Following a proof of a theorem stated in [\textit{M. Deza} and \textit{P. Frankl}, ``Erdős-Ko-Rado theorem --- 22 years later'', SIAM J. Algebraic Discrete Methods 4, 419--431 (1983; Zbl 0526.05001)], the authors prove \newline{Theorem 1.4:} Let \(t\geq2\). Suppose \({\mathcal A}\subseteq\text{Sym}([n])\) is \(t\)-cycle-intersecting, and \(n\geq n_0(t)=\text{O}(t^2)\) as \(t\to\infty\). Then \(| {\mathcal A}| \leq(n-t)!\), with equality iff \(\mathcal A\) is the stabilizer of \(t\) fixed points. In \S3, using methods they describe as ``similar to those given in'' [\textit{P. J. Cameron} and \textit{C. Y. Ku}, ``Intersecting families of permutations'', Eur.\ J. Comb.\ 24, No.\,7, 881--890 (2003; Zbl 1026.05001)], they prove \newline{Theorem 1.7:} Let \(n\geq2\). Suppose \({\mathcal A}\subseteq{\mathcal B}(n)\) is 1-intersecting. Then \(| {\mathcal A}| \leq| {\mathcal B}(n-1)| \), with equality iff \(\mathcal A\) consists of all set partitions with a fixed singleton; \newline{Theorem 1.8:} Let \(t\geq2\). Suppose \({\mathcal A}\subseteq{\mathcal B}(n)\) is \(t\)-intersecting. If \(n\geq n_0(t)\), then \(| {\mathcal A}| \leq| {\mathcal B}(n-1)| \), with equality iff \(\mathcal A\) consists of all set partitions with \(t\) fixed singletons.
    0 references
    t-intersectin
    0 references
    t-cycle-intersecting
    0 references
    intersecting families
    0 references
    permutations
    0 references
    set partitions
    0 references

    Identifiers