2-intersecting permutations

MaRDI QIDQ6339788zbMATH OpenFDO

Authors K. Meagher, A. Sarobidy Razafimahatratra

Publication date 30 April 2020

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: In this paper we consider the ErdH{o}s-Ko-Rado property for both $2$-pointwise and $2$-setwise intersecting permutations. Two permutations $sigma,auinSym(n)$ are $t$-setwise intersecting if there exists a $t$-subset $S$ of $1,2,dots,n$ such that $S^{s}igma=S^{a}u$. If for each $sinS$, $s^{s}igma=s^{a}u$, then we say $sigma$ and $au$ are $t$-pointwise intersecting. We say that $Sym(n)$ has the $t$-setwise (resp. $t$-pointwise) intersecting property if for any family $mathcalF$ of $t$-setwise (resp. $t$-pointwise) intersecting permutations, $|mathcalF|leq(n-t)!t!$ (resp. $|mathcalF|leq(n-t)!$). Ellis (["Setwise intersecting families of permutation". { Journal of Combinatorial Theory, Series A}, 119(4):825-849, 2012.]), proved that for $n$ sufficiently large relative to $t$, $Sym(n)$ has the $t$-setwise intersecting property. Ellis also conjuctured that this result holds for all $ngeqt$. Ellis, Friedgut and Pilpel [Ellis, David, Ehud Friedgut, and Haran Pilpel. "Intersecting families of permutations." {Journal of the American Mathematical Society} 24(3):649-682, 2011.] also proved that for $n$ sufficiently large relative to $t$, $Sym(n)$ has the $t$-pointwise intersecting property. It is also conjectured that $Sym(n)$ has the $t$-pointwise intersecting propoperty for $ngeq2t+1$. In this work, we prove these two conjectures for $Sym(n)$ when $t=2$.

This page was built for publication: 2-intersecting permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6339788)