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.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2701
Origin domain: mathematics
Subdomain: extremal combinatorics
Aliases: (6,3)-problem, Ruzsa–Szemerédi (6,3)-problem, Ruzsa–Szemerédi induced-matching problem

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^[1]. Determining the correct asymptotic gap remains the problem's organizing challenge.

The same extremal quantity has equivalent formulations, up to constant-factor changes in the vertex parameter and objective. A balanced bipartite graph may have its edges partitioned into a linear number of induced matchings. A 3-uniform hypergraph may contain many triples while every six vertices support at most two triples. Each formulation makes a different mechanism visible: unique triangles, induced-matching decomposition, or forbidden local triple density.

The abstraction is not merely a theorem that dense configurations are impossible. It is a translation hub joining extremal graph theory, hypergraph theory, additive combinatorics, graph-removal methods, and streaming lower bounds. Its identity includes the extremal function, its equivalent encodings, the subquadratic upper-bound phenomenon, the nearly quadratic construction program, and the unresolved quantitative gap between them.

Structural Signature¶

The mandatory roles are:

a size parameter \(n\);
a finite graph, balanced bipartite graph, or 3-uniform set system normalized to that parameter;
an objective counting edges or selected triples;
a local uniqueness or sparsity constraint;
an extremal function taking the maximum objective over all admissible structures;
constant-factor reductions among the three standard formulations;
an upper-bound route through triangle removal or related regularity machinery;
a lower-bound route through large sets avoiding three-term arithmetic progressions;
asymptotic notation distinguishing linear, subquadratic, and nearly quadratic regimes; and
an open quantitative gap rather than a known exact growth rate.

The graph formulation is:

maximize \(|E(G)|\) over \(n\)-vertex graphs \(G\), subject to every edge belonging to exactly one triangle.

The hypergraph formulation asks for the largest family of triples on \(n\) points such that no six points carry three of the chosen triples. The induced-matching formulation asks how dense a balanced bipartite graph can be when its edge set is decomposable into \(O(n)\) induced matchings. Conversions preserve density to constant factors, not literal equality under an unchanged \(n\).

What It Is Not¶

It is not the ordinary maximum matching problem. A matching is one vertex-disjoint edge set; the induced-matching formulation partitions an entire dense graph into many matchings, each of which must be induced in the ambient graph.

It is not merely the triangle-free extremal problem. Admissible graphs contain many triangles; the condition is that each edge belongs to exactly one of them. The triangles are edge-disjoint, while vertices may participate in several triangles.

It is not the graph removal lemma. Triangle removal supplies the qualitative subquadratic upper bound and later quantitative improvements, but it is a more general theorem about graphs with few triangles being close to triangle-free^[2].

It is not Behrend's progression-free-set problem. Behrend-type sets supply lower-bound constructions, but the Ruzsa–Szemerédi object is a graph or triple system and requires a conversion^[3].

It is not an exact finite-\(n\) classification. The principal question is asymptotic density; constants and normalization vary among equivalent forms.

It is not the full Brown–Erdős–Sós conjecture. The \((6,3)\) case is a particular extremal triple-system problem with a celebrated resolution at the \(o(n^2)\) level^[4].

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.

The induced-matching form is influential in theoretical computer science. Dense Ruzsa–Szemerédi graphs provide hard communication instances and govern bounds for graph-streaming matching approximations^[5]. Related constructions appear in property testing and in analyses of how sparse a certificate can be while preserving matching information across many vertex subsets.

The node includes the equivalence machinery because it is what transports bounds between fields. A result proved for one standard formulation becomes a result for the others after the parameter blow-up and constant losses are tracked.

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.

“Unique triangle” means exactly one triangle per edge, not one triangle per vertex or one triangle in the entire graph. “Induced matching” means that among all endpoints of the matching edges the ambient graph contains no additional edges. Ordinary edge-disjoint matchings are too weak.

The phrase “nearly quadratic” also needs its denominator. A lower bound such as \(n^2/\exp(O(\sqrt{\log n}))\) is subquadratic but exceeds \(n^{2-\varepsilon}\) for every fixed positive \(\varepsilon\) at sufficiently large \(n\)^[1]. It does not mean a constant fraction of all possible edges.

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.

This lets an analyst select the representation suited to the proof. Lower bounds move to additive sets because progression avoidance is easier to construct arithmetically. Upper bounds move to triangle removal because a graph with few triangles yet requiring many deletions would contradict the removal lemma. Algorithmic reductions move to induced matchings because each matching can encode a separate hidden choice.

The abstraction also distinguishes qualitative and quantitative progress. Proving \(o(n^2)\) settles the density-zero question but leaves enormous room between known upper and lower rates. The extremal-function view records both achievements without treating the qualitative theorem as an exact solution.

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.

The key lower-bound inference converts arithmetic nonstructure into graph uniqueness. Choose a large set \(A\) with no nontrivial three-term arithmetic progression. Across three copies of a cyclic group, insert triangles indexed by \(x\) and \(a\in A\), with vertices corresponding to \(x\), \(x+a\), and \(x+2a\). A second triangle sharing an edge would force an arithmetic progression among step values, so progression avoidance guarantees edge uniqueness.

The equivalence to induced matchings is constructive. Starting from a balanced bipartite graph whose edges are partitioned into induced matchings, add a third vertex class with one vertex naming each matching. Connect that name to the endpoints of every edge in its matching. Each original edge becomes a triangle, and inducedness blocks unintended triangles. Reversing the construction deletes one class and groups edges by the deleted triangle vertex.

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.

The concept should not be generalized to every situation with “local sparsity but global density.” That phrase is a portable analogy, but the exact node depends on triangles, six-point triple systems, and induced matchings. The substrate-neutral core belongs to Constraint and Optimization; this entry preserves the mathematical machinery.

Examples¶

Tripartite arithmetic construction. Let each of three vertex classes be a copy of \(\mathbb{Z}_p\), and let \(A\subseteq\mathbb{Z}_p\) contain no nontrivial three-term arithmetic progression. For every \(x\) and \(a\in A\), add the triangle \((x,x+a,x+2a)\) across the classes. The result has \(3p\) vertices and \(3p|A|\) edges, with every edge in exactly one triangle.

Induced-matching encoding. Begin with a balanced bipartite graph decomposed into \(n\) induced matchings. Add one new vertex for each matching and connect it to both endpoints of every edge in that matching. The three-part graph has the unique-triangle property.

Non-example: disjoint triangles. A union of vertex-disjoint triangles satisfies the unique-triangle condition but has only linearly many edges. It is admissible yet far from extremal, showing that satisfying the constraint is not the same as approaching the optimum.

Non-example: complete tripartite graph. It is dense, but each edge lies in many triangles, so it violates uniqueness.

Streaming use. A dense graph partitioned into large induced matchings can encode one of many matching instances. Space lower bounds inherit their strength from how dense such a graph can be.

Structural Tensions¶

Local uniqueness versus global density. Every edge has only one triangular witness, yet the objective seeks almost quadratically many edges.

Equivalent structure versus normalization loss. Reductions expose one invariant while changing vertex counts and constants.

Qualitative resolution versus quantitative uncertainty. The \(o(n^2)\) theorem settles zero limiting density but leaves the precise slowly growing deficit unresolved.

Regularity power versus bound weakness. Removal and regularity arguments prove broad qualitative statements while traditionally producing poor quantitative dependence.

Arithmetic construction versus graph objective. The best lower-bound ideas live in progression-free sets, requiring translation before they count graph edges.

General extremal problem versus algorithmic restricted variants. Streaming applications often require each induced matching to have linear size, a stronger condition whose best density may differ.

Structural–Framed Character¶

The Ruzsa–Szemerédi problem is structurally precise but domain-specific. It is medium-neutral only inside closely linked mathematical representations: graphs, hypergraphs, and set systems. Its identity depends on triangle incidence, induced subgraphs, asymptotic edge counts, and extremal reductions.

The cross-form equivalence is genuine mathematical transfer, not metaphor. Yet replacing vertices and edges with arbitrary entities strips away the theorems and open bounds. The candidate is therefore a mathematical domain abstraction rather than a substrate-independent prime.

Structural Core vs. Domain Accent¶

The structural core is:

maximize global density subject to a fixed local uniqueness constraint, then transport bounds through equivalent encodings.

The domain accent makes “density” an edge or triple count and makes “local uniqueness” exactly one triangle per edge, at most two triples on any six vertices, or a partition into induced matchings. It supplies graph removal, additive progression avoidance, and asymptotic extremal notation.

Optimization captures the maximize-under-constraint skeleton. Constraint captures admissibility. Neither carries the three equivalent formulations or the central subquadratic-versus-nearly-quadratic gap.

Optimization is the minimal prospective parent. The problem explicitly maximizes an objective—the edge or triple count—over a feasible family defined by a combinatorial constraint.

Constraint supplies the unique-triangle or six-point admissibility rule. Network supplies the graph substrate. Matching is the nearest domain-specific neighbor because one formulation partitions edges into induced matchings, but it is not a universal taxonomic parent of the unique-triangle or triple-system object. Equivalence explains transport among encodings. Approximation and Asymptotic Analysis govern the unresolved growth-rate comparison.

Only Optimization is proposed as a DAG edge.

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 (82^nd 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

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Matching: one set of pairwise vertex-disjoint edges; the Ruzsa–Szemerédi formulation uses many induced matchings covering a graph.
Induced matching: a component object, not the extremal density problem.
Triangle-free graph: forbids all triangles, whereas admissible graphs here are unions of edge-unique triangles.
Triangle removal lemma: the upper-bound tool, not the extremal problem.
Brown–Erdős–Sós conjecture: a broader family of hypergraph extremal questions.
Roth's theorem: concerns three-term arithmetic progressions in dense integer sets and is connected through removal arguments.
Behrend construction: supplies progression-free sets used for lower bounds.
Strong chromatic index: minimizes the number of induced matchings needed to partition a fixed graph; the present problem maximizes density under a linear partition budget.
Ruzsa–Szemerédi graph: an admissible graph or a parameterized induced-matching construction; the “problem” asks for the extremal size.

References¶

[1] Ruzsa, I. Z. and Szemeredi, E. “Triple systems with no six points carrying three triangles”. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II; Colloquia Mathematica Societatis Janos Bolyai 18; North-Holland, Amsterdam-New York, 1978. The originating paper, which proves the (6,3)-theorem f(n) = o(n^2) and gives the Behrend-derived construction placing f(n) only a slowly growing factor below quadratic. The source of the n^2/exp(O(sqrt(log n))) construction whose growth rate this sentence characterises; the comparison with n^(2-epsilon) is elementary asymptotics. registry ↩a ↩b

[2] Fox. “A new proof of the graph removal lemma”. Annals of Mathematics, 2011. Fox's proof of the graph removal lemma in its general form – every n-vertex graph with o(n^h) copies of a fixed H can be made H-free by deleting o(n^2) edges – with a bound better than the regularity-lemma proof gives; the original subquadratic bound for this problem is Ruzsa-Szemeredi's. registry ↩

[3] Behrend. “On Sets of Integers Which Contain No Three Terms in Arithmetical Progression”. Proceedings of the National Academy of Sciences, 1946. Behrend's construction of dense sets of integers containing no three terms in arithmetic progression, which is the arithmetic input to the lower bound; the conversion into a graph or triple system is Ruzsa-Szemeredi's. registry ↩

[4] Brown, W. G., Erdos, P., and Sos, V. T. “Some extremal problems on r-graphs”. New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), Academic Press, New York, 1973. The Brown-Erdos-Sos paper that poses the general extremal problem on r-graphs and conjectures the o(n^2) bound for every (e+3, e) configuration, of which (6,3) is the first non-trivial case; the resolution of that case is Ruzsa-Szemeredi 1978. registry ↩

[5] Goel, Kapralov, and Khanna. “On the communication and streaming complexity of maximum bipartite matching”. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012. Shows that the smallest epsilon-matching cover of a graph is essentially the size of the largest epsilon-Ruzsa-Szemeredi graph on the same vertex set, and uses that to prove superlinear communication and one-pass streaming lower bounds for better-than-⅔ bipartite matching approximation. registry ↩