Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 49 min ago
PreprintarXiv licencearXiv

A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem

  • Xiangliang Kong
  • Chong Shangguan
  • Xin Wang
Open at sourcePDFDOICite

Abstract

Let f3(n,e+3,e) denote the maximum number of edges in an n-vertex $3$-uniform hypergraph containing no e distinct edges spanning at most e+3 vertices. It has long been conjectured that f3(n,e+3,e)≥ n2−o(1) for every fixed e≥3. We prove that f3(n,9,6)≥ n2exp(−O((log n)2/3)), settling the first unsolved case of the conjecture.

Related

  1. The quadratic Brown--Erdős--Sós problem for 3-uniform hypergraphs with 8 and 9 edges
    Levente Bodnár, Oleg Pikhurko, Shumin Sun +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
    Yoshiteru Ishida
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Asymptotics of the Brown--Erdős--Sós problem at integer exponents
    Ting-Wei Chao, Xinqi Huang, Hong Liu
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
    Santosh S. Vempala
    arXivPreprintarXiv licenceFull textAnalysis & PDEsOptimisation & controlarXiv
  5. A Quadratic Lower Bound on Determinantal Complexity
    Mrinal Kumar, Ben Lee Volk
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{kong2026nearquadratic,
  title = {{A near-quadratic lower bound for the Brown--Erdős--Sós $(9,6)$-problem}},
  author = {Xiangliang Kong and Chong Shangguan and Xin Wang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05261},
  eprint = {2611.05261},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05261},
}
RIS
TY  - UNPB
TI  - A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
AU  - Xiangliang Kong
AU  - Chong Shangguan
AU  - Xin Wang
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05261
UR  - https://arxiv.org/abs/2611.05261
AB  - Let f_3(n,e+3,e) denote the maximum number of edges in an n-vertex $3$-uniform hypergraph containing no e distinct edges spanning at most e+3 vertices. It has long been conjectured that f_3(n,e+3,e)≥ n^2−o(1) for every fixed e≥3. We prove that f_3(n,9,6)≥ n^2exp(−O((log n)^2/3)), settling the first unsolved case of the conjecture.
ER  -