Ruzsa–Szemerédi Problem¶
An extremal-combinatorics problem asking how dense an n-vertex graph can be when every edge lies in exactly one triangle, equivalently how many triples can be chosen with no three supported on six vertices.
Core Idea¶
The Ruzsa–Szemerédi problem, also called the (6,3)-problem, asks for the maximum size of a finite combinatorial structure subject to a sharp local sparsity condition. In its graph form, one seeks the largest number of edges in an \(n\)-vertex graph in which every edge lies in exactly one triangle. If \(f(n)\) denotes that maximum, the fundamental result is that \(f(n)=o(n^2)\), while constructions make \(f(n)\) only a slowly growing factor below quadratic. Determining the correct asymptotic gap remains the problem's organizing challenge.
Scope of Application¶
The home scope is extremal combinatorics. The problem measures how globally dense a structure can be when every small window is restricted. It illustrates a recurring phenomenon: local scarcity can force global sparsity even when no elementary counting argument reveals the loss.
In graph theory, locally linear or locally matched graphs expose the unique-triangle condition directly. In hypergraph theory, the six-vertices/two-triples form situates the result within forbidden-configuration problems. In additive combinatorics, progression-free subsets generate dense examples by encoding triples \((x,x+a,x+2a)\) across three vertex classes.
Clarity¶
A statement invoking the problem should specify:
- which formulation is being used;
- whether the graph is general, tripartite, or balanced bipartite;
- what \(n\) counts in that formulation;
- whether every edge lies in exactly one triangle or whether the edge set is partitioned into induced matchings;
- how many matchings are permitted and what their sizes are;
- whether the claim is exact, asymptotic, or only up to constant factors;
- which extremal function notation is in force; and
- whether a construction addresses the classical problem or a restricted linear-size-matching variant.
Manages Complexity¶
The equivalence compresses three families of arguments into one extremal invariant. Unique triangles make removal arguments transparent: destroying all triangles requires deleting at least one edge per triangle, and edge uniqueness prevents one deletion from eliminating many. Induced matchings expose decomposition and communication structure. Triple systems expose the forbidden six-point configuration.
Abstract Reasoning¶
The key upper-bound inference is a removal contradiction. Suppose a unique-triangle graph had a positive quadratic fraction of all possible edges. It would have only \(O(n^2)\) triangles, hence \(o(n^3)\). The triangle removal lemma says that deleting \(o(n^2)\) edges suffices to destroy every triangle. But because each edge lies in only one triangle, at least one edge per triangle must be removed; the number of edges and triangles are proportional. Positive quadratic density would then require \(\Omega(n^2)\) deletions, a contradiction.
Knowledge Transfer¶
Within combinatorics, the vocabulary transfers literally: extremal function, forbidden configuration, induced matching, tripartite reduction, removal lemma, and progression-free construction retain the same roles. A proof improvement in triangle removal immediately sharpens the unique-triangle upper bound after the quantitative dependence is evaluated.
In streaming and communication complexity, a collection of induced matchings provides many dense, separately addressable payloads. A hidden index can select one matching while the combined graph conceals which edges matter. The density of available Ruzsa–Szemerédi graphs then controls the strength of lower bounds or approximation barriers.
Relationships to Other Abstractions¶
Current abstraction Ruzsa–Szemerédi Problem Domain-specific
Parents (1) — more general patterns this builds on
-
Ruzsa–Szemerédi Problem is a kind of Optimization Prime
Optimization is the minimal prospective parent.
Hierarchy path (1) — routes to 1 parentless root
- Ruzsa–Szemerédi Problem → Optimization
Neighborhood in Abstraction Space¶
Ruzsa–Szemerédi Problem sits in a sparse region of the domain-specific corpus (82nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Advanced Probability & Combinatorial Bounds (6 abstractions)
Nearest neighbors
- Turán Graph — 0.83
- Variational Message Passing — 0.82
- Matching — 0.82
- Hadwiger number — 0.81
- Sequential Dynamical System — 0.80
Computed from structural-signature embeddings · 2026-09-08