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 n {\displaystyle n} 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 n 2 {\displaystyle n^{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.
What is the maximum possible number of edges in a graph with n {\displaystyle n} vertices in which every edge belongs to a unique triangle? The graphs with this property are called locally linear graphs or locally matched graphs. What is the maximum possible number of edges in a bipartite graph with n {\displaystyle n} vertices on each side of its bipartition, whose edges can be partitioned into n {\displaystyle n} induced subgraphs that are each matchings? What is the largest possible number of triples of points that one can select from n {\displaystyle n} given points, in such a way that every six points contain at most two of the selected triples? 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 n {\displaystyle n} vertices to the graph, one for each induced matching, and add edges from vertices u {\displaystyle u} and v {\displaystyle v} of the bipartite graph to vertex w {\displaystyle w} in this third set whenever bipartite edge u v {\displaystyle uv} belongs to induced matching w {\displaystyle w} . The result is a balanced tripartite graph with 3 n {\displaystyle 3n} 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.
… excerpt ends here. Continue reading the full article.
