pith. sign in

arxiv: 2607.00318 · v1 · pith:I7T6WIBTnew · submitted 2026-07-01 · 🧮 math.CO · cs.DM

A Complete Intersection Theorem for Large Permutation Groups

Nathan Keller , Andrey Kupavskii , Noam Lifshitz , Ohad Sheinfeld This is my paper

Pith reviewed 2026-07-02 11:19 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords intersecting familiespermutationssymmetric groupextremal combinatoricsDeza-Frankl problemfixed points
0
0 comments X

The pith

Beyond a finite threshold the largest t-intersecting families of permutations are those with many fixed points in an initial segment.

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

This paper shows that for any fixed t there is a number n0 such that when the number of elements n exceeds n0 the biggest families of permutations where any two agree on at least t positions are the families F_n,t,r. These families collect all permutations that have at least t plus r fixed points among the first t plus 2r positions. A reader would care because this gives the exact maximum size and the structure of the largest such families, solving a 1977 problem for all large cases. The result mirrors the classical complete intersection theorem but for the symmetric group instead of subsets.

Core claim

There exists an n0 in natural numbers such that for every n greater than n0 and every t between 1 and n the maximum size of a t-intersecting family in the symmetric group S_n is attained by one of the families F_{n,t,r} consisting of those permutations whose set of fixed points intersects the initial segment {1 to t+2r} in at least t+r points.

What carries the argument

The families F_{n,t,r} that require permutations to fix enough points in a prefix of length t+2r.

If this is right

  • The maximum size is explicitly known for large n.
  • Only these families achieve the bound for large n.
  • The Deza-Frankl problem has an essentially complete solution for permutations when n is large.
  • For each fixed t only finitely many n require separate treatment.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Explicit bounds on n0 would allow checking all remaining cases by computer.
  • The same phenomenon may appear in other finite groups or for other notions of intersection.
  • One could try to find the exact n0(t) by examining small cases.

Load-bearing premise

A finite threshold n0 exists after which the listed families are always the maximum ones.

What would settle it

A t-intersecting family in S_n for some large n whose size exceeds that of every F_{n,t,r}.

read the original abstract

A family of permutations is called $t$-intersecting if any two permutations in the family agree on at least $t$ elements. We prove that there exists $n_0 \in \mathbb{N}$ such that for any $n>n_0$ and any $1 \leq t \leq n$, the maximum size of a $t$-intersecting family in $S_n$ is obtained by one of the families $\mathcal{F}_{n,t,r}=\{\sigma \in S_n: |\mathrm{Fixed}(\sigma) \cap \{1,2,\ldots,t+2r\}|\geq t+r\}$, where $\mathrm{Fixed}(\sigma)$ is the set of fixed points of $\sigma$. This proves an analogue of the classical Complete Intersection Theorem for large permutation groups, thus providing an essentially complete solution of the Deza-Frankl intersection problem for permutations (1977).

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

1 major / 0 minor

Summary. The manuscript proves that there exists n0 ∈ ℕ such that for all n > n0 and 1 ≤ t ≤ n, the largest t-intersecting subfamily of S_n is one of the families F_{n,t,r} = {σ ∈ S_n : |Fixed(σ) ∩ {1,…,t+2r}| ≥ t+r}. This is presented as an analogue of the classical complete intersection theorem and an essentially complete solution to the 1977 Deza–Frankl problem on intersecting permutation families.

Significance. If the claimed stability threshold holds, the result supplies the first structural classification of extremal t-intersecting families in S_n for all sufficiently large n, resolving a long-standing question in extremal set theory for the symmetric group.

major comments (1)
  1. [Main Theorem (abstract statement)] The central claim rests on the existence of a finite (though possibly ineffective) threshold n0(t) after which all other constructions are dominated by the listed fixed-point families. The abstract asserts this threshold without exhibiting either an explicit bound or the compression/stability argument that produces it; verification that the argument yields a finite n0 rather than an asymptotic statement therefore cannot be performed from the given text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their report and the opportunity to clarify the manuscript. We address the single major comment below.

read point-by-point responses

  1. Referee: [Main Theorem (abstract statement)] The central claim rests on the existence of a finite (though possibly ineffective) threshold n0(t) after which all other constructions are dominated by the listed fixed-point families. The abstract asserts this threshold without exhibiting either an explicit bound or the compression/stability argument that produces it; verification that the argument yields a finite n0 rather than an asymptotic statement therefore cannot be performed from the given text.

    Authors: The full manuscript contains a complete proof that n0 is finite. The argument first establishes a stability result via the compression method: any t-intersecting family whose size exceeds that of the largest F_{n,t,r} by more than a controlled error term must be contained in (or very close to) one of the fixed-point families. The error terms arise from counting permutations with a bounded number of additional fixed points or derangements on the remaining elements; these are bounded by explicit (though large) functions of n and t that are o( the main term difference between the F families and any competing construction). The threshold n0 is then taken large enough so that these error terms are strictly smaller than the size gap between the F families and all other candidates; because the gap grows linearly in n while the errors are at most exponential in a fixed function of t, such a finite n0 exists. We agree that the abstract is terse on this point and will add a short paragraph in the introduction (and a remark after the statement of the main theorem) explicitly noting that the stability-plus-size-comparison argument produces a finite threshold rather than a purely asymptotic statement. revision: partial

Circularity Check

0 steps flagged

No circularity: theorem asserts existence of n0 via independent combinatorial argument

full rationale

The paper states a structural existence result: for all sufficiently large n there exists n0(t) such that the maximum t-intersecting families in S_n are precisely the listed fixed-point families F_{n,t,r}. This is framed as an analogue of the classical Erdős–Ko–Rado-type Complete Intersection Theorem and a solution to the 1977 Deza–Frankl problem. No parameters are fitted to data, no quantity is defined in terms of itself, no load-bearing step reduces to a self-citation whose validity depends on the present claim, and no known empirical pattern is merely renamed. The derivation is therefore self-contained against external combinatorial benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result is a pure existence theorem for large n relying on standard combinatorial definitions and group actions. No free parameters, invented entities, or non-standard axioms are mentioned.

axioms (1)
  • domain assumption Standard definition of t-intersecting families via agreement on at least t points and the action of S_n on [n].
    Basic setup of the problem in permutation group theory.

pith-pipeline@v0.9.1-grok · 5687 in / 1242 out tokens · 45258 ms · 2026-07-02T11:19:41.196137+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

42 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    Khachatrian

    Rudolf Ahlswede and Levon H. Khachatrian. The complete nontrivial-intersection theorem for systems of finite sets.J. Comb. Theory A, 76(1):121–138, 1996

    1996

  2. [2]

    Khachatrian

    Rudolf Ahlswede and Levon H. Khachatrian. The complete intersection theorem for systems of finite sets.European J. Combin., 18(2):125–136, 1997

    1997

  3. [3]

    Improved bounds for the sunflower lemma.Ann

    Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma.Ann. of Math. (2), 194(3):795–815, 2021

    2021

  4. [4]

    Extremal𝑡-intersecting sub-families of hereditary families.J

    Peter Borg. Extremal𝑡-intersecting sub-families of hereditary families.J. Lond. Math. Soc., 79:167–185, 2009

    2009

  5. [5]

    Complexity measures and decision tree complexity: a survey.Theor

    Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey.Theor. Comput. Sci., 288(1):21–43, 2002

    2002

  6. [6]

    Peter J. Cameron. Metric and geometric properties of sets of permutations. InAlgebraic, extremal and metric combinatorics, 1986 (Montreal, PQ, 1986), volume 131 ofLondon Math. Soc. Lecture Note Ser., pages 39–53. Cambridge Univ. Press, Cambridge, 1988

    1986

  7. [7]

    Cameron and Cheng Y

    Peter J. Cameron and Cheng Y. Ku. Intersecting families of permutations.European J. Combin., 24(7):881–890, 2003

    2003

  8. [8]

    Uniqueness for 2-intersecting families of permutations and perfect matchings.Algebraic Combinatorics, 9(2):357–377, 2026

    Gilad Chase, Neta Dafni, Yuval Filmus, and Nathan Lindzey. Uniqueness for 2-intersecting families of permutations and perfect matchings.Algebraic Combinatorics, 9(2):357–377, 2026

    2026

  9. [9]

    Exchangeable pairs and Poisson approximation.Probability Surveys, 2:64–106, 2005

    Sourav Chatterjee, Persi Diaconis, and Elizabeth Meckes. Exchangeable pairs and Poisson approximation.Probability Surveys, 2:64–106, 2005

    2005

  10. [10]

    Complexity measures on the symmetric group and beyond (extended abstract)

    Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals. Complexity measures on the symmetric group and beyond (extended abstract). Inproceedings of ITCS, volume 185 ofLIPIcs, pages 87:1–87:5, 2021

    2021

  11. [11]

    On the hardness of approximating minimum vertex cover.Ann

    Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover.Ann. of Math. (2), 162(1):439–485, 2005

    2005

  12. [12]

    Stability for𝑡-intersecting families of permutations.J

    David Ellis. Stability for𝑡-intersecting families of permutations.J. Combin. Theory Ser. A, 118(1):208–227, 2011

    2011

  13. [13]

    Triangle-intersecting families of graphs.J

    David Ellis, Yuval Filmus, and Ehud Friedgut. Triangle-intersecting families of graphs.J. Eur. Math. Soc., 14(3):841–885, 2012

    2012

  14. [14]

    Intersecting families of permutations.J

    David Ellis, Ehud Friedgut, and Haran Pilpel. Intersecting families of permutations.J. Amer. Math. Soc., 24(3):649–682, 2011

    2011

  15. [15]

    Stability versions of Erd˝ os-Ko-Rado type theorems via isoperimetry.J

    David Ellis, Nathan Keller, and Noam Lifshitz. Stability versions of Erd˝ os-Ko-Rado type theorems via isoperimetry.J. Eur. Math. Soc. (JEMS), 21(12):3857–3902, 2019

    2019

  16. [16]

    Stability for the complete intersection theo- rem, and the forbidden intersection problem of Erd˝ os and S´ os.J

    David Ellis, Nathan Keller, and Noam Lifshitz. Stability for the complete intersection theo- rem, and the forbidden intersection problem of Erd˝ os and S´ os.J. Eur. Math. Soc., 26:1611– 1654, 2024

    2024

  17. [17]

    Forbidden intersection problems for families of linear maps.Discrete Analysis, 19:1–32, 2023

    David Ellis, Guy Kindler, and Noam Lifshitz. Forbidden intersection problems for families of linear maps.Discrete Analysis, 19:1–32, 2023

    2023

  18. [18]

    Approximation by juntas in the symmetric group, and for- bidden intersection problems.Duke Math

    David Ellis and Noam Lifshitz. Approximation by juntas in the symmetric group, and for- bidden intersection problems.Duke Math. J., 171(7):1417–1467, 2022

    2022

  19. [19]

    Intersection theorems for systems of finite sets

    Paul Erd˝ os, Chao Ko, and Richard Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2), 12:313–320, 1961

    1961

  20. [20]

    The Erd˝ os-Ko-Rado theorem is true for𝑛=𝑐𝑘𝑡

    Peter Frankl. The Erd˝ os-Ko-Rado theorem is true for𝑛=𝑐𝑘𝑡. InCombinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, volume 18 ofColloq. Math. Soc. J´ anos Bolyai, pages 365–375. North-Holland, Amsterdam-New York, 1978

    1976

  21. [21]

    Erd˝ os-Ko-Rado theorem with conditions on the maximal degree.J

    Peter Frankl. Erd˝ os-Ko-Rado theorem with conditions on the maximal degree.J. Combin. Theory Ser. A, 46(2):252–263, 1987

    1987

  22. [22]

    On the maximum number of permutations with given maxi- mal or minimal distance.J

    P´ eter Frankl and Mikhail Deza. On the maximum number of permutations with given maxi- mal or minimal distance.J. Combinatorial Theory Ser. A, 22(3):352–360, 1977

    1977

  23. [23]

    Beyond the Erd¨ os-Ko-Rado theorem.J

    Peter Frankl and Zolt´ an F¨ uredi. Beyond the Erd¨ os-Ko-Rado theorem.J. Comb. Theory A, 56(2):182–194, 1991

    1991

  24. [24]

    Peter Frankl and Ronald L. Graham. Intersection theorems for vector spaces.Eur. J. Comb., 6(2):183–187, 1985

    1985

  25. [25]

    The Hajnal–Rothschild problem, arxiv:2502.06699

    Peter Frankl and Andrey Kupavskii. The Hajnal–Rothschild problem, arxiv:2502.06699. 2025

    work page arXiv 2025

  26. [26]

    Invitation to intersection problems for finite sets.J

    Peter Frankl and Norihide Tokushige. Invitation to intersection problems for finite sets.J. Combin. Theory Ser. A, 144:157–211, 2016. A COMPLETE INTERSECTION THEOREM FOR LARGE PERMUTATION GROUPS 69

    2016

  27. [27]

    On the measure of intersecting families, uniqueness and stability.Combina- torica, 28(5):503–528, 2008

    Ehud Friedgut. On the measure of intersecting families, uniqueness and stability.Combina- torica, 28(5):503–528, 2008

    2008

  28. [28]

    Anthony J. W. Hilton and Eric C. Milner. Some intersection theorems for systems of finite sets.Quart. J. Math. Oxford Ser. (2), 18:369–384, 1967

    1967

  29. [29]

    Hypercontractivity for global functions and sharp thresholds.J

    Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer. Hypercontractivity for global functions and sharp thresholds.J. Amer. Math. Soc., 37:245–279, 2024

    2024

  30. [30]

    The junta method for hypergraphs and the Erd˝ os-Chv´ atal simplex conjecture.Adv

    Nathan Keller and Noam Lifshitz. The junta method for hypergraphs and the Erd˝ os-Chv´ atal simplex conjecture.Adv. Math., 392:107991:1–95, 2021

    2021

  31. [31]

    On t-intersecting families of permutations.Advances in Mathematics, 445:109650, 2024

    Nathan Keller, Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld. On t-intersecting families of permutations.Advances in Mathematics, 445:109650, 2024

    2024

  32. [32]

    Kupavskii

    A. Kupavskii. Delta-system method: a survey, arxiv:2508.20132

    work page arXiv

  33. [33]

    Intersection theorems for uniform subfamilies of hereditary families, arxiv:2311.02246

    Andrey Kupavskii. Intersection theorems for uniform subfamilies of hereditary families, arxiv:2311.02246. 2023

    work page arXiv 2023

  34. [34]

    An almost complete𝑡-intersection theorem for permutations.arXiv preprint arXiv:2405.07843, 2024

    Andrey Kupavskii. An almost complete𝑡-intersection theorem for permutations.arXiv preprint arXiv:2405.07843, 2024

    work page arXiv 2024

  35. [35]

    Erd˝ os-Ko-Rado type results for partitions via spread approximations.Eur

    Andrey Kupavskii. Erd˝ os-Ko-Rado type results for partitions via spread approximations.Eur. J. Comb., 132:104288, 2026

    2026

  36. [36]

    Spread approximations for forbidden intersections problems.Advances in Mathematics, 445:109653, 2024

    Andrey Kupavskii and Dmitrii Zakharov. Spread approximations for forbidden intersections problems.Advances in Mathematics, 445:109653, 2024

    2024

  37. [37]

    Stable sets of maximal size in Kneser-type graphs

    Benoit Larose and Claudia Malvenuto. Stable sets of maximal size in Kneser-type graphs. European J. Combin., 25(5):657–673, 2004

    2004

  38. [38]

    Electron

    KarenMeagherandLuciaMoura.Erd˝ os-Ko-Radotheoremsforuniformset-partitionsystems. Electron. J. Combin., 12:40:1–12, 2005

    2005

  39. [39]

    The Erd˝ os-Ko-rado theo- rem for 2-pointwise and 2-setwise intersecting permutations.Electron

    Karen Meagher and Andriaherimanana Sarobidy Razafimahatratra. The Erd˝ os-Ko-rado theo- rem for 2-pointwise and 2-setwise intersecting permutations.Electron. J. Comb., 28(4), 2021

    2021

  40. [40]

    Extremal $t$-intersecting Families of Permutations for Large $t$

    Pitchayut Saengrungkongka. Extremal𝑡-intersecting families of permutations for large𝑡. arXiv preprint arXiv:2605.26051, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  41. [41]

    The sunflower lemma via shannon entropy.https://terrytao.wordpress.com/ 2020/07/20/the-sunflower-lemma-via-shannon-entropy/, 2020

    Terence Tao. The sunflower lemma via shannon entropy.https://terrytao.wordpress.com/ 2020/07/20/the-sunflower-lemma-via-shannon-entropy/, 2020

    2020

  42. [42]

    Richard M. Wilson. The exact bound in the Erd˝ os-Ko-Rado theorem.Combinatorica, 4(2- 3):247–257, 1984

    1984