An Erd\H{o}s Matching Conjecture for Vector Spaces

Baoyan Feng; Chenyang Zhang; Chong Shangguan; Yulin Yang

arxiv: 2606.24529 · v1 · pith:CT2MW6NEnew · submitted 2026-06-23 · 🧮 math.CO · cs.IT· math.IT

An ErdH{o}s Matching Conjecture for Vector Spaces

Baoyan Feng , Chong Shangguan , Yulin Yang , Chenyang Zhang This is my paper

Pith reviewed 2026-06-25 23:16 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT

keywords Erdős matching conjecturevector spacessubspace familiesGaussian binomialsmatroid matchingscover-free familiesstability theorems

0 comments

The pith

A vector-space analogue of the Erdős matching conjecture holds for k=2, for n exactly (s+1)k, and for all sufficiently large n.

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

The paper defines m_q(n,k,s) as the largest number of k-dimensional subspaces of an n-dimensional space over F_q such that no s+1 of them have direct sum. It gives two explicit constructions that achieve lower bounds on this quantity and conjectures that one of them is always optimal when n is at least (s+1)k. The conjecture is proved in three regimes: when the subspace dimension k equals 2, when the ambient dimension n equals (s+1)k, and when n is large enough. A stability theorem identifying the largest non-extremal families is also proved for large n, and the same methods determine the extremal size of t-cover-free families of subspaces up to a lower-order term.

Core claim

The conjecture asserts that m_q(n,k,s) equals the maximum of the Gaussian binomial [(s+1)k-1 choose k]_q and [n choose k]_q minus q^{ks} times [n-s choose k]_q for every n at least (s+1)k. This equality is established when k=2 (a vector-space Erdős-Gallai theorem), when n=(s+1)k, and when n is sufficiently large, via Lovász's minimax theorem for matroid matchings together with a high-dimensional Hoffman bound.

What carries the argument

The two constructions (all k-subspaces inside a fixed ((s+1)k-1)-dimensional subspace, and all k-subspaces meeting a fixed s-dimensional subspace nontrivially) together with Lovász's minimax theorem for matroid matchings and the high-dimensional Hoffman bound on uniform hypergraphs.

If this is right

The conjecture holds for every choice of parameters when k equals 2.
The conjecture holds for every choice of parameters when n equals (s+1)k.
The conjecture holds for every choice of parameters when n is sufficiently large.
A Hilton-Milner-type stability theorem identifies the largest families that are not one of the two constructions when n is large.
The maximum size of a t-cover-free family of subspaces is determined up to a lower-order term for every t.

Where Pith is reading between the lines

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

The same two constructions may remain extremal for the remaining open parameter ranges.
The matroid-matching and Hoffman-bound techniques may resolve the conjecture for additional fixed values of k.

Load-bearing premise

The two listed constructions are the only ones that achieve the maximum size.

What would settle it

A collection of k-subspaces larger than both constructions for some parameters with k greater than 2 and n only moderately larger than (s+1)k.

read the original abstract

We study a vector-space analogue of the Erd\H{o}s Matching Conjecture. Let $m_q(n,k,s)$ denote the maximum cardinality of a family of $k$-dimensional subspaces of an $n$-dimensional vector space over $\mathbb F_q$ with no $s+1$ members whose sum is direct. Two natural constructions provide lower bounds. The first consists of all $k$-subspaces contained in a fixed $((s+1)k-1)$-dimensional subspace; the second consists of all $k$-subspaces that intersect a fixed $s$-dimensional subspace nontrivially. These constructions motivate the following vector-space analogue of the Erd\H{o}s Matching Conjecture: for all $n\ge (s+1)k$, $$m_q(n,k,s)=\max\left\{\genfrac{[}{]}{0pt}{}{(s+1)k-1}{k}_q,~\genfrac{[}{]}{0pt}{}{n}{k}_q-q^{ks}\genfrac{[}{]}{0pt}{}{n-s}{k}_q\right\}.$$ We prove this conjecture when $k=2$, when $n=(s+1)k$, and when $n$ is sufficiently large. In particular, the case $k=2$ may be viewed as a vector-space analogue of the Erd\H{o}s--Gallai theorem. In the large-$n$ range, we also prove a Hilton--Milner-type stability theorem, determining the largest nontrivial families with this property. Finally, we connect this problem with $t$-cover-free families in vector spaces and determine their extremal number up to a lower-order term, extending a recent result of Shan and Zhou for the special case $t=2$. The proofs combine Lov\'asz's minimax theorem for matroid matchings, a high-dimensional Hoffman bound for uniform hypergraphs, and packing-design arguments in vector spaces.

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.

Desk Editor's Note private letter to a colleague

The paper proves the vector-space Erdős matching conjecture for k=2, n=(s+1)k, and large n, plus stability and a t-cover-free extension.

read the letter

This paper proves the vector-space analogue of the Erdős matching conjecture in three regimes: k=2, n exactly (s+1)k, and n sufficiently large. It also gives a Hilton-Milner stability theorem for the large-n case and extends the problem to t-cover-free families of subspaces, determining their extremal size up to lower-order terms.

The two constructions are the natural ones: all k-subspaces inside a fixed ((s+1)k-1)-dimensional space, and all k-subspaces that meet a fixed s-dimensional space nontrivially. The proofs combine Lovász's minimax theorem for matroid matchings, a high-dimensional Hoffman bound on the relevant intersection hypergraph, and direct packing arguments in the vector space. For k=2 this yields a vector-space version of the Erdős-Gallai theorem. The stability result shows that large families in the large-n regime must be close to one of the two constructions.

The work is clean on the tools it uses. The matroid and Hoffman arguments apply directly to the linear matroid over F_q with no evident extra restrictions, and the packing steps are standard in this setting. The link to t-cover-free families builds directly on prior work for t=2 and gives a useful connection between the two problems.

The main limitation is that the large-n result is asymptotic, so the threshold for "sufficiently large" is not made explicit. The conjecture remains open outside the three handled cases. No circularity or fitting issues appear in the argument.

This is for people working on q-analogues of extremal set theory or on subspace versions of matching and covering problems. It shows clear engagement with the literature and uses standard tools appropriately, so it deserves a serious referee. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The paper defines m_q(n,k,s) as the maximum size of a family of k-dimensional subspaces of an n-dimensional vector space over F_q with no s+1 members whose sum is direct. It proposes the conjecture that for n ≥ (s+1)k this equals the maximum of two quantities arising from the 'all k-subspaces in a fixed ((s+1)k-1)-space' and 'all k-subspaces meeting a fixed s-space nontrivially' constructions. The manuscript proves the equality when k=2, when n=(s+1)k, and when n is sufficiently large; it also proves a Hilton-Milner-type stability theorem for large n and determines the extremal function for t-cover-free families in vector spaces up to lower-order terms, extending Shan-Zhou. The proofs combine Lovász's minimax theorem for matroid matchings, a high-dimensional Hoffman bound on an intersection hypergraph, and vector-space packing arguments.

Significance. If the derivations hold, the work is a substantive contribution to q-analogues of extremal set theory. It establishes the vector-space Erdős Matching Conjecture in three nontrivial regimes (including the k=2 case as a direct analogue of the Erdős-Gallai theorem) and supplies a stability result together with an application to t-cover-free families. The combination of matroid matching, spectral bounds, and packing arguments is appropriate and yields explicit extremal constructions that match the claimed upper bounds in each regime treated.

minor comments (3)

[Introduction] The introduction should include an explicit definition of the q-binomial coefficient [n choose k]_q (including the product formula) before its first use in the conjecture statement, for accessibility to readers outside the q-analogue literature.
[Section on large-n case] In the large-n regime, the manuscript should state the explicit lower bound on n (in terms of s, k, q) that makes the packing argument and Hoffman bound yield the claimed equality, rather than leaving 'sufficiently large' unqualified.
[Stability theorem] The stability theorem for large n is stated only for the maximum nontrivial families; a brief remark on whether the same packing analysis yields stability for the k=2 or n=(s+1)k cases would strengthen the presentation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough reading and positive evaluation of the manuscript. The recommendation for minor revision is noted, and we are pleased that the combination of methods and the results in the k=2, n=(s+1)k, and large-n regimes are viewed as substantive contributions. Since the report lists no specific major comments requiring clarification or correction, we have no point-by-point revisions to address at this stage.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states a vector-space analogue of the Erdős Matching Conjecture motivated by two explicit constructions, then proves the equality holds for k=2, n=(s+1)k, and sufficiently large n. The proofs rely on Lovász's minimax theorem for matroid matchings, the high-dimensional Hoffman bound on intersection hypergraphs, and vector-space packing arguments; these are external, independently established results applied directly to the linear matroid over F_q. No step reduces the claimed bound to a fitted parameter, a self-referential definition, or a load-bearing self-citation chain. The stability result and the connection to t-cover-free families likewise invoke external prior work without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard combinatorial theorems and the definition of direct sum in vector spaces; no free parameters or new entities are introduced.

axioms (2)

standard math Lovász's minimax theorem for matroid matchings
Invoked for the matching problem in the vector-space matroid.
standard math High-dimensional Hoffman bound for uniform hypergraphs
Used to bound the size of families without s+1 direct sums.

pith-pipeline@v0.9.1-grok · 5894 in / 1348 out tokens · 26700 ms · 2026-06-25T23:16:40.759720+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

56 extracted references · 4 linked inside Pith

[1]

On the size of graphs with complete-factors.Journal of Graph Theory, 9(1):197–201, 1985

Jin Akiyama and Peter Frankl. On the size of graphs with complete-factors.Journal of Graph Theory, 9(1):197–201, 1985

1985
[2]

Sur le couplage maximum d’un graphe.Comptes Rendus Hebdomadaires des S´ eances de l’Acad´ emie des Sciences, 247:258–259, 1958

Claude Berge. Sur le couplage maximum d’un graphe.Comptes Rendus Hebdomadaires des S´ eances de l’Acad´ emie des Sciences, 247:258–259, 1958

1958
[3]

Blackburn and Tuvi Etzion

Simon R. Blackburn and Tuvi Etzion. The asymptotic behavior of Grassmannian codes.IEEE Transactions on Information Theory, 58(10):6605–6609, 2012

2012
[4]

Brouwer, Ameera Chowdhury, Peter Frankl, T

Aart Blokhuis, Andries E. Brouwer, Ameera Chowdhury, Peter Frankl, T. Mussche, Bal´ azs Patk´ os, and Tam´ as Sz¨ onyi. A Hilton–Milner theorem for vector spaces.Electronic Journal of Combina- torics, 17(1):R71, 2010

2010
[5]

Bollob´ as, David E

B. Bollob´ as, David E. Daykin, and Paul Erd˝ os. Sets of independent edges of a hypergraph.The Quarterly Journal of Mathematics, 27(1):25–32, 1976

1976
[6]

Brouwer, Arjeh M

Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier.Distance-Regular Graphs, volume 18 ofErgebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. Springer, Berlin, 1989

1989
[7]

Mengyu Cao, Mei Lu, Benjian Lv, and Kaishun Wang.r-crosst-intersecting families for vector spaces.Journal of Combinatorial Theory, Series A, 193:105688, 2023

2023
[8]

Shadows and intersections in vector spaces.Journal of Combinatorial Theory, Series A, 117(8):1095–1106, 2010

Ameera Chowdhury and Bal´ azs Patk´ os. Shadows and intersections in vector spaces.Journal of Combinatorial Theory, Series A, 117(8):1095–1106, 2010

2010
[9]

PhD thesis, University of California, San Diego, 2012

Ameerah Naz Chowdhury.Shadows and Intersections. PhD thesis, University of California, San Diego, 2012. 22

2012
[10]

Association schemes andt-designs in regular semilattices.Journal of Combi- natorial Theory, Series A, 20(2):230–243, 1976

Philippe Delsarte. Association schemes andt-designs in regular semilattices.Journal of Combi- natorial Theory, Series A, 20(2):230–243, 1976

1976
[11]

A problem on independentr-tuples.Annales Universitatis Scientiarum Budapesti- nensis de Rolando E¨ otv¨ os Nominatae

Paul Erd˝ os. A problem on independentr-tuples.Annales Universitatis Scientiarum Budapesti- nensis de Rolando E¨ otv¨ os Nominatae. Sectio Mathematica, 8:93–95, 1965

1965
[12]

Families of finite sets in which no set is covered by the union of two others.Journal of Combinatorial Theory, Series A, 33(2):158–166, 1982

Paul Erd˝ os, Peter Frankl, and Zolt´ an F¨ uredi. Families of finite sets in which no set is covered by the union of two others.Journal of Combinatorial Theory, Series A, 33(2):158–166, 1982

1982
[13]

Families of finite sets in which no set is covered by the union ofrothers.Israel Journal of Mathematics, 51(1–2):79–89, 1985

Paul Erd˝ os, Peter Frankl, and Zolt´ an F¨ uredi. Families of finite sets in which no set is covered by the union ofrothers.Israel Journal of Mathematics, 51(1–2):79–89, 1985

1985
[14]

On maximal paths and circuits of graphs.Acta Mathematica Academiae Scientiarum Hungaricae, 10(3–4):337–356, 1959

Paul Erd˝ os and Tibor Gallai. On maximal paths and circuits of graphs.Acta Mathematica Academiae Scientiarum Hungaricae, 10(3–4):337–356, 1959

1959
[15]

Paul Erd˝ os, Chao Ko, and R. Rado. Intersection theorems for systems of finite sets.The Quarterly Journal of Mathematics, 12(1):313–320, 1961

1961
[16]

Problems onq-analogs in coding theory.arXiv preprint arXiv:1305.6126, 2013

Tuvi Etzion. Problems onq-analogs in coding theory.arXiv preprint arXiv:1305.6126, 2013

Pith/arXiv arXiv 2013
[17]

Grassmannian codes with new distance measures for network coding

Tuvi Etzion and Hui Zhang. Grassmannian codes with new distance measures for network coding. IEEE Transactions on Information Theory, 65(7):4131–4142, 2019

2019
[18]

High-dimensional Hoffman bound and applications in extremal combinatorics.Algebraic Combinatorics, 4(6):1005–1026, 2021

Yuval Filmus, Konstantin Golubev, and Noam Lifshitz. High-dimensional Hoffman bound and applications in extremal combinatorics.Algebraic Combinatorics, 4(6):1005–1026, 2021

2021
[19]

The shifting technique in extremal set theory

Peter Frankl. The shifting technique in extremal set theory. In C. Whitehead, editor,Surveys in Combinatorics 1987, volume 123 ofLondon Mathematical Society Lecture Note Series, pages 81–110. Cambridge University Press, 1987

1987
[20]

Improved bounds for Erd˝ os’ matching conjecture.Journal of Combinatorial Theory, Series A, 120(5):1068–1072, 2013

Peter Frankl. Improved bounds for Erd˝ os’ matching conjecture.Journal of Combinatorial Theory, Series A, 120(5):1068–1072, 2013

2013
[21]

On the maximum number of edges in a hypergraph with given matching number

Peter Frankl. On the maximum number of edges in a hypergraph with given matching number. Discrete Applied Mathematics, 216:562–581, 2017

2017
[22]

Proof of the Erd˝ os matching conjecture in a new range.Israel Journal of Mathe- matics, 222(1):421–430, 2017

Peter Frankl. Proof of the Erd˝ os matching conjecture in a new range.Israel Journal of Mathe- matics, 222(1):421–430, 2017

2017
[23]

On non-trivial families without a perfect matching.European Journal of Combina- torics, 84:103044, 2020

Peter Frankl. On non-trivial families without a perfect matching.European Journal of Combina- torics, 84:103044, 2020

2020
[24]

Colored packing of sets

Peter Frankl and Zolt´ an F¨ uredi. Colored packing of sets. In C. J. Colbourn and R. Mathon, editors,Combinatorial Design Theory, volume 149 ofNorth-Holland Mathematics Studies, pages 165–177. North-Holland, Amsterdam, 1987

1987
[25]

Peter Frankl and Ronald L. Graham. Intersection theorems for vector spaces.European Journal of Combinatorics, 6(2):183–187, 1985

1985
[26]

The Erd˝ os matching conjecture and concentration inequalities

Peter Frankl and Andrey Kupavskii. The Erd˝ os matching conjecture and concentration inequalities. Journal of Combinatorial Theory, Series B, 157:366–400, 2022

2022
[27]

Towards the Erd˝ os matching conjecture for 4-uniform hypergraphs: Stability and applications.arXiv preprint arXiv:2602.19230, 2026

Peter Frankl, Hongliang Lu, Jie Ma, and Yuze Wu. Towards the Erd˝ os matching conjecture for 4-uniform hypergraphs: Stability and applications.arXiv preprint arXiv:2602.19230, 2026. 23

Pith/arXiv arXiv 2026
[28]

On matchings in hypergraphs.Elec- tronic Journal of Combinatorics, 19(2):P42, 2012

Peter Frankl, Tomasz Luczak, and Katarzyna Mieczkowska. On matchings in hypergraphs.Elec- tronic Journal of Combinatorics, 19(2):P42, 2012

2012
[29]

Near perfect coverings in graphs and hypergraphs.European Journal of Combinatorics, 6(4):317–326, 1985

Peter Frankl and Vojtech R¨ odl. Near perfect coverings in graphs and hypergraphs.European Journal of Combinatorics, 6(4):317–326, 1985

1985
[30]

On the maximum number of edges in a triple system not containing a disjoint family of a given size.Combinatorics, Probability and Computing, 21(1–2):141–148, 2012

Peter Frankl, Vojtech R¨ odl, and Andrzej Ruci´ nski. On the maximum number of edges in a triple system not containing a disjoint family of a given size.Combinatorics, Probability and Computing, 21(1–2):141–148, 2012

2012
[31]

Peter Frankl and Richard M. Wilson. The Erd˝ os–Ko–Rado theorem for vector spaces.Journal of Combinatorial Theory, Series A, 43(2):228–236, 1986

1986
[32]

Christopher Godsil and Karen Meagher.Erd˝ os–Ko–Rado Theorems: Algebraic Approaches, volume
[33]

Cambridge University Press, 2015

2015
[34]

Kleitman

Curtis Greene and Daniel J. Kleitman. Proof techniques in the theory of finite sets. In Gian-Carlo Rota, editor,Studies in Combinatorics, volume 17 ofMAA Studies in Mathematics, pages 22–79. Mathematical Association of America, Washington, D.C., 1978

1978
[35]

A stability result for almost perfect matchings.Journal of Graph Theory, 112(1):5–14, 2026

Mingyang Guo and Hongliang Lu. A stability result for almost perfect matchings.Journal of Graph Theory, 112(1):5–14, 2026

2026
[36]

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

1967
[37]

Alan J. Hoffman. On eigenvalues and colorings of graphs. In Charles A. Micchelli, editor,Selected Papers of Alan J. Hoffman: With Commentary, pages 407–419. World Scientific, 2003

2003
[38]

A finite-board reduction for the Erd˝ os matching conjec- ture and the 4-uniform case via exact certificates.arXiv preprint arXiv:2605.26060, 2026

Jianfeng Hou, Caiyun Hu, and Xizhi Liu. A finite-board reduction for the Erd˝ os matching conjec- ture and the 4-uniform case via exact certificates.arXiv preprint arXiv:2605.26060, 2026

Pith/arXiv arXiv 2026
[39]

Intersection theorems for systems of finite vector spaces.Discrete Mathematics, 12(1):1–16, 1975

Wen-Ning Hsieh. Intersection theorems for systems of finite vector spaces.Discrete Mathematics, 12(1):1–16, 1975

1975
[40]

The size of a hypergraph and its matching number

Hao Huang, Po-Shen Loh, and Benny Sudakov. The size of a hypergraph and its matching number. Combinatorics, Probability and Computing, 21(3):442–450, 2012

2012
[41]

Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjecture.Journal of Combinatorial Theory, Series A, 150:233–247, 2017

Hao Huang and Yi Zhao. Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjecture.Journal of Combinatorial Theory, Series A, 150:233–247, 2017

2017
[42]

A survey of cover-free families: Constructions, applica- tions, and generalizations

Tha´ ıs Bardini Idalino and Lucia Moura. A survey of cover-free families: Constructions, applica- tions, and generalizations. InProceedings of the International Conference on New Advances in Designs, Codes and Cryptography, pages 195–239. Springer, 2022

2022
[43]

Remarks on the Erd˝ os matching conjecture for vector spaces.European Journal of Combinatorics, 94:103306, 2021

Ferdinand Ihringer. Remarks on the Erd˝ os matching conjecture for vector spaces.European Journal of Combinatorics, 94:103306, 2021

2021
[44]

Structure oft-intersecting families of vector spaces

Ferdinand Ihringer and Andrey Kupavskii. Structure oft-intersecting families of vector spaces. arXiv preprint arXiv:2605.02698, 2026

Pith/arXiv arXiv 2026
[45]

G. O. H. Katona. A simple proof of the Erd˝ os–Chao Ko–Rado theorem.Journal of Combinatorial Theory, Series B, 13(2):183–184, 1972. 24

1972
[46]

W. H. Kautz and R. C. Singleton. Nonrandom binary superimposed codes.IEEE Transactions on Information Theory, 10(4):363–377, 1964

1964
[47]

Kleitman

Daniel J. Kleitman. Maximal number of subsets of a finite set nokof which are pairwise disjoint. Journal of Combinatorial Theory, 5(2):157–163, 1968

1968
[48]

Erd˝ os matching conjecture for almost perfect matchings

Dmitriy Kolupaev and Andrey Kupavskii. Erd˝ os matching conjecture for almost perfect matchings. Discrete Mathematics, 346(4):113304, 2023

2023
[49]

Isodiametric inequality for vector spaces.arXiv preprint arXiv:2503.19239, 2025

Jiaqi Liao, Hong Liu, and Guiying Yan. Isodiametric inequality for vector spaces.arXiv preprint arXiv:2503.19239, 2025

arXiv 2025
[50]

Jiuqiang Liu, Guihai Yu, Lihua Feng, and Yongtao Li.L-intersecting or configuration-forbidden families on set systems and vector spaces over finite fields.arXiv preprint arXiv:2403.04289, 2024

arXiv 2024
[51]

Matroid matching and some applications.Journal of Combinatorial Theory, Series B, 28(2):208–236, 1980

L´ aszl´ o Lov´ asz. Matroid matching and some applications.Journal of Combinatorial Theory, Series B, 28(2):208–236, 1980

1980
[52]

Selecting independent lines from a family of lines in a space.Acta Scientiarum Mathematicarum, 42(1–2):121–131, 1980

L´ aszl´ o Lov´ asz. Selecting independent lines from a family of lines in a space.Acta Scientiarum Mathematicarum, 42(1–2):121–131, 1980

1980
[53]

On Erd˝ os’ extremal problem on matchings in hy- pergraphs.Journal of Combinatorial Theory, Series A, 124:178–194, 2014

Tomasz Luczak and Katarzyna Mieczkowska. On Erd˝ os’ extremal problem on matchings in hy- pergraphs.Journal of Combinatorial Theory, Series A, 124:178–194, 2014

2014
[54]

The formula for Tur´ an number of spanning linear forests.Discrete Mathematics, 343(8):111924, 2020

Bo Ning and Jian Wang. The formula for Tur´ an number of spanning linear forests.Discrete Mathematics, 343(8):111924, 2020

2020
[55]

Covering Grassmannian codes: Bounds and constructions.IEEE Transactions on Information Theory, 69(6):3748–3758, 2023

Bingchen Qian, Xin Wang, Chengfei Xie, and Gennian Ge. Covering Grassmannian codes: Bounds and constructions.IEEE Transactions on Information Theory, 69(6):3748–3758, 2023

2023
[56]

On cover-free families of finite vector spaces.Journal of Combi- natorial Theory, Series A, 220:106131, 2026

Yunjing Shan and Junling Zhou. On cover-free families of finite vector spaces.Journal of Combi- natorial Theory, Series A, 220:106131, 2026. A Parameter calculations for Theorem 1.3(iii) We write [a]q := a 1 q. The following elementary estimate will be used repeatedly. Lemma A.1.Letm, r, tbe positive integers withm≥t+r. Then 1−4q −(m−t−r+2) [t]q m−1 r−1 q...

2026

[1] [1]

On the size of graphs with complete-factors.Journal of Graph Theory, 9(1):197–201, 1985

Jin Akiyama and Peter Frankl. On the size of graphs with complete-factors.Journal of Graph Theory, 9(1):197–201, 1985

1985

[2] [2]

Sur le couplage maximum d’un graphe.Comptes Rendus Hebdomadaires des S´ eances de l’Acad´ emie des Sciences, 247:258–259, 1958

Claude Berge. Sur le couplage maximum d’un graphe.Comptes Rendus Hebdomadaires des S´ eances de l’Acad´ emie des Sciences, 247:258–259, 1958

1958

[3] [3]

Blackburn and Tuvi Etzion

Simon R. Blackburn and Tuvi Etzion. The asymptotic behavior of Grassmannian codes.IEEE Transactions on Information Theory, 58(10):6605–6609, 2012

2012

[4] [4]

Brouwer, Ameera Chowdhury, Peter Frankl, T

Aart Blokhuis, Andries E. Brouwer, Ameera Chowdhury, Peter Frankl, T. Mussche, Bal´ azs Patk´ os, and Tam´ as Sz¨ onyi. A Hilton–Milner theorem for vector spaces.Electronic Journal of Combina- torics, 17(1):R71, 2010

2010

[5] [5]

Bollob´ as, David E

B. Bollob´ as, David E. Daykin, and Paul Erd˝ os. Sets of independent edges of a hypergraph.The Quarterly Journal of Mathematics, 27(1):25–32, 1976

1976

[6] [6]

Brouwer, Arjeh M

Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier.Distance-Regular Graphs, volume 18 ofErgebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. Springer, Berlin, 1989

1989

[7] [7]

Mengyu Cao, Mei Lu, Benjian Lv, and Kaishun Wang.r-crosst-intersecting families for vector spaces.Journal of Combinatorial Theory, Series A, 193:105688, 2023

2023

[8] [8]

Shadows and intersections in vector spaces.Journal of Combinatorial Theory, Series A, 117(8):1095–1106, 2010

Ameera Chowdhury and Bal´ azs Patk´ os. Shadows and intersections in vector spaces.Journal of Combinatorial Theory, Series A, 117(8):1095–1106, 2010

2010

[9] [9]

PhD thesis, University of California, San Diego, 2012

Ameerah Naz Chowdhury.Shadows and Intersections. PhD thesis, University of California, San Diego, 2012. 22

2012

[10] [10]

Association schemes andt-designs in regular semilattices.Journal of Combi- natorial Theory, Series A, 20(2):230–243, 1976

Philippe Delsarte. Association schemes andt-designs in regular semilattices.Journal of Combi- natorial Theory, Series A, 20(2):230–243, 1976

1976

[11] [11]

A problem on independentr-tuples.Annales Universitatis Scientiarum Budapesti- nensis de Rolando E¨ otv¨ os Nominatae

Paul Erd˝ os. A problem on independentr-tuples.Annales Universitatis Scientiarum Budapesti- nensis de Rolando E¨ otv¨ os Nominatae. Sectio Mathematica, 8:93–95, 1965

1965

[12] [12]

Families of finite sets in which no set is covered by the union of two others.Journal of Combinatorial Theory, Series A, 33(2):158–166, 1982

Paul Erd˝ os, Peter Frankl, and Zolt´ an F¨ uredi. Families of finite sets in which no set is covered by the union of two others.Journal of Combinatorial Theory, Series A, 33(2):158–166, 1982

1982

[13] [13]

Families of finite sets in which no set is covered by the union ofrothers.Israel Journal of Mathematics, 51(1–2):79–89, 1985

Paul Erd˝ os, Peter Frankl, and Zolt´ an F¨ uredi. Families of finite sets in which no set is covered by the union ofrothers.Israel Journal of Mathematics, 51(1–2):79–89, 1985

1985

[14] [14]

On maximal paths and circuits of graphs.Acta Mathematica Academiae Scientiarum Hungaricae, 10(3–4):337–356, 1959

Paul Erd˝ os and Tibor Gallai. On maximal paths and circuits of graphs.Acta Mathematica Academiae Scientiarum Hungaricae, 10(3–4):337–356, 1959

1959

[15] [15]

Paul Erd˝ os, Chao Ko, and R. Rado. Intersection theorems for systems of finite sets.The Quarterly Journal of Mathematics, 12(1):313–320, 1961

1961

[16] [16]

Problems onq-analogs in coding theory.arXiv preprint arXiv:1305.6126, 2013

Tuvi Etzion. Problems onq-analogs in coding theory.arXiv preprint arXiv:1305.6126, 2013

Pith/arXiv arXiv 2013

[17] [17]

Grassmannian codes with new distance measures for network coding

Tuvi Etzion and Hui Zhang. Grassmannian codes with new distance measures for network coding. IEEE Transactions on Information Theory, 65(7):4131–4142, 2019

2019

[18] [18]

High-dimensional Hoffman bound and applications in extremal combinatorics.Algebraic Combinatorics, 4(6):1005–1026, 2021

Yuval Filmus, Konstantin Golubev, and Noam Lifshitz. High-dimensional Hoffman bound and applications in extremal combinatorics.Algebraic Combinatorics, 4(6):1005–1026, 2021

2021

[19] [19]

The shifting technique in extremal set theory

Peter Frankl. The shifting technique in extremal set theory. In C. Whitehead, editor,Surveys in Combinatorics 1987, volume 123 ofLondon Mathematical Society Lecture Note Series, pages 81–110. Cambridge University Press, 1987

1987

[20] [20]

Improved bounds for Erd˝ os’ matching conjecture.Journal of Combinatorial Theory, Series A, 120(5):1068–1072, 2013

Peter Frankl. Improved bounds for Erd˝ os’ matching conjecture.Journal of Combinatorial Theory, Series A, 120(5):1068–1072, 2013

2013

[21] [21]

On the maximum number of edges in a hypergraph with given matching number

Peter Frankl. On the maximum number of edges in a hypergraph with given matching number. Discrete Applied Mathematics, 216:562–581, 2017

2017

[22] [22]

Proof of the Erd˝ os matching conjecture in a new range.Israel Journal of Mathe- matics, 222(1):421–430, 2017

Peter Frankl. Proof of the Erd˝ os matching conjecture in a new range.Israel Journal of Mathe- matics, 222(1):421–430, 2017

2017

[23] [23]

On non-trivial families without a perfect matching.European Journal of Combina- torics, 84:103044, 2020

Peter Frankl. On non-trivial families without a perfect matching.European Journal of Combina- torics, 84:103044, 2020

2020

[24] [24]

Colored packing of sets

Peter Frankl and Zolt´ an F¨ uredi. Colored packing of sets. In C. J. Colbourn and R. Mathon, editors,Combinatorial Design Theory, volume 149 ofNorth-Holland Mathematics Studies, pages 165–177. North-Holland, Amsterdam, 1987

1987

[25] [25]

Peter Frankl and Ronald L. Graham. Intersection theorems for vector spaces.European Journal of Combinatorics, 6(2):183–187, 1985

1985

[26] [26]

The Erd˝ os matching conjecture and concentration inequalities

Peter Frankl and Andrey Kupavskii. The Erd˝ os matching conjecture and concentration inequalities. Journal of Combinatorial Theory, Series B, 157:366–400, 2022

2022

[27] [27]

Towards the Erd˝ os matching conjecture for 4-uniform hypergraphs: Stability and applications.arXiv preprint arXiv:2602.19230, 2026

Peter Frankl, Hongliang Lu, Jie Ma, and Yuze Wu. Towards the Erd˝ os matching conjecture for 4-uniform hypergraphs: Stability and applications.arXiv preprint arXiv:2602.19230, 2026. 23

Pith/arXiv arXiv 2026

[28] [28]

On matchings in hypergraphs.Elec- tronic Journal of Combinatorics, 19(2):P42, 2012

Peter Frankl, Tomasz Luczak, and Katarzyna Mieczkowska. On matchings in hypergraphs.Elec- tronic Journal of Combinatorics, 19(2):P42, 2012

2012

[29] [29]

Near perfect coverings in graphs and hypergraphs.European Journal of Combinatorics, 6(4):317–326, 1985

Peter Frankl and Vojtech R¨ odl. Near perfect coverings in graphs and hypergraphs.European Journal of Combinatorics, 6(4):317–326, 1985

1985

[30] [30]

On the maximum number of edges in a triple system not containing a disjoint family of a given size.Combinatorics, Probability and Computing, 21(1–2):141–148, 2012

Peter Frankl, Vojtech R¨ odl, and Andrzej Ruci´ nski. On the maximum number of edges in a triple system not containing a disjoint family of a given size.Combinatorics, Probability and Computing, 21(1–2):141–148, 2012

2012

[31] [31]

Peter Frankl and Richard M. Wilson. The Erd˝ os–Ko–Rado theorem for vector spaces.Journal of Combinatorial Theory, Series A, 43(2):228–236, 1986

1986

[32] [32]

Christopher Godsil and Karen Meagher.Erd˝ os–Ko–Rado Theorems: Algebraic Approaches, volume

[33] [33]

Cambridge University Press, 2015

2015

[34] [34]

Kleitman

Curtis Greene and Daniel J. Kleitman. Proof techniques in the theory of finite sets. In Gian-Carlo Rota, editor,Studies in Combinatorics, volume 17 ofMAA Studies in Mathematics, pages 22–79. Mathematical Association of America, Washington, D.C., 1978

1978

[35] [35]

A stability result for almost perfect matchings.Journal of Graph Theory, 112(1):5–14, 2026

Mingyang Guo and Hongliang Lu. A stability result for almost perfect matchings.Journal of Graph Theory, 112(1):5–14, 2026

2026

[36] [36]

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

1967

[37] [37]

Alan J. Hoffman. On eigenvalues and colorings of graphs. In Charles A. Micchelli, editor,Selected Papers of Alan J. Hoffman: With Commentary, pages 407–419. World Scientific, 2003

2003

[38] [38]

A finite-board reduction for the Erd˝ os matching conjec- ture and the 4-uniform case via exact certificates.arXiv preprint arXiv:2605.26060, 2026

Jianfeng Hou, Caiyun Hu, and Xizhi Liu. A finite-board reduction for the Erd˝ os matching conjec- ture and the 4-uniform case via exact certificates.arXiv preprint arXiv:2605.26060, 2026

Pith/arXiv arXiv 2026

[39] [39]

Intersection theorems for systems of finite vector spaces.Discrete Mathematics, 12(1):1–16, 1975

Wen-Ning Hsieh. Intersection theorems for systems of finite vector spaces.Discrete Mathematics, 12(1):1–16, 1975

1975

[40] [40]

The size of a hypergraph and its matching number

Hao Huang, Po-Shen Loh, and Benny Sudakov. The size of a hypergraph and its matching number. Combinatorics, Probability and Computing, 21(3):442–450, 2012

2012

[41] [41]

Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjecture.Journal of Combinatorial Theory, Series A, 150:233–247, 2017

Hao Huang and Yi Zhao. Degree versions of the Erd˝ os–Ko–Rado theorem and Erd˝ os hypergraph matching conjecture.Journal of Combinatorial Theory, Series A, 150:233–247, 2017

2017

[42] [42]

A survey of cover-free families: Constructions, applica- tions, and generalizations

Tha´ ıs Bardini Idalino and Lucia Moura. A survey of cover-free families: Constructions, applica- tions, and generalizations. InProceedings of the International Conference on New Advances in Designs, Codes and Cryptography, pages 195–239. Springer, 2022

2022

[43] [43]

Remarks on the Erd˝ os matching conjecture for vector spaces.European Journal of Combinatorics, 94:103306, 2021

Ferdinand Ihringer. Remarks on the Erd˝ os matching conjecture for vector spaces.European Journal of Combinatorics, 94:103306, 2021

2021

[44] [44]

Structure oft-intersecting families of vector spaces

Ferdinand Ihringer and Andrey Kupavskii. Structure oft-intersecting families of vector spaces. arXiv preprint arXiv:2605.02698, 2026

Pith/arXiv arXiv 2026

[45] [45]

G. O. H. Katona. A simple proof of the Erd˝ os–Chao Ko–Rado theorem.Journal of Combinatorial Theory, Series B, 13(2):183–184, 1972. 24

1972

[46] [46]

W. H. Kautz and R. C. Singleton. Nonrandom binary superimposed codes.IEEE Transactions on Information Theory, 10(4):363–377, 1964

1964

[47] [47]

Kleitman

Daniel J. Kleitman. Maximal number of subsets of a finite set nokof which are pairwise disjoint. Journal of Combinatorial Theory, 5(2):157–163, 1968

1968

[48] [48]

Erd˝ os matching conjecture for almost perfect matchings

Dmitriy Kolupaev and Andrey Kupavskii. Erd˝ os matching conjecture for almost perfect matchings. Discrete Mathematics, 346(4):113304, 2023

2023

[49] [49]

Isodiametric inequality for vector spaces.arXiv preprint arXiv:2503.19239, 2025

Jiaqi Liao, Hong Liu, and Guiying Yan. Isodiametric inequality for vector spaces.arXiv preprint arXiv:2503.19239, 2025

arXiv 2025

[50] [50]

Jiuqiang Liu, Guihai Yu, Lihua Feng, and Yongtao Li.L-intersecting or configuration-forbidden families on set systems and vector spaces over finite fields.arXiv preprint arXiv:2403.04289, 2024

arXiv 2024

[51] [51]

Matroid matching and some applications.Journal of Combinatorial Theory, Series B, 28(2):208–236, 1980

L´ aszl´ o Lov´ asz. Matroid matching and some applications.Journal of Combinatorial Theory, Series B, 28(2):208–236, 1980

1980

[52] [52]

Selecting independent lines from a family of lines in a space.Acta Scientiarum Mathematicarum, 42(1–2):121–131, 1980

L´ aszl´ o Lov´ asz. Selecting independent lines from a family of lines in a space.Acta Scientiarum Mathematicarum, 42(1–2):121–131, 1980

1980

[53] [53]

On Erd˝ os’ extremal problem on matchings in hy- pergraphs.Journal of Combinatorial Theory, Series A, 124:178–194, 2014

Tomasz Luczak and Katarzyna Mieczkowska. On Erd˝ os’ extremal problem on matchings in hy- pergraphs.Journal of Combinatorial Theory, Series A, 124:178–194, 2014

2014

[54] [54]

The formula for Tur´ an number of spanning linear forests.Discrete Mathematics, 343(8):111924, 2020

Bo Ning and Jian Wang. The formula for Tur´ an number of spanning linear forests.Discrete Mathematics, 343(8):111924, 2020

2020

[55] [55]

Covering Grassmannian codes: Bounds and constructions.IEEE Transactions on Information Theory, 69(6):3748–3758, 2023

Bingchen Qian, Xin Wang, Chengfei Xie, and Gennian Ge. Covering Grassmannian codes: Bounds and constructions.IEEE Transactions on Information Theory, 69(6):3748–3758, 2023

2023

[56] [56]

On cover-free families of finite vector spaces.Journal of Combi- natorial Theory, Series A, 220:106131, 2026

Yunjing Shan and Junling Zhou. On cover-free families of finite vector spaces.Journal of Combi- natorial Theory, Series A, 220:106131, 2026. A Parameter calculations for Theorem 1.3(iii) We write [a]q := a 1 q. The following elementary estimate will be used repeatedly. Lemma A.1.Letm, r, tbe positive integers withm≥t+r. Then 1−4q −(m−t−r+2) [t]q m−1 r−1 q...

2026