TOPICS
Search

Ruzsa-Szemerédi Theorem

The Ruzsa-Szemerédi theorem, also called the (6,3)-theorem, states that a 3-uniform hypergraph on n vertices in which no six vertices contain three distinct hyperedges has o(n^2) hyperedges (Ruzsa and Szemerédi 1978). Here o denotes little-O notation.

Equivalently, if the union of every three distinct hyperedges has at least seven vertices, the number of hyperedges is subquadratic. The theorem does not require a linear hypergraph. It is the three-edge case of the Brown-Erdős-Sós conjecture.

This is problem 716 in the Erdős problems collection (Bloom 2026).

See also

Brown-Erdős-Sós Conjecture, Erdős Problems, Hypergraph

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 716." Accessed Oct. 26, 2026. https://www.erdosproblems.com/716.Ruzsa, I. Z. and Szemerédi, E. "Triple Systems with No Six Points Carrying Three Triangles." In Combinatorics, Vol. II (Proc. Fifth Hungarian Colloq., Keszthely, 1976) (Ed. A. Hajnal and V. T. Sós). Amsterdam, Netherlands: North-Holland, pp. 939-945, 1978.

Cite this as:

Weisstein, Eric W. "Ruzsa-Szemerédi Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Ruzsa-SzemerediTheorem.html

Subject classifications