pith. sign in

arxiv: 2605.17945 · v1 · pith:WQNYFKNDnew · submitted 2026-05-18 · 🧮 math.CO

Note on the codegree version of the ErdH{o}s--Ko--Rado theorem

Luyining Gan , Jie Han , Seonghyuk Im This is my paper

Pith reviewed 2026-05-20 09:42 UTC · model grok-4.3

classification 🧮 math.CO
keywords intersecting familiesErdős–Ko–Rado theoremcodegreeextremal set theorystability methodsuniform hypergraphsdegree conditions
0
0 comments X

The pith

For d equal to k minus one, the n threshold guaranteeing the codegree bound in intersecting k-uniform families drops to 2k plus roughly the square root of 2k.

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

The paper sharpens the codegree form of the Erdős–Ko–Rado theorem on intersecting families of k-subsets. It proves that when the codegree parameter d equals k minus one, the ground set needs only to be at least 2k plus the square root of 2k plus a small error term before every such family has its smallest d-degree no larger than in the standard extremal example. The authors obtain a similar but weaker improvement when d equals k minus two. A reader cares because these tighter thresholds narrow the gap between the absolute minimum size 2k and the point where the intersection property forces the degree condition to hold.

Core claim

If F is an intersecting family of k-subsets of an n-element set with d equal to k minus one and n at least 2k plus the square root of 2k plus O(1), then the minimum d-degree of F is at most the binomial coefficient binom(n-d-1, k-d-1). The same conclusion holds with the weaker additive term 7k to the two-thirds plus O(k to the one-third) when d equals k minus two. Both statements improve the earlier threshold of n at least 2k plus 2d minus three.

What carries the argument

Refined stability and counting arguments that bound the minimum d-degree once n exceeds the new threshold.

If this is right

  • When d is k minus one the extremal degree bound holds for all n at least 2k plus roughly sqrt(2k).
  • When d is k minus two the same bound holds for all n at least 2k plus roughly 7k to the two-thirds.
  • The required n gets closer to the absolute minimum 2k as d approaches k.
  • Stability methods can be tuned to produce stronger additive terms when the difference k minus d is small.

Where Pith is reading between the lines

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

  • The pattern of improvement may continue for other small values of k minus d, possibly yielding thresholds even closer to 2k.
  • Explicit constructions that violate the degree bound at n just below the new threshold would show whether the sqrt(2k) term is sharp.
  • The same refinement technique could be tested on related degree conditions in intersecting families beyond the two cases treated here.

Load-bearing premise

The stability or counting arguments still force every intersecting family to have small minimum d-degree as soon as n passes the stated new threshold.

What would settle it

An intersecting family of k-subsets on n equal to 2k plus the floor of the square root of 2k points, with d equal to k minus one, in which some d-set lies in more than binom(n-d-1, k-d-1) members of the family would show the improved bound fails.

read the original abstract

Kupavskii proved a codegree version of the Erd\H{o}s--Ko--Rado theorem by showing that for an intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ with $n \geq 2k +3d/(1-d/k)$, the minimum $d$-degree of $\mathcal{F}$ is at most $\binom{n-d-1}{k-d-1}$. Huang and Zhang improved the bound on $n$ to $n \geq 2k+2d-3$. In this short note, we prove that if $d = k-1$, then the bound on $n$ can be improved to $2k + \sqrt{2k} + O(1)$. In addition, we extend our method to show that the bound on $n$ can be improved to $2k + 7k^{2/3}+O(k^{1/3})$ when $d=k-2$.

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 is a short note improving the n-threshold in the codegree version of the Erdős–Ko–Rado theorem for intersecting k-uniform families. Building on Kupavskii and Huang–Zhang, it shows that when d = k−1 the minimum d-degree is at most binom(n−d−1, k−d−1) already for n ≥ 2k + √(2k) + O(1), and when d = k−2 the same conclusion holds for n ≥ 2k + 7k^{2/3} + O(k^{1/3}). The improvements are obtained by extending the stability/counting arguments of the earlier works and solving the quadratic and cubic inequalities that arise from the minimum-degree hypothesis.

Significance. If the derivations hold, the note supplies sharper, explicit thresholds for two regimes in which d is close to k. The method of directly solving the resulting quadratic and cubic inequalities yields concrete correction terms (square-root and k^{2/3}) without extra hypotheses on error terms or family structure, thereby refining the quantitative picture of codegree EKR-type results and illustrating how stability techniques can be tuned for special parameter values.

minor comments (3)
  1. [Proof for d = k−1] In the derivation of the bound for d = k−1, the passage from the minimum-degree inequality to the quadratic equation whose positive root supplies the √(2k) term should be written out explicitly (including the precise coefficients) so that the O(1) remainder can be verified to be independent of k.
  2. [Proof for d = k−2] For the cubic inequality arising when d = k−2, the authors should record the explicit constant 7 in front of k^{2/3} and confirm that the O(k^{1/3}) term absorbs all lower-order contributions uniformly for large k.
  3. A one-sentence comparison of the new thresholds with the previous bound n ≥ 2k + 2d − 3 would help readers immediately see the improvement for the two special cases.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our note, as well as the recommendation for minor revision. The report correctly identifies the improvements to the n-threshold for d = k-1 and d = k-2.

Circularity Check

0 steps flagged

No significant circularity detected in the derivation

full rationale

The manuscript extends the stability and counting arguments from the external prior works of Kupavskii and Huang-Zhang to the special cases d = k-1 and d = k-2. The improved thresholds 2k + √(2k) + O(1) and 2k + 7k^{2/3} + O(k^{1/3}) are obtained directly by solving the quadratic and cubic inequalities that follow from the minimum d-degree condition in an intersecting family. These steps consist of explicit algebraic estimates with no reduction to fitted parameters, self-definitions, or load-bearing self-citations; the central claims remain independent mathematical refinements supported by the cited external methods and the intersecting property alone.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on a mathematical proof that refines standard counting or stability arguments already present in the cited literature; no free parameters, new axioms beyond ordinary combinatorics, or invented entities are indicated by the abstract.

axioms (1)
  • standard math Standard combinatorial inequalities and double-counting arguments suffice to control the minimum d-degree once n exceeds the stated threshold.
    The note extends the methods of Kupavskii and Huang–Zhang, which themselves rely on such background combinatorial facts.

pith-pipeline@v0.9.0 · 5707 in / 1376 out tokens · 48937 ms · 2026-05-20T09:42:44.111806+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Deza and P

    M. Deza and P. Frankl. Erd˝ os–Ko–Rado theorem – 22 years later.SIAM Journal on Algebraic Discrete Methods, 4(4):419–431, 1983

    work page 1983

  2. [2]

    Erd˝ os, C

    P. Erd˝ os, C. Ko, and R. Rado. Intersection theorems for systems of finite sets.The Quarterly Journal of Mathem- atics, 12(1):313–320, 01 1961

    work page 1961

  3. [3]

    P. Frankl. Erd˝ os-Ko-Rado theorem with conditions on the maximal degree.Journal of Combinatorial Theory, Series A, 46(2):252–263, 1987

    work page 1987

  4. [4]

    Frankl, J

    P. Frankl, J. Han, H. Huang, and Y. Zhao. A degree version of the Hilton–Milner theorem.Journal of Combinatorial Theory, Series A, 155:493–502, 2018

    work page 2018

  5. [5]

    Frankl and N

    P. Frankl and N. Tokushige. A note on Huang–Zhao theorem on intersecting families with large minimum degree. Discrete Mathematics, 340(5):1098–1103, 2017

    work page 2017

  6. [6]

    A. J. W. Hilton and E. C. Milner. Some intersection theorems for systems of finite sets.The Quarterly Journal of Mathematics, 18(1):369–384, 01 1967

    work page 1967

  7. [7]

    Huang and Y

    H. Huang and Y. Zhang. On ad-degree Erd˝ os–Ko–Rado theorem.Journal of Combinatorial Theory, Series A, 221:106163, 2026

    work page 2026

  8. [8]

    Huang and Y

    H. Huang and Y. Zhao. Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjec- ture.Journal of Combinatorial Theory, Series A, 150:233–247, 2017

    work page 2017

  9. [9]

    Kupavskii

    A. Kupavskii. Degree versions of theorems on intersecting families via stability.Journal of Combinatorial Theory, Series A, 168:272–287, 2019. School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China; Key Laboratory of Mathematics and Information Networks (BUPT), Ministry of Education, Beijing, China Email addres...

    work page 2019