TOPICS
Search

Erdős-Sós Bipartite-Link Conjecture


The Erdős-Sós bipartite-link conjecture asserts that a 3-uniform hypergraph on n vertices whose every vertex link is a bipartite graph has at most (1/4+o(1))(n; 3) edges as n->infty. The link of a vertex v has the remaining vertices as its vertices and an edge {x,y} precisely when {v,x,y} is a hyperedge. This conjecture is distinct from the Erdős-Sós theorem about trees in graphs.

Yang (2026) constructed a counterexample with 497 vertices and 5115152 edges, all of whose vertex links are bipartite. Replacing each vertex by k vertices and each hyperedge by all triples from the corresponding three classes gives such hypergraphs on n=497k vertices with

 (1/(24)+(25)/(420903336))n^3

edges. Their limiting edge density is 1/4+150/420903336, strictly greater than 1/4. Yang (2026) reports using GPT-6.1 for strategies and proof checks, with the results reviewed by the author.


See also

Bipartite Graph, Erdős-Sós Theorem, Hypergraph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Yang, T. "A Counterexample to the Erdős-Sós Bipartite-Link Conjecture." 8 Oct 2026. https://arxiv.org/abs/2610.11642.

Cite this as:

Weisstein, Eric W. "Erdős-Sós Bipartite-Link Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Erdos-SosBipartite-LinkConjecture.html

Subject classifications