Erdős–Ko–Rado problem for permutations with a fixed number of cycles

Let $\mathrm{Sym}(n,k)$ be the set of permutations of $[n]=\{1,\ldots,n\}$ having exactly $k$ cycles. A family $\mathcal{F}\subseteq\mathrm{Sym}(n,k)$ is intersecting if, for every $\sigma,\tau\in\mathcal{F}$ , the permutation $\sigma^{-1}\tau$ has a fixed point. Let $c(n,k)=|\mathrm{Sym}(n,k)|$ , and for $i,j\in[n]$ let $\mathcal{S}_{i,j}=\{\sigma\in\mathrm{Sym}(n,k):\sigma(i)=j\}$ . Determine whether the maximum size of an intersecting family is $\max\{c(n-1,k),c(n-1,k-1)\}$ , and characterize all maximum families; in particular, determine whether every maximum family is a star $\mathcal{S}_{i,j}$ of maximum size. This is unresolved outside the ranges currently covered by the asymptotic results.

References

Primary source

arXiv

Additional references

Intersecting families of permutations with a fixed number of cycles — arXiv — Pantangi, Venkata Raghu Tej

extremal-set-theory permutation-groups

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new preprint settles the expected largest-family and near-largest-family behavior only in limited ranges, so the full problem remains open.

The problem concerns intersecting families of permutations on $[n]$ having exactly $k$ cycles, where two permutations intersect when their quotient has a fixed point. The latest work addresses this question asymptotically, not for every $n$ and $k$ .

Known results

For the related notion of having at least $t$ common cycles, a 2014 theorem gives $|\mathcal A|\le\binom{n-t}{k-t}$ for sufficiently large $n$ , with equality characterized by fixing $t$ points; this is not the same intersection notion.

August 2026 asymptotic theorem

Pantangi and Venkata Raghu Tej prove that, for sufficiently large $n$ and $k\le n^{0.25}$ , every maximum intersecting family is a star, with size at most $\max\{c(n-1,k),c(n-1,k-1)\}$ . They also prove stability: non-centred families are at most $(2/3+\xi)$ of the largest star in this range, and at most $(1-1/e+\xi)$ when $k\le(\ln n)^d$ ; the latter bound is asymptotically sharp.

Current status (as of August 2026): The EKR and stability assertions are established in the stated asymptotic regimes, while the problem for general $n$ and $k$ remains open.

Sources

No solutions have been posted yet.