pith. sign in

arxiv: 2605.19424 · v1 · pith:35IUMXEDnew · submitted 2026-05-19 · 🧮 math.CO

On extremal cross t-intersecting families with t-covering number conditions

Yu Zhu , Benjian Lv , Kaishun Wang This is my paper

Pith reviewed 2026-05-20 04:39 UTC · model grok-4.3

classification 🧮 math.CO
keywords cross t-intersecting familiest-covering numbert-intersecting familiesextremal set theoryErdős–Ko–Rado theoremcovering numbercombinatorial extremal problems
0
0 comments X

The pith

Cross t-intersecting families with t-covering number at least t+1 maximize their size product only through particular constructions that lack a common t-subset inside each family.

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

The paper determines the families F1 and F2 of subsets that achieve the largest possible product of their cardinalities while ensuring every member of F1 intersects every member of F2 in at least t elements, yet each family separately has t-covering number at least t+1. This last condition rules out the usual situation in which all sets in one family share a fixed t-element subset. A sympathetic reader cares because the result refines classical bounds on intersecting families by forcing the families to remain diverse within themselves while still intersecting across the pair. The authors give the precise structures that attain the maximum and then treat the special case of a single t-intersecting family whose t-covering number equals t+1.

Core claim

We characterize the extremal structures of cross t-intersecting families F1 and F2 that maximize |F1||F2| under the condition that tau_t(F1) >= t+1 and tau_t(F2) >= t+1. We then describe the maximal t-intersecting families with t-covering number t+1.

What carries the argument

The t-covering number tau_t(F), the smallest cardinality of a set T such that every member of F intersects T in at least t elements; the condition tau_t >= t+1 forces each family to have empty total intersection of size t and thereby excludes the classical starring construction inside each family.

If this is right

  • The maximum product |F1||F2| equals the product attained by the described constructions.
  • Any family achieving the bound must coincide with one of the listed extremal examples.
  • The same extremal families also solve the single-family problem of maximum size among t-intersecting families that satisfy tau_t = t+1.
  • The characterization yields explicit upper bounds on the sizes once the covering-number constraint is imposed.

Where Pith is reading between the lines

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

  • The same techniques may extend to q-analogues or to families with restricted intersection sizes beyond t.
  • For moderate n one can computationally enumerate small cases and check whether the predicted constructions remain optimal.
  • The result suggests a stability statement: families close to the maximum must be close in structure to the listed examples.

Load-bearing premise

The ground set [n] is assumed large enough relative to k and t so that the extremal constructions are not blocked by boundary effects.

What would settle it

For concrete values of n, k1, k2 and t, exhibit a pair of families satisfying the cross t-intersecting and tau_t >= t+1 conditions whose size product exceeds the product of the structures claimed to be extremal.

read the original abstract

Let $n$, $k$ and $t$ be positive integers, and let $\mathcal{F}$ be a collection of $k$-subsets of $[n]=\{1,2,\dots,n\}$. The $t$-covering number $\tau_t(\mathcal{F})$ of $\mathcal{F}$ is defined as the minimum size of a set $T$ such that $|F\cap T|\geq t$ for all $F\in \mathcal{F}$. For positive integers $k_1$ and $k_2$, let $\mathcal{F}_i$ be a collection of $k_i$-subsets of $[n]$ for $i\in \{1,2\}$. The families $\mathcal{F}_1$ and $\mathcal{F}_2$ are said to be cross $t$-intersecting if $|F_1\cap F_2|\geq t$ for all $F_1\in\mathcal{F}_1$ and $F_2\in \mathcal{F}_2$. When $\mathcal{F}_1=\mathcal{F}_2$, $\mathcal{F}_1$ is called a $t$-intersecting family. In this paper, we first characterize the extremal structures of cross $t$-intersecting families $\mathcal{F}_1$ and $\mathcal{F}_2$ that maximize $|\mathcal{F}_1||\mathcal{F}_2|$ under the condition that $\tau_t(\mathcal{F}_1)\geq t+1$ and $\tau_t(\mathcal{F}_2)\geq t+1$. We then describe the maximal $t$-intersecting families with $t$-covering number $t+1$.

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 / 1 minor

Summary. The paper characterizes the extremal structures of cross t-intersecting families F1 and F2 of k1- and k2-subsets that maximize |F1| |F2| subject to tau_t(Fi) >= t+1 for i=1,2. It further describes the maximal t-intersecting families with t-covering number exactly t+1.

Significance. If the characterizations hold, the work extends EKR-type theorems by adding t-covering number constraints, supplying explicit structural descriptions of the extremal examples rather than mere bounds. This could serve as a reference for subsequent results on constrained intersecting families.

major comments (1)
  1. [Theorem 1.1] Theorem 1.1 (and the abstract): the characterization is asserted for arbitrary positive integers n, k, t, yet the standard proof technique in this area requires n sufficiently large relative to k and t (to preclude boundary constructions from overtaking the claimed families). No explicit threshold N0(k,t) is stated or derived, which is load-bearing for the universality of the claimed extremal structures.
minor comments (1)
  1. The definition of tau_t(F) is clear, but a brief remark relating it to the non-existence of a t-wise common intersection would aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this important point about the range of the main result. We address the comment below and will revise the paper accordingly.

read point-by-point responses

  1. Referee: [Theorem 1.1] Theorem 1.1 (and the abstract): the characterization is asserted for arbitrary positive integers n, k, t, yet the standard proof technique in this area requires n sufficiently large relative to k and t (to preclude boundary constructions from overtaking the claimed families). No explicit threshold N0(k,t) is stated or derived, which is load-bearing for the universality of the claimed extremal structures.

    Authors: We agree that the proof of Theorem 1.1 relies on n being sufficiently large relative to k and t in order to ensure that the claimed extremal families are indeed maximal and that no other constructions (possible only for small n) can produce a larger product. The manuscript does not currently state an explicit lower bound on n. In the revised version we will add the hypothesis n ≥ N(k,t) to the statement of Theorem 1.1 and the abstract, and we will derive a concrete (though possibly not optimal) explicit threshold N(k,t) from the existing proof arguments. This will make the range of validity of the characterization fully explicit. revision: yes

Circularity Check

0 steps flagged

No circularity in combinatorial characterization

full rationale

The paper delivers a structural characterization of maximal cross t-intersecting families subject to tau_t(F_i) >= t+1, using standard tools from extremal set theory (EKR-type theorems and covering-number arguments). No equations, fitted parameters, or self-definitional quantities appear; the result is proved directly from the definitions of cross t-intersecting and t-covering number without reducing any claimed extremal structure to a prior fit or self-citation chain. The derivation remains self-contained once the (standard) large-n assumption is granted, and no load-bearing step collapses to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard axioms of finite set theory and the definitions of t-intersecting and t-covering number; no new entities or fitted parameters are introduced in the abstract.

axioms (1)
  • domain assumption The ground set is the finite set [n] with n sufficiently large compared to k and t.
    Standard background assumption in extremal set theory papers to avoid boundary cases.

pith-pipeline@v0.9.0 · 5833 in / 1298 out tokens · 45746 ms · 2026-05-20T04:39:42.089059+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

36 extracted references · 36 canonical work pages

  1. [1]

    Ahlswede and L.H

    R. Ahlswede and L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets,J. Combin. Theory Ser. A76 (1996) 121–138

    work page 1996

  2. [2]

    Ahlswede and L.H

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

    work page 1997

  3. [3]

    Borg, A short proof of a cross-intersection theorem of Hilton,Discrete Math.309 (2009) 4750–4753

    P. Borg, A short proof of a cross-intersection theorem of Hilton,Discrete Math.309 (2009) 4750–4753. 21

    work page 2009

  4. [4]

    Borg, The maximum sum and the maximum product of sizes of cross intersecting families,European J

    P. Borg, The maximum sum and the maximum product of sizes of cross intersecting families,European J. Combin.35 (2014) 117–130

    work page 2014

  5. [5]

    Borg, The maximum product of sizes of cross-t-intersecting uniform families,Aus- tralas

    P. Borg, The maximum product of sizes of cross-t-intersecting uniform families,Aus- tralas. J. Combin.60 (2014) 69–78

    work page 2014

  6. [6]

    Borg, The maximum product of weights of cross-intersecting families,J

    P. Borg, The maximum product of weights of cross-intersecting families,J. London Math. Soc.(2) 94 (2016) 993–1018

    work page 2016

  7. [7]

    Brouwer, A.M

    A.E. Brouwer, A.M. Cohen and A. Neumaier,Distance-Regular Graphs, Springer-Verlag, Berlin 1989

    work page 1989

  8. [8]

    M. Cao, M. Lu, B. Lv and K. Wang, Nearly extremal non-trivial crosst-intersecting families andr-wiset-intersecting families,European J. Combin.120 (2024) 103958

    work page 2024

  9. [9]

    M. Cao, B. Lv and K. Wang, The structure of large non-trivialt-intersecting families of finite sets,European J. Combin.97 (2021) 103373

    work page 2021

  10. [10]

    Erd˝ os, C

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

    work page 1961

  11. [11]

    Frankl, The Erd˝ os-Ko-Rado theorem is true forn=ckt, in: I

    P. Frankl, The Erd˝ os-Ko-Rado theorem is true forn=ckt, in: I. Combinatorics (Ed), Proc. Fifth Hungarian Colloq., Keszthey 1976, in: Colloq. Math. Soc. J´ anos Bolyai, vol. 18, North-Holland, 1978, pp. 365–375

    work page 1976

  12. [12]

    Frankl, On intersecting families of finite sets,J

    P. Frankl, On intersecting families of finite sets,J. Combin. Theory Ser. A24 (1978) 146–161

    work page 1978

  13. [13]

    Frankl and Z

    P. Frankl and Z. F¨ uredi, Nontrivial intersecting families,J. Combin. Theory Ser. A41 (1986) 150–153

    work page 1986

  14. [14]

    Frankl and Z

    P. Frankl and Z. F¨ uredi, Beyond the Erd˝ os-Ko-Rado theorem,J. Combin. Theory Ser. A56 (1991) 182–194

    work page 1991

  15. [15]

    Frankl and A

    P. Frankl and A. Kupavskii, Asize-sensitive inequality for cross-intersecting families, European J. Combin.62 (2017) 263–271

    work page 2017

  16. [16]

    Frankl, S

    P. Frankl, S. J. Lee, M. Siggers and N. Tokushige, An Erd˝ os-Ko-Rado theorem for cross t-intersecting families,J. Combin. Theory Ser. A128 (2014) 207–249

    work page 2014

  17. [17]

    Frankl and J

    P. Frankl and J. Wang, A product version of the Hilton-Milner theorem,J. Combin. Theory Ser. A200 (2023) 105791

    work page 2023

  18. [18]

    Frankl and J

    P. Frankl and J. Wang, A product version of the Hilton-Milner-Frankl theorem,Sci. China Math.67 (2024), no. 2, 455–474

    work page 2024

  19. [19]

    Han and Y

    J. Han and Y. Kohayakawa, The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family,Proc. Amer. Math. Soc. 145(1) (2017) 73–87

    work page 2017

  20. [20]

    Hilton, An intersection theorem for a collection of families of subsets of a finite set, J

    A. Hilton, An intersection theorem for a collection of families of subsets of a finite set, J. London Math. Soc.(2) 15 (1977) 369–376

    work page 1977

  21. [21]

    D. He, A. Li, B. Wu and H. Zhang, On nontrivial cross-t-intersecting families,J. Combin. Theory Ser. A217 (2026) 106095. 22

    work page 2026

  22. [22]

    Hilton and E

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

    work page 1967

  23. [23]

    Huang and Y

    Y. Huang and Y. Peng, Non-empty pairwise cross-intersecting families,J. Combin. Theory Ser. A211 (2025) 105981

    work page 2025

  24. [24]

    Kostochka and D

    A. Kostochka and D. Mubayi, The structure of large intersecting families,Proc. Amer. Math. Soc.145 (6) (2017) 2311–2321

    work page 2017

  25. [25]

    Li and H

    A. Li and H. Zhang, On non-empty cross-t-intersecting families,J. Combin. Theory Ser. A210 (2025) 105960

    work page 2025

  26. [26]

    Matsumoto and N

    M. Matsumoto and N. Tokushige, The exact bound in the Erd˝ os-Ko-Rado theorem for cross intersecting families,J. Combin. Theory Ser. A52 (1989) 90–97

    work page 1989

  27. [27]

    Pyber, A new generalization of the Erd˝ os-Ko-Rado theorem,J

    L. Pyber, A new generalization of the Erd˝ os-Ko-Rado theorem,J. Combin. Theory Ser. A43 (1986) 85–90

    work page 1986

  28. [28]

    C. Shi, P. Frankl and J. Qian, On non-empty cross-intersecting families,Combinatorica 42 (2) (2022) 1513–1525

    work page 2022

  29. [29]

    Tanaka and N

    H. Tanaka and N. Tokushige, A semidefinite programming approach to cross 2- intersecting families, arXiv:2503.14844

    work page arXiv

  30. [30]

    Tokushige, On crosst-intersecting families of sets,J

    N. Tokushige, On crosst-intersecting families of sets,J. Combin. Theory Ser. A117 (2010) 1167–1177

    work page 2010

  31. [31]

    Tokushige, The eigenvalue method for crosst-intersecting families,J

    N. Tokushige, The eigenvalue method for crosst-intersecting families,J. Algebr. Comb. 38 (2013) 653–662

    work page 2013

  32. [32]

    Wang and H

    J. Wang and H. Zhang, Cross-intersecting families and primitivity of symmetric systems, J. Combin. Theory Ser. A118 (2011) 455–462

    work page 2011

  33. [33]

    Wilson, The exact bound in the Erd˝ os-Ko-Rado theorem,Combinatorica4 (1984) 247–257

    R.M. Wilson, The exact bound in the Erd˝ os-Ko-Rado theorem,Combinatorica4 (1984) 247–257

    work page 1984

  34. [34]

    Y. Xi, X. Kong and G. Ge, Multi-part cross-intersecting families,J. Algebraic Combin. 59 (3) (2024) 597–620

    work page 2024

  35. [35]

    T. Yao, D. Liu, K. Wang, Extremalt-intersecting families for finite sets witht-covering number at leastt+ 2, arXiv:2602.14129

    work page arXiv

  36. [36]

    Zhang and B

    H. Zhang and B. Wu, On a conjecture of Tokushige for cross-t-intersecting families,J. Combin. Theory Ser. B171 (2025) 49–70. 23

    work page 2025