On Bollob\'as-type theorems of $d$-tuples

Erfei Yue

REVIEW 1 major objections 5 minor 24 references

On Bollob\'as-type theorems of $d$-tuples

T0 review · 1 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper refutes the Hegedüs–Frankl conjecture that d-tuple Bollobás sums stay at most 1, proves an asymptotically tight (n+3)/2 bound for triples, and gives multinomial bounds for skew systems of sets and spaces.

desk verdict Nice counterexample and sound uniform bounds, but the proof of the main upper bound has a real gap in the empty-middle-component case. read the letter →

arxiv 2411.17192 v3 pith:HG3GUYDN submitted 2024-11-26 math.CO

Erfei Yue This is my paper · ORCID

classification math.CO MSC 05D0505A1005A20

keywords Bollobássystemsskewd-tuplesmultinomialcoefficientsrandompermutationsexterioralgebraextremalsettheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

In 1965 Bollobás proved that for a family of disjoint set-pairs with the required cross-intersections, the sum of inverse binomial coefficients is at most 1. The paper extends this question to d-tuples of pairwise disjoint sets and shows that the natural multinomial generalization is false. It constructs a triples example whose inverse-multinomial sum is floor(n/2)+1, and proves that for triples the sum can never exceed (n+3)/2, so the construction is asymptotically tight. For general d, the paper gives a polynomial upper bound whose leading term is 1/(d-1) times the binomial coefficient (n+d-2 choose d-2). It also sharpens the known inequality for skew Bollobás systems and determines the exact maximum size of uniform skew systems on both sets and spaces.

What carries the argument

The load-bearing mechanism is a random-permutation encoding: take a uniformly random permutation of [n] together with d-1 extra delimiter elements, and require the components of a tuple to appear in the prescribed order with delimiters separating specified adjacent blocks. The probability of such an event is the reciprocal of a product of a multinomial coefficient and a binomial factor, and the Bollobás condition forces events belonging to different tuples to be disjoint, giving the sum bound. For skew systems the same encoding yields the weighted inequality of Theorem 1.8. For the space version, exterior algebra replaces permutations: each subspace is represented by a wedge product, and the skew cross-intersection condition makes certain linear functionals vanish in a triangular way, yielding the multinomial size bound.

What would settle it

An explicit Bollobás system of triples on a five-element ground set with inverse-multinomial sum exceeding 4 would refute the d=3 bound; exhaustive search for small n could settle it.

Watch

Extended reading notes

Core claim

The central discovery is that the multinomial analogue of Bollobás's inequality fails for d-tuples, and the correct order of growth is polynomial in the ground-set size. The counterexample collects all disjoint triples of type (l, n-2l, l) for l=0,...,floor(n/2); each triple contributes an inverse multinomial coefficient, and the total is floor(n/2)+1. Theorem 1.6 proves for d=3 that no Bollobás system of triples on [n] can make the sum exceed (n+3)/2, so the construction is asymptotically extremal. For general d, the same random-permutation argument yields the bound 1/(d-1) times (n+d-2 choose d-2) plus O($n^{{d-3}}$). For skew systems, the paper proves a refined inequality with an extra binomial factor and shows that uniform skew systems of d-tuples, of sets or of subspaces, have size at most the corresponding multinomial coefficient.

Load-bearing premise

The counting argument assumes that the permutation events for different tuples cannot overlap, and that this remains true even for tuples with empty first or last components.

Editorial extensions

If this is right

The Hegedüs–Frankl conjecture is false: for d=3 the inverse-multinomial sum can be as large as floor(n/2)+1, so the original bound of 1 does not extend to d-tuples.
For triples, the maximum sum is pinned between roughly n/2 and (n+3)/2, so the paper's construction is asymptotically extremal.
For d≥4, the leading term 1/(d-1) times (n+d-2 choose d-2) is the first general upper bound, and it remains open whether the true maximum is smaller.
For skew Bollobás systems, the weighted inverse sum is at most 1, which immediately implies the unweighted inverse sum is at most (n+d-1 choose d-1).
Uniform skew systems of d-tuples, whether of sets or of subspaces, have size at most the multinomial coefficient (a_1+...+a_d choose a_1,...,a_d), and this is tight by the explicit disjoint-tuples construction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The d=3 upper bound of (n+3)/2 suggests that extremal constructions concentrate on middle components of intermediate size; a testable conjecture is that the maximum is attained by types with all components as equal as possible.
The proof gap for tuples with empty first or last components might be closed by a limiting or convexity argument; if the gap cannot be closed, the bound could still be valid by a different route.
The exterior-algebra proof for uniform skew systems of spaces may extend to affine subspaces or matroids, paralleling the classical Lovász extension of Bollobás-type theorems.
For d≥4, sharpening the O(n^{d-3}) error term would require precisely counting tuples with empty middle components, which the current induction only estimates coarsely.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. The counterexample to Hegedüs and Frankl's conjecture is real, and the uniform skew Bollobás bounds (Theorems 1.9 and 1.13) look correct. But the proof of the main upper bound, Theorem 1.6, has a load-bearing gap: the empty-middle-component case is not handled by the argument given.

What's good. Example 2 is a clean construction: for d=3, the sum of inverse multinomials is about n/2, so the conjectured bound of 1 is wrong. Theorem 1.8's random-permutation argument is sound and genuinely sharpens the skew Bollobás inequality; the disjointness of the events is straightforward. The exterior algebra proof of Theorem 1.13 is a valid linear-independence argument and gives the tight uniform bound for spaces, which also implies Theorem 1.9 for sets.

Where it breaks. In the proof of Theorem 1.6, after handling tuples with nonempty middle component, the paper says that when A_i^(2)=∅, the projected pairs (A_i^(1), A_i^(3)) form a d=2 Bollobás system, so Theorem 1.2 applies. That is false. Take i=({1},∅,{2}) and j=({3},{1,2},{4}). The triple system is Bollobás: i∩j via {1}∩{1,2}, and j∩i via {1,2}∩{2}. But the projected pairs ({1},{2}) and ({3},{4}) fail in both directions. So the bound (n+3)/2 is not established. The same defective projection appears in the induction step for d>3 when deleting a component. This is not a minor technicality; it is the step that lets the proof reach the asserted bound.

The paper is honest about Tian and Wu's independent work, so the counterexample and Theorem 1.8 are not novel to this manuscript. What remains new is Theorem 1.6 (needs a repaired proof) and the uniform bounds.

Bottom line: the counterexample and the uniform bounds are worth a serious referee. The author should be asked to fix the empty-component argument, or clearly restrict Theorem 1.6 to tuples with all internal components nonempty. Until then, Theorem 1.6 should not be taken as proved.

Recommendation: send to peer review, but with the expectation that the proof of Theorem 1.6 must be revised.

Referee Report

1 major / 5 minor

Summary. The paper studies Bollobás-type theorems for families of d-tuples of sets and of vector subspaces. It refutes a conjecture of Hegedűs and Frankl by constructing a Bollobás triple system whose inverse multinomial sum is floor(n/2)+1, and proves upper bounds for this sum for arbitrary d (Theorem 1.6), which is asymptotically tight for d=3. It also improves a skew Bollobás inequality (Theorem 1.8) and determines the maximum size of uniform skew Bollobás systems of d-tuples of sets and spaces (Theorems 1.9 and 1.13). The proofs use random permutations and exterior algebra.

Significance. If the results hold, the paper settles a natural conjecture in the negative and provides the first nontrivial upper bounds for the generalized Bollobás sum. The d=3 bound is asymptotically tight, and the exterior algebra proof of Theorem 1.13 is a clean linear independence argument. The probabilistic techniques are coherent, and the paper correctly acknowledges independent work by Tian and Wu.

major comments (1)

[Section 2, induction step of Theorem 1.6] The displayed estimate for a fixed k states that the sum over tuples with A_i^(k)=∅ is at most 1/(d-2) binom(n+d-3,d-3) + O(n^{d-4}). The subsequent 'Hence' line adds a single binom(n+d-3,d-3) term to the bound for tuples with all middle components nonempty. To cover all tuples with at least one empty middle component, the proof must sum the displayed estimates over all k in {2,...,d-1}; the factor (d-2) then cancels the 1/(d-2), yielding exactly the term shown. As written, the step is a non sequitur, though the repair is straightforward.

minor comments (5)

[Section 2, d=3 case of Theorem 1.6] The statement that the subfamily with A_i^(2)=∅ projects to a Bollobás pair system is true, but the proof should justify it: any witness for two such triples cannot involve the empty second component, so it survives projection.
[Section 2, proof of Theorem 1.8] The definition of E_i is ambiguous about whether the delimiters must appear in a fixed order. If a specific order is meant, the probability should include a 1/(d-1)! factor; if the union over all orders is meant, this should be stated. The current text is open to misinterpretation.
[Example 2] The claim 'A ∩ (B′ ∪ C′) ≠ ∅' when A≠A′ is false in general (e.g., if A=∅ or A⊆A′). The example is still valid because in the exceptional case B∩C′≠∅ provides the witness; the proof should be corrected.
[Theorem 1.6 statement] There is a typo in the family notation: the closing parenthesis is missing in '{(A_i^(1), ..., A_i^(d) | i ∈ [m])}'.
[Abstract and text] There are several minor typos, e.g., 'boun d' in the abstract and '/greaterorequalslant' in the body; and the symbols '⋆' in Table 2 are only explained in the final remark.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new bounds are derived from external theorems and self-contained probabilistic/exterior-algebra arguments; the author's prior work is cited as inspiration only.

full rationale

The paper's central results (Theorem 1.6, Theorem 1.8, Theorem 1.9, Theorem 1.13) are proved directly from Bollobás's theorem, Frankl's skew Bollobás theorem, the general-position lemma of Babai–Frankl, and explicit random-permutation/exterior-algebra arguments. The citation of the author's own preprint [23] occurs as 'Generalizing the probabilistic method in [23]' and in the attribution of Theorem 1.4, but the probabilistic argument is fully reproduced in the paper (events Ei, Fi, probability computations, disjointness arguments), so [23] is not load-bearing. No fitted parameter is renamed as a prediction, no uniqueness theorem from the authors' prior work is invoked, and no ansatz is smuggled in by citation. The main mathematical difficulty in the write-up is a proof gap: the assertion in Section 2 that 'for A_i^(2)=∅, the collection {(A_i^(1), A_i^(3)) | A_i^(2)=∅} forms a Bollobás system (of d=2)' is not generally true, since deleting an empty middle component can destroy the cross-intersection witnesses, so the induction step of Theorem 1.6 is not valid as written. That is a correctness flaw, not circularity, because the attempted reduction is to an external theorem (Theorem 1.2 / the induction hypothesis) and the equations do not identify the conclusion with an input by construction. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted. The proofs use only standard combinatorial, probabilistic, and exterior algebra tools plus the external Bollobás theorem and general position lemma. No new entities are postulated.

assumptions (4)

standard math The exterior product of a list of vectors is nonzero iff the vectors are linearly independent (Lemma 3.2).
Invoked in proof of Theorem 1.13 to infer f_i(ξ_i) is nonzero and f_i(ξ_j) is zero from direct sum decompositions and positive-dimensional intersections.
standard math General position lemma: over an infinite field, a linear map can preserve the dimension of every subspace in a finite list (Lemma 3.3, from Babai-Frankl [2]).
Used to construct the maps φ_k in Theorem 1.13; it holds for R and is stated for |F| > (n-k)(m+1).
standard math Uniform random permutation and the union bound for disjoint events.
Basis of the probabilistic proofs of Theorems 1.6 and 1.8.
standard math Bollobás's 1965 theorem (Theorem 1.2) is true.
Used in the d=3 proof of Theorem 1.6 for tuples with the middle component empty.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Bollob\'as-type theorems of $d$-tuples." pith.science (2026). https://pith.science/paper/HG3GUYDN

@misc{pith2026241117192,
  author       = {Pith},
  title        = {Pith review of: On Bollob\'as-type theorems of $d$-tuples},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HG3GUYDN}},
  note         = {Machine review of arXiv:2411.17192}
}

abstract

In 1965, Bollob\'as proved that for a Bollob\'as set-pair system $\{(A_i,B_i)\mid i\in[m]\}$, the maximum value of $\sum_{i=1}^m\binom{|A_i|+|B_i|}{A_i}^{-1}$ is $1$. Heged\"{u}s and Frankl recently extended the concept of Bollob\'as systems to $d$-tuples, conjecturing that for a Bollob\'as system of $d$-tuples, $\{(A_i^{(1)},\ldots,A_i^{(d)})\mid i\in[m]\}$, the maximum value of $\sum_{i=1}^m\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}^{-1}$ is also $1$. This paper refutes this conjecture and establishes an upper bound for the sum. In the case $d=3$, the derived upper bound is asymptotically tight. Furthermore, we sharpen an inequality for skew Bollob\'as systems of $d$-tuples in Heged\"{u}s and Frankl's paper. Finally, we determine the maximum size of a uniform skew Bollob\'as system of $d$-tuples on both sets and spaces.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Alon, An extremal problem for sets with applications to graph t heory, J

N. Alon, An extremal problem for sets with applications to graph t heory, J. Combin. Theory Ser. A 40 (1985) 82-89

work page 1985
[2]

Babai, P

L. Babai, P. Frankl, Linear algebra methods in combinatorics, 199 2

work page
[3]

Bollob´ as, On generalized graphs, Acta Math

B. Bollob´ as, On generalized graphs, Acta Math. Acad. Sci. Hung ar. 16 (1965) 447-452

work page 1965
[4]

Frankl, An extremal problem for two families of sets, Europ

P. Frankl, An extremal problem for two families of sets, Europ. J . Combin. 3 (1982) 125-127

work page 1982
[5]

F¨ uredi, Geometrical solution of an intersection problem for t wo hypergraphs, Europ

Z. F¨ uredi, Geometrical solution of an intersection problem for t wo hypergraphs, Europ. J. Combin. 5 (1984) 133-136

work page 1984
[6]

Heged¨ us, A Bollob´ as-type theorem for aﬃne subspaces, Australasian Journal of Com- binatorics 63 (2015) 262-267

G. Heged¨ us, A Bollob´ as-type theorem for aﬃne subspaces, Australasian Journal of Com- binatorics 63 (2015) 262-267

work page 2015
[7]

Heged¨ us, P

G. Heged¨ us, P. Frankl, Variations on the Bollob´ as set-pair theorem, Europ. J. Combin. 120 (2024) 103983

work page 2024
[8]

Jaeger, C

F. Jaeger, C. Payan, Nombre maximal d’arˆ etes d’un hypergraphe critique de rang h. CR Acad. Sci. Paris 273 (1971) 221-223

work page 1971

Show all 24 references

[9]

D. Kang, J. Kim, A. Kim, On the Erd¨ os-Ko-Rado theorem and the Bollob´ as theorem for t-intersecting families, Europ. J. Combin. 47 (2015) 68-74. 12

2015
[10]

G. O. H. Katona, Solution of a problem of A. Ehrenfeucht and J. Mycielski, J. Combin. Theory Ser. A 17 (1974) 265-266

1974
[11]

Kir´ aly, Z

Z. Kir´ aly, Z. L. Nagy, D. P´ alv¨ olgyi, M. Visontai, On families of weakly cross-intersecting set-pairs, Fund. Inform. 117 (2012) 189-198

2012
[12]

Lov´ asz, Flats in matroids and geometric graphs, Proc

L. Lov´ asz, Flats in matroids and geometric graphs, Proc. 6th British Combin. Conf., Academic Press, London, 1977

1977
[13]

Lov´ asz, Topological and algebraic methods in graph theory, Graph theory and related topics, Academic Press, New York, 1979

L. Lov´ asz, Topological and algebraic methods in graph theory, Graph theory and related topics, Academic Press, New York, 1979

1979
[14]

Lov´ asz, Combinatorial problems and exercises, Akad´ emia i Kiad´ o, Budapest, and North-Holland, Amsterdam, 1979

L. Lov´ asz, Combinatorial problems and exercises, Akad´ emia i Kiad´ o, Budapest, and North-Holland, Amsterdam, 1979

1979
[15]

O’Neill, J

J. O’Neill, J. Verstra¨ ete, A generalization of the Bollob´ as set pairs inequality, the Elec- tronic J. Combin. 28(3) (2021) #P3.8

2021
[16]

J. E. Pin, On two combinatorial problems arising from automata t heory, North-Holland Mathematics Studies 75 (1981) 535-548

1981
[17]

Scott, E

A. Scott, E. Wilmer, Combinatorics in the exterior algebra and th e Bollob´ astwo families theorem, J. Lond. Math. Soc. 2(104) (2021) 1812-1839

2021
[18]

Talbot, A new Bollob´ as-type inequality and applications to t-in tersecting families of sets, Discrete Math

J. Talbot, A new Bollob´ as-type inequality and applications to t-in tersecting families of sets, Discrete Math. 285 (2004) 349-353

2004
[19]

T. G. Tarj´ an, Complexity of lattice-conﬁgurations, Studia Scientiarum Mathematicarum Hungarica 10 (1975) 203-211

1975
[20]

A. Tian, Y. Wu, Bollob´ as set pair inequalities for compositions, https://math.sjtu.edu.cn/faculty/ykwu/data/Paper/Bollobas.pdf
[21]

Tuza, Inequalities for two set systems with prescribed inte rsections, Graphs and J

Zs. Tuza, Inequalities for two set systems with prescribed inte rsections, Graphs and J. Combin. 3 (1987) 75-80

1987
[22]

W. Yu, X. Kong, Y. Xi, X. Zhang, G. Ge, Bollob´ as type theorems for hemi-bundled two families, Europ. J. Combin. 100 (2022) 103438

2022
[23]

Yue, Some new Bollob´ as-type inequalities, https://arxiv.org /abs/2405.17639, 2024- 6-29

E. Yue, Some new Bollob´ as-type inequalities, https://arxiv.org /abs/2405.17639, 2024- 6-29

2024 arXiv
[24]

Zhu, On two set-systems with restricted cross-intersect ions, Europ

C. Zhu, On two set-systems with restricted cross-intersect ions, Europ. J. Combin. 16 (1995) 655-658. 13

1995

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Alon, An extremal problem for sets with applications to graph t heory, J

N. Alon, An extremal problem for sets with applications to graph t heory, J. Combin. Theory Ser. A 40 (1985) 82-89

work page 1985

[2] [2]

Babai, P

L. Babai, P. Frankl, Linear algebra methods in combinatorics, 199 2

work page

[3] [3]

Bollob´ as, On generalized graphs, Acta Math

B. Bollob´ as, On generalized graphs, Acta Math. Acad. Sci. Hung ar. 16 (1965) 447-452

work page 1965

[4] [4]

Frankl, An extremal problem for two families of sets, Europ

P. Frankl, An extremal problem for two families of sets, Europ. J . Combin. 3 (1982) 125-127

work page 1982

[5] [5]

F¨ uredi, Geometrical solution of an intersection problem for t wo hypergraphs, Europ

Z. F¨ uredi, Geometrical solution of an intersection problem for t wo hypergraphs, Europ. J. Combin. 5 (1984) 133-136

work page 1984

[6] [6]

Heged¨ us, A Bollob´ as-type theorem for aﬃne subspaces, Australasian Journal of Com- binatorics 63 (2015) 262-267

G. Heged¨ us, A Bollob´ as-type theorem for aﬃne subspaces, Australasian Journal of Com- binatorics 63 (2015) 262-267

work page 2015

[7] [7]

Heged¨ us, P

G. Heged¨ us, P. Frankl, Variations on the Bollob´ as set-pair theorem, Europ. J. Combin. 120 (2024) 103983

work page 2024

[8] [8]

Jaeger, C

F. Jaeger, C. Payan, Nombre maximal d’arˆ etes d’un hypergraphe critique de rang h. CR Acad. Sci. Paris 273 (1971) 221-223

work page 1971