pith. sign in

arxiv: 2606.25931 · v1 · pith:BFJ7X2W3new · submitted 2026-06-24 · 🧮 math.CO

A Simple Counting Argument for Dense Linear Hypergraphs

Lior Gishboliner , J\'ozsef Solymosi This is my paper

Pith reviewed 2026-06-25 18:58 UTC · model grok-4.3

classification 🧮 math.CO
keywords linear hypergraphsdensity theoremBrown-Erdős-Sós conjecturer-uniform hypergraphscounting argumentextremal combinatoricstriple systemslocal averaging
0
0 comments X

The pith

A linear r-uniform hypergraph exceeding a quadratic edge threshold contains k edges spanning at most (r-2)k+3 vertices.

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

The paper gives a short local averaging proof that any linear r-uniform hypergraph on n vertices whose edge count meets or exceeds ((k-2)/(r²((r-2)(k-2)+1)))n² + n/r must contain k edges on at most (r-2)k+3 vertices. The argument applies once n is at least (r-2)(k-2)+1 and directly yields an asymptotic density threshold of (r-1)/r times (k-2)/((r-2)(k-2)+1) plus lower-order terms. This supplies a simple proof of the large-uniformity case of the Brown-Erdős-Sós theorem and sharpens the triple-system bound from 4/5 to 2(k-2)/(3(k-1)) plus o(1). A sympathetic reader cares because the result converts a qualitative conjecture into an explicit, elementary counting statement that applies uniformly across uniformity parameters r.

Core claim

For r ≥ 3, k ≥ 3 and n ≥ (r-2)(k-2)+1, every linear r-uniform hypergraph H on n vertices satisfying |E(H)| ≥ ((k-2)/(r²((r-2)(k-2)+1)))n² + n/r contains k edges that together span at most (r-2)k+3 vertices. In the usual linear-density scaling this threshold is asymptotically c ≥ ((r-1)/r)·((k-2)/((r-2)(k-2)+1)) + o(1). The same counting argument recovers the large-uniformity form of the Brown-Erdős-Sós theorem and improves the previous triple-system constant.

What carries the argument

A local averaging argument that counts pairs consisting of an edge and a vertex outside it, using linearity to control pairwise intersections and obtain a global density contradiction.

If this is right

  • The asymptotic density threshold is c ≥ ((r-1)/r)·((k-2)/((r-2)(k-2)+1)) + o(1).
  • The argument yields a simple proof of the large-uniformity form of the Brown-Erdős-Sós theorem.
  • For r=3 the bound improves to c ≥ 2(k-2)/(3(k-1)) + o(1).
  • The result holds once n meets or exceeds (r-2)(k-2)+1.

Where Pith is reading between the lines

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

  • The same averaging technique could be tested on hypergraphs that are only approximately linear.
  • The explicit constant may be checked for sharpness by constructing random linear hypergraphs for small fixed r and k.
  • The method isolates the contribution of linearity, suggesting that removing the linearity hypothesis would require a different counting scheme.

Load-bearing premise

The hypergraph is linear, so any two edges share at most one vertex.

What would settle it

A linear r-uniform hypergraph on sufficiently large n with more than the stated number of edges yet containing no k edges on at most (r-2)k+3 vertices.

read the original abstract

In connection to the Brown-Erd\H{o}s-S\'os conjecture, we give a short local averaging proof of a density theorem for linear uniform hypergraphs. Let $r \ge 3$, $k \ge 3$, and suppose that $n \ge (r-2)(k-2)+1$. If $H$ is a linear $r$-uniform hypergraph on $n$ vertices and \[|E(H)| \geq \frac{k-2}{r^2((r-2)(k-2)+1)}n^2 + \frac{n}{r},\] then $H$ contains $k$ edges spanning at most $(r-2)k+3$ vertices. In the standard linear-density normalization, this gives the asymptotic density threshold $c \geq \frac{r-1}{r} \cdot \frac{k-2}{(r-2)(k-2)+1} + o(1)$. In particular, this yields a simple proof of the large-uniformity form of the Brown-Erd\H{o}s-S\'os theorem, due to Keevash and Long. In the case of triple systems, our bound becomes $c \geq \frac{2(k-2)}{3(k-1)} + o(1)$, improving upon a bound of $\frac{4}{5}$ due to Santos and Tyomkyn.

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

Summary. The manuscript gives a short local averaging proof that any linear r-uniform hypergraph H on n vertices (n ≥ (r-2)(k-2)+1) with |E(H)| ≥ [(k-2)/(r²((r-2)(k-2)+1))]n² + n/r edges must contain k edges spanning at most (r-2)k+3 vertices. In the linear-density normalization this yields the asymptotic threshold c ≥ ((r-1)/r)·((k-2)/((r-2)(k-2)+1)) + o(1). The argument recovers the large-uniformity case of the Brown-Erdős-Sós theorem (Keevash-Long) and improves the r=3 bound from 4/5 to 2(k-2)/(3(k-1)) + o(1).

Significance. If correct, the result supplies an elementary counting proof of an improved density threshold for a configuration central to the Brown-Erdős-Sós conjecture. The proof is short, avoids heavy machinery, and directly improves the best previously published constant for triple systems while also giving a new derivation of the Keevash-Long theorem for large r. These features make the manuscript a useful contribution to extremal hypergraph theory.

minor comments (2)
  1. §1, after the statement of the main theorem: the phrase 'in the standard linear-density normalization' is used without an explicit definition of the normalization; a one-sentence reminder of the precise scaling would help readers who are not specialists in the area.
  2. The +n/r additive term in the edge lower bound is retained throughout; the paper should briefly note whether this term can be absorbed into the o(n²) error when only the asymptotic density is required, or whether it is essential for the exact finite-n statement.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and their recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a direct local averaging proof deriving the stated density threshold from the linearity assumption and the given vertex lower bound n ≥ (r-2)(k-2)+1. The threshold constant appears explicitly in the hypothesis and is obtained by counting without parameter fitting, self-definition of the conclusion, or load-bearing self-citations. The argument improves on external prior bounds (Keevash-Long, Santos-Tyomkyn) and remains self-contained against the stated structural hypotheses.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard double-counting and averaging over pairs; no free parameters are fitted to data, no new entities are postulated, and the only background assumptions are the definition of linearity and basic counting lemmas.

axioms (2)
  • domain assumption Any two edges intersect in at most one vertex (linearity)
    Invoked as the structural hypothesis that makes the local averaging work; stated in the abstract.
  • standard math Standard double counting and averaging inequalities hold over finite sets
    Used implicitly in the local averaging proof; no section reference available from abstract alone.

pith-pipeline@v0.9.1-grok · 5784 in / 1349 out tokens · 17296 ms · 2026-06-25T18:58:34.339110+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

9 extracted references · 2 canonical work pages

  1. [1]

    W. G. Brown, P. Erd˝ os, and V. T. S´ os,Some extremal problems on r-graphs, New Directions in the Theory of Graphs (Proc. Third Ann. Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), Academic Press, New York, 1973, pp. 53–63

    1971

  2. [2]

    W. G. Brown, P. Erd˝ os, and V. T. S´ os,On the existence of triangulated spheres in 3-graphs, and related problems, Period. Math. Hungar.3(1973), no. 3-4, 221–228

    1973

  3. [3]

    Conlon, L

    D. Conlon, L. Gishboliner, Y. Levanzov and A. Shapira, A new bound for the Brown–Erd˝ os–S´ os problem, Journal of Combinatorial Theory, Series B, 158, pp.1-35, 2023

    2023

  4. [4]

    Janzer, A

    O. Janzer, A. Methuku, A. Milojevi´ c and B. Sudakov, Power saving for the Brown-Erd˝ os-S´ os problem,Discrete Analysis2025(2025), Paper No. 5, 16 pp

    2025

  5. [5]

    Keevash and J

    P. Keevash and J. Long,The Brown-Erd˝ os-S´ os conjecture for hypergraphs of large uniformity, arXiv preprint arXiv:2007.14824 (2020). to appear in Proc. Amer. Math. Soc

    work page arXiv 2007

  6. [6]

    I. Z. Ruzsa and E. Szemer´ edi, Triple systems with no six points carrying three triangles,Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. J´ anos Bolyai18, North-Holland, Amsterdam- New York (1978), 939–945

    1976

  7. [7]

    Santos and M

    G. Santos and M. Tyomkyn,The Brown-Erd˝ os-S´ os conjecture in dense triple systems, arXiv preprint arXiv:2508.09841 (2025)

    work page arXiv 2025

  8. [8]

    Shapira and M

    A. Shapira and M. Tyomkyn, A Ramsey variant of the Brown–Erd˝ os–S´ os conjecture, Bulletin of the London Mathematical Society, 53(5), pp.1453-1469, 2021

    2021

  9. [9]

    Shapira and M

    A. Shapira and M. Tyomkyn, A new approach for the Brown-Erd˝ os-S´ os problem, Israel Journal of Mathematics 267(2), pp.717-728, 2025. A SIMPLE COUNTING ARGUMENT FOR DENSE LINEAR HYPERGRAPHS 7 Department of Mathematics, University of Toronto, Toronto, ON, Canada Email address:lior.gishboliner@utoronto.ca Department of Mathematics, University of British Co...

    2025