pith. sign in

arxiv: 2605.04987 · v1 · submitted 2026-05-06 · 🧮 math.CO · cs.DM

Matchings in permutations

Eduard Inozemtsev , Dmitrii Kolupaev , Andrey Kupavskii This is my paper

Pith reviewed 2026-05-08 16:46 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords permutationsmatchingsintersecting familiesHilton-Milnerderangementssymmetric groupextremal set theory
0
0 comments X

The pith

The largest families of permutations without an s-matching are fully characterized, along with a Hilton-Milner type stability result and versions for derangements.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to describe exactly the maximum size and structure of families of permutations on [n] that contain no s pairwise disjoint permutations, where two permutations intersect if there exists some x mapped to the same y by both. A sympathetic reader would care because this supplies the precise extremal examples and stability statements in the symmetric group under this natural notion of intersection, extending classical results on intersecting families to the problem of avoiding large matchings. The work also treats the restricted case of derangement families, which matters for counting or packing problems where fixed points are forbidden. If correct, the results pin down the trade-off between family size and the maximum number of non-intersecting permutations one can extract.

Core claim

We say that two permutations [n] to [n] intersect if they map some element x to the same element y. A matching in a family of permutations is a collection of pairwise disjoint permutations. In this paper, we study families of permutations with no matchings of size s. In particular, we obtain a characterization of the largest s-matching-free families and a Hilton-Milner type result. We also obtain results for the families of derangements.

What carries the argument

The s-matching-free family of permutations, where an s-matching is any collection of s permutations that are pairwise non-intersecting (no two agree on the image of any common domain element), which serves as the forbidden configuration whose avoidance determines the maximum family size.

Load-bearing premise

The definitions of intersection as sharing an image for some domain element and of a matching as a set of pairwise non-intersecting permutations are taken as given in the symmetric group on [n] for sufficiently large n.

What would settle it

For concrete small values such as n=6 and s=2, compute by enumeration or exhaustive search the size of the largest 2-matching-free family and check whether it exactly equals the size of the family consisting of all permutations that map one fixed element to one fixed value.

read the original abstract

We say that two permutations $[n]\to [n]$ intersect if they map some element $x$ to the same element $y$. A matching in a family of permutations is a collection of pairwise disjoint permutations. In this paper, we study families of permutations with no matchings of size $s$. In particular, we obtain a characterization of the largest $s$-matching-free families and a Hilton--Milner type result. We also obtain results for the families of derangements.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper defines two permutations in S_n as intersecting if they agree on the image of at least one element x. A matching is a set of pairwise non-intersecting permutations. The manuscript studies the maximum size of families of permutations with no s-matching, claims a complete characterization of the largest such families, proves a Hilton-Milner-type stability result, and obtains analogous results when restricting to derangements.

Significance. If the claimed characterizations hold, the work would extend the Erdős–Ko–Rado theorem and its stability versions to the symmetric group under the natural pointwise-agreement intersection relation. The inclusion of both the extremal characterization and the Hilton–Milner result, together with the derangement case, would constitute a coherent contribution to extremal combinatorics on permutations.

minor comments (3)
  1. [Abstract] The abstract states results for 'sufficiently large n' but does not indicate the precise threshold; the introduction or main theorems should make the dependence on n explicit.
  2. [Introduction] Notation for the intersection relation and for s-matchings is introduced in the abstract; a dedicated preliminary section with all definitions and basic observations would improve readability.
  3. [Introduction] The manuscript should include a brief comparison with existing EKR-type results for permutations (e.g., those using different intersection notions) to clarify the novelty.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. No specific major comments appear in the report, so we have no point-by-point items to address.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents standard combinatorial characterizations of maximum-size s-matching-free families of permutations in S_n, along with Hilton-Milner stability and derangement variants. All definitions (intersection via shared image, matching as pairwise disjoint permutations) are introduced explicitly as primitives and not derived from the claimed results. The extremal constructions (e.g., all permutations fixing a point) are exhibited directly and bounded via direct counting or shifting arguments typical of EKR theory; no parameters are fitted to data and then relabeled as predictions, no self-citations serve as load-bearing uniqueness theorems, and no ansatz is smuggled through prior work. The derivation chain is therefore self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of the symmetric group and the newly introduced notions of intersection and matching; no free parameters or invented entities are visible in the abstract.

axioms (2)
  • standard math Permutations are bijections from [n] to [n]
    Basic definition invoked by the setup.
  • domain assumption Two permutations intersect when they agree on the image of at least one element
    Explicitly stated in the abstract as the key relation.

pith-pipeline@v0.9.0 · 5366 in / 1155 out tokens · 60254 ms · 2026-05-08T16:46:45.956331+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 1 internal anchor

  1. [1]

    Alweiss, S

    R. Alweiss, S. Lovett, K. Wu, J. Zhang, Improved bounds for the sunflower lemma, Ann. of Math. (2) 194 (2021), no. 3, 795–815

    work page 2021

  2. [2]

    Borg, Extremal t-intersecting sub-families of hereditary families, J

    P. Borg, Extremal t-intersecting sub-families of hereditary families, J. London Math. Soc. (2) 79 (2009), no. 1, 167–185

    work page 2009

  3. [3]

    P. J. Cameron, C. Y. Ku, Intersecting families of permutations, European J. Combin. 24 (2003), no. 7, 881–890

    work page 2003

  4. [4]

    G. P. Egorychev, The solution of van der Waerden’s problem for permanents, Adv. Math. 42 (1981), no. 3, 299–305

    work page 1981

  5. [5]

    Ellis, A proof of the Cameron–Ku conjecture, J

    D. Ellis, A proof of the Cameron–Ku conjecture, J. London Math. Soc. (2) 85 (2012), no. 1, 165–190

    work page 2012

  6. [6]

    Ellis, Y

    D. Ellis, Y. Filmus, E. Friedgut, Triangle-intersecting families of graphs, J. Eur. Math. Soc. 14 (2012), no. 3, 841–885

    work page 2012

  7. [7]

    Erd˝ os, A problem on independentr-tuples, Ann

    P. Erd˝ os, A problem on independentr-tuples, Ann. Univ. Sci. Budapest. E¨ otv¨ os Sect. Math. 8 (1965), 93–95. 14

    work page 1965

  8. [8]

    Erd˝ os, C

    P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313–320

    work page 1961

  9. [9]

    D. I. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29 (1981), no. 6, 931–938, 957 (in Russian); English translation: Math. Notes 29 (1981), no. 6, 475–479

    work page 1981

  10. [10]

    Frankl, M

    P. Frankl, M. Deza, On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A 22 (1977), no. 3, 352–360

    work page 1977

  11. [11]

    Frankl, R

    P. Frankl, R. L. Graham, Intersection theorems for vector spaces, European J. Combin. 6 (1985), no. 2, 183–187

    work page 1985

  12. [12]

    Frankl, A

    P. Frankl, A. Kupavskii, Two problems on matchings in set families — in the footsteps of Erd˝ os and Kleitman, J. Combin. Theory Ser. B 138 (2019), 286–313

    work page 2019

  13. [13]

    Frankl, A

    P. Frankl, A. Kupavskii, The Erd˝ os Matching Conjecture and concentration inequalities, J. Combin. Theory Ser. B 157 (2022), 366–400

    work page 2022

  14. [14]

    Frankl, A

    P. Frankl, A. Kupavskii, The Hajnal–Rothschild problem, arXiv:2502.06699, 2025

    work page arXiv 2025

  15. [15]

    A. J. W. Hilton, E. C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 18 (1967), no. 1, 369–384

    work page 1967

  16. [16]

    Structure of $t$-Intersecting Families of Vector Spaces

    F. Ihringer, A. Kupavskii, Structure of t-intersecting families of vector spaces, arXiv:2605.02698, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  17. [17]

    Inozemtsev, A

    E. Inozemtsev, A. Kupavskii, Frankl’s diversity theorem for permutations, arXiv:2602.11796, 2026

    work page arXiv 2026

  18. [18]

    Keevash, N

    P. Keevash, N. Lifshitz, E. Long, D. Minzer, Global hypercontractivity and its applications, arXiv:2103.04604, 2021

    work page arXiv 2021

  19. [19]

    Kolupaev, A

    D. Kolupaev, A. Kupavskii, Erd˝ os Matching Conjecture for almost perfect matchings, Discrete Math. 346 (2023), 113281

    work page 2023

  20. [20]

    Kupavskii, Erd˝ os–Ko–Rado type results for partitions via spread approximations, European J

    A. Kupavskii, Erd˝ os–Ko–Rado type results for partitions via spread approximations, European J. Combin. 132 (2026), 104288

    work page 2026

  21. [21]

    Kupavskii, Intersection theorems for uniform subfamilies of hereditary families, arXiv:2311.02246, 2023

    A. Kupavskii, Intersection theorems for uniform subfamilies of hereditary families, arXiv:2311.02246, 2023

    work page arXiv 2023

  22. [22]

    Kupavskii, F

    A. Kupavskii, F. Noskov, Exact results and the structure of extremal families for the Duke–Erd˝ os forbidden sunflower problem, arXiv:2511.17142, 2025

    work page arXiv 2025

  23. [23]

    Kupavskii, D

    A. Kupavskii, D. Zakharov, Spread approximations for forbidden intersections problems, Adv. Math. 445 (2024), 109653

    work page 2024

  24. [24]

    Larose, C

    B. Larose, C. Malvenuto, Stable sets of maximal size in Kneser-type graphs, European J. Combin. 25 (2004), no. 5, 657–673

    work page 2004

  25. [25]

    Meagher, L

    K. Meagher, L. Moura, Erd˝ os–Ko–Rado theorems for uniform set-partition systems, Electron. J. Combin. 12 (2005), no. 1, Research Paper 40, 12 pp. 15

    work page 2005

  26. [26]

    Stoeckl, Lecture notes on recent improvements for the sunflower lemma, available at https://mstoeckl.com/notes/research/sunflower_notes.html

    M. Stoeckl, Lecture notes on recent improvements for the sunflower lemma, available at https://mstoeckl.com/notes/research/sunflower_notes.html

    work page

  27. [27]

    J. Wang, J. Xiao, A note on the maximum diversity of intersecting families in the symmetric group, European J. Combin. 134 (2026), 104331. 16

    work page 2026