PreprintarXiv licencearXiv
A counterexample to the Erdős--Sós bipartite-link conjecture
Abstract
Erdős and Sós conjectured that every n-vertex $3$-uniform hypergraph whose link graphs are all bipartite has at most (1/4+o(1))binom n3 edges. We disprove this conjecture by constructing counterexamples with edge density at least 0.250000356>1/4 for all sufficiently large n.
Related
- A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
- Delocalized region of bipartite Erdős-Rényi graphs
- Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
- A counterexample to a conjecture of Duncan on versal actions
- The Erdős--Chvátal Simplex Conjecture
BibTeX
@misc{yang2026counterexample,
title = {{A counterexample to the Erdős--Sós bipartite-link conjecture}},
author = {Tianchi Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11642},
eprint = {2610.11642},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11642},
}
RIS
TY - UNPB
TI - A counterexample to the Erdős--Sós bipartite-link conjecture
AU - Tianchi Yang
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11642
UR - https://arxiv.org/abs/2610.11642
AB - Erdős and Sós conjectured that every n-vertex $3$-uniform hypergraph whose link graphs are all bipartite has at most (1/4+o(1))binom n3 edges. We disprove this conjecture by constructing counterexamples with edge density at least 0.250000356>1/4 for all sufficiently large n.
ER -