In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a 
graph in which every edge belongs to a unique triangle.
Equivalently it asks for the maximum number of edges in a balanced bipartite graph whose edges can be partitioned into a linear number of induced matchings, or the maximum number of triples one can choose from formula_1 points so that every six points contain at most two triples. The problem is named after Imre Z. Ruzsa and Endre Szemerédi, who first proved that its answer is smaller than formula_2 by a slowly-growing (but still unknown) factor.
Equivalence between formulations.
The following questions all have answers that are asymptotically equivalent: they differ by, at most, constant factors from each other.
The Ruzsa–Szemerédi problem asks for the answer to these equivalent questions.
To convert the bipartite graph induced matching problem into the unique triangle problem, add a third set of formula_1 vertices to the graph, one for each induced matching, and add edges from vertices formula_8 and formula_9 of the bipartite graph to vertex formula_10 in this third set whenever
bipartite edge formula_11 belongs to induced matching formula_10.
The result is a balanced tripartite graph with formula_13 vertices and the unique triangle property. In the other direction, an arbitrary graph with the unique triangle property can be made into a balanced tripartite graph by choosing a partition of the vertices into three equal sets randomly and keeping only the triangles that respect the partition. This will retain (in expectation) a constant fraction of the triangles and edges. A balanced tripartite graph with the unique triangle property can be made into a partitioned bipartite graph by removing one of its three subsets of vertices, and making an induced matching on the neighbors of each removed vertex.
To convert a graph with a unique triangle per edge into a triple system,
let the triples be the triangles of the graph. No six points can include three triangles without either two of the three triangles sharing an edge or all three triangles forming a fourth triangle that shares an edge with each of them.
In the other direction, to convert a triple system into a graph, first eliminate any sets of four points that contain two triples. These four points cannot participate in any other triples, and so cannot contribute towards a more-than-linear total number of triples. Then, form a graph connecting any pair of points that both belong to any of the remaining triples.
Lower bound.
A nearly-quadratic lower bound on the Ruzsa–Szemerédi problem can be derived from a result of Felix Behrend, according to which the numbers modulo an odd prime number formula_14 have large Salem–Spencer sets, subsets formula_15 of size formula_16 with no three-term arithmetic progressions.
Behrend's result can be used to construct tripartite graphs in which each side of the tripartition has formula_14 vertices, there are formula_18 edges, and each edge belongs to a unique triangle. Thus, with this construction, formula_19 and the number of edges is formula_20.
To construct a graph of this form from Behrend's arithmetic-progression-free subset formula_15, number the vertices on each side of the tripartition from formula_22 to formula_23, and construct triangles of the form formula_24 modulo formula_14 for each formula_26 in the range from formula_22 to formula_23 and each formula_29 in formula_15. For example, with formula_31 and formula_32, the result is a nine-vertex balanced tripartite graph with 18 edges, shown in the illustration. The graph formed from the union of these triangles has the desired property that every edge belongs to a unique triangle. For, if not, there would be a triangle formula_33 where formula_29, formula_35, and formula_36 all belong to formula_15, violating the assumption that there be no arithmetic progressions formula_38 in formula_15.
Upper bound.
The Szemerédi regularity lemma can be used to prove that any solution to the Ruzsa–Szemerédi problem has at most formula_40 edges or triples. A stronger form of the graph removal lemma by Jacob Fox implies that the size of a solution is at most formula_41. Here the formula_42 and formula_43 are instances of little o and big Omega notation, and formula_44 denotes the iterated logarithm.
Fox proves that, in any formula_1-vertex graph with formula_46 triangles for some formula_47, one can find a triangle-free subgraph by removing at most formula_41 edges. In a graph with the unique triangle property, there are (naively) formula_49 triangles, so this result applies with formula_50. But in this graph, each edge removal eliminates only one triangle, so the number of edges that must be removed to eliminate all triangles is the same as the number of triangles.
History.
The problem is named after Imre Z. Ruzsa and Endre Szemerédi, who studied this problem, in the formulation involving triples of points, in a 1978 publication. However, it had been previously studied by W. G. Brown, Paul Erdős, and Vera T. Sós, in two publications in 1973 which
proved that the maximum number of triples can be formula_51, and conjectured that it was formula_40. Ruzsa and Szemerédi provided (unequal) nearly-quadratic upper and lower bounds for the problem, significantly improving the previous lower bound of Brown, Erdős, and Sós, and proving their conjecture.
Applications.
The existence of dense graphs that can be partitioned into large induced matchings has been used to construct efficient tests for whether a Boolean function is linear, a key component of the PCP theorem in computational complexity theory. In the theory of property testing algorithms, the known results on the Ruzsa–Szemerédi problem have been applied to show that it is possible to test whether a graph has no copies of a given subgraph formula_53, with one-sided error in a number of queries polynomial in the error parameter, if and only if formula_53 is a bipartite graph.
In the theory of streaming algorithms for graph matching (for instance to match internet advertisers with advertising slots), the quality of matching covers (sparse subgraphs that approximately preserve the size of a matching in all vertex subsets) is closely related to the density of bipartite graphs that can be partitioned into induced matchings. This construction uses a modified form of the Ruzsa-Szemerédi problem in which the number of induced matchings can be much smaller than the number of vertices, but each induced matching must cover most of the vertices of the graph. In this version of the problem, it is possible to construct graphs with a non-constant number of linear-sized induced matchings, and this result leads to nearly-tight bounds on the approximation ratio of streaming matching algorithms.
The subquadratic upper bound on the Ruzsa–Szemerédi problem was also used to provide an formula_55 bound on the size of cap sets,
before stronger bounds of the form formula_56 for formula_57 were proven for this problem. It also provides the best known upper bound on tripod packing.
References.
 ;templatestyles src="Reflist/styles.css" / ;