The nine-vertex
Paley graph , a balanced tripartite graph with 18 edges, each belonging to exactly one triangle
Several views of the
BrouwerâHaemers graph , a non-tripartite 20-regular graph with 81 vertices in which each edge belongs to exactly one triangle
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.
[1]
The following questions all have answers that are
asymptotically equivalent: they differ by, at most, constant factors from each other.
[1]
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?
[2] The graphs with this property are called
locally linear graphs
[3] or locally matching graphs.
[4]
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 ?
[1]
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?
[5]
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.
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
p
{\displaystyle p}
have large
SalemâSpencer sets , subsets
A
{\displaystyle A}
of size
|
A
|
=
p
/
e
O
(
log
p
)
{\displaystyle |A|=p/e^{O({\sqrt {\log p}})}}
with no three-term
arithmetic progressions .
[6]
Behrend's result can be used to construct tripartite graphs in which each side of the tripartition has
p
{\displaystyle p}
vertices, there are
3
|
A
|
p
{\displaystyle 3|A|p}
edges, and each edge belongs to a unique triangle. Thus, with this construction,
n
=
3
p
{\displaystyle n=3p}
and the number of edges is
n
2
/
e
O
(
log
n
)
{\displaystyle n^{2}/e^{O({\sqrt {\log n}})}}
.
[5]
To construct a graph of this form from Behrend's arithmetic-progression-free subset
A
{\displaystyle A}
, number the vertices on each side of the tripartition from
0
{\displaystyle 0}
to
p
−
1
{\displaystyle p-1}
, and construct triangles of the form
(
x
,
x
+
a
,
x
+
2
a
)
{\displaystyle (x,x+a,x+2a)}
modulo
p
{\displaystyle p}
for each
x
{\displaystyle x}
in the range from
0
{\displaystyle 0}
to
p
−
1
{\displaystyle p-1}
and each
a
{\displaystyle a}
in
A
{\displaystyle A}
. For example, with
p
=
3
{\displaystyle p=3}
and
A
=
{
±
1
}
{\displaystyle A=\{\pm 1\}}
, 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
(
x
,
x
+
a
,
x
+
a
+
b
)
{\displaystyle (x,x+a,x+a+b)}
where
a
{\displaystyle a}
,
b
{\displaystyle b}
, and
c
=
(
a
+
b
)
/
2
{\displaystyle c=(a+b)/2}
all belong to
A
{\displaystyle A}
, violating the assumption that there be no arithmetic progressions
(
a
,
c
,
b
)
{\displaystyle (a,c,b)}
in
A
{\displaystyle A}
.
[5]
The
SzemerĂ©di regularity lemma can be used to prove that any solution to the RuzsaâSzemerĂ©di problem has at most
o
(
n
2
)
{\displaystyle o(n^{2})}
edges or triples.
[5] A stronger form of the
graph removal lemma by
Jacob Fox implies that the size of a solution is at most
n
2
/
e
Ω
(
log
∗
n
)
{\displaystyle n^{2}/e^{\Omega (\log ^{*}n)}}
. Here the
o
{\displaystyle o}
and
Ω
{\displaystyle \Omega }
are instances of
little o and big Omega notation , and
log
∗
{\displaystyle \log ^{*}}
denotes the
iterated logarithm .
Fox proves that, in any
n
{\displaystyle n}
-vertex graph with
O
(
n
3
−
δ
)
{\displaystyle O(n^{3-\delta })}
triangles for some
δ
>
0
{\displaystyle \delta >0}
, one can find a
triangle-free subgraph by removing at most
n
2
/
e
Ω
(
log
∗
n
)
{\displaystyle n^{2}/e^{\Omega (\log ^{*}n)}}
edges.
[7] In a graph with the unique triangle property, there are (naively)
O
(
n
2
)
{\displaystyle O(n^{2})}
triangles, so this result applies with
δ
=
1
{\displaystyle \delta =1}
. 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.
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.
[5] 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
Ω
(
n
3
/
2
)
{\displaystyle \Omega (n^{3/2})}
,
[8] and conjectured that it was
o
(
n
2
)
{\displaystyle o(n^{2})}
.
[9] 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.
[5]
Tripod packing , one of the applications of the upper bounds on the RuzsaâSzemerĂ©di problem
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 .
[10] 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
H
{\displaystyle H}
, with one-sided error in a number of queries polynomial in the error parameter, if and only if
H
{\displaystyle H}
is a
bipartite graph .
[11]
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.
[12]
[13]
[14]
[15]
The subquadratic upper bound on the RuzsaâSzemerĂ©di problem was also used to provide an
o
(
3
n
)
{\displaystyle o(3^{n})}
bound on the size of
cap sets ,
[16]
before stronger bounds of the form
c
n
{\displaystyle c^{n}}
for
c
<
3
{\displaystyle c<3}
were proven for this problem.
[17] It also provides the best known upper bound on
tripod packing .
[18]
^
a
b
c KomlĂłs, J.; Simonovits, M. (1996), "SzemerĂ©di's regularity lemma and its applications in graph theory", Combinatorics, Paul ErdĆs is eighty, Vol. 2 (Keszthely, 1993) , Bolyai Soc. Math. Stud., vol. 2, Budapest: JĂĄnos Bolyai Math. Soc., pp. 295â352,
CiteSeerX
10.1.1.31.2310 ,
MR
1395865
^ Clark, L. H.; Entringer, R. C.; McCanna, J. E.; Székely, L. A. (1991),
"Extremal problems for local properties of graphs" (PDF) , The Australasian Journal of Combinatorics , 4 : 25â31,
MR
1129266
^ FronÄek, Dalibor (1989), "Locally linear graphs", Mathematica Slovaca , 39 (1): 3â6,
hdl :
10338.dmlcz/136481 ,
MR
1016323
^ Larrión, F.; Pizaña, M. A.; Villarroel-Flores, R. (2011),
"Small locally nK 2 graphs" (PDF) , Ars Combinatoria , 102 : 385â391,
MR
2867738
^
a
b
c
d
e
f
Ruzsa, I. Z. ;
SzemerĂ©di, E. (1978), "Triple systems with no six points carrying three triangles", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II , Colloq. Math. Soc. JĂĄnos Bolyai, vol. 18, Amsterdam and New York: North-Holland, pp. 939â945,
MR
0519318
^
Behrend, F. A. (December 1946), "On sets of integers which contain no three terms in arithmetical progression",
Proceedings of the National Academy of Sciences , 32 (12): 331â332,
doi :
10.1073/pnas.32.12.331 ,
PMC
1078964 ,
PMID
16578230
^
Fox, Jacob (2011), "A new proof of the graph removal lemma",
Annals of Mathematics , Second Series, 174 (1): 561â579,
arXiv :
1006.1300 ,
doi :
10.4007/annals.2011.174.1.17 ,
MR
2811609
^
SĂłs, V. T. ;
ErdĆs, P. ;
Brown, W. G. (1973),
"On the existence of triangulated spheres in 3-graphs, and related problems" (PDF) , Periodica Mathematica Hungarica , 3 (3â4): 221â228,
doi :
10.1007/BF02018585 ,
MR
0323647
^
Brown, W. G. ;
ErdĆs, P. ;
SĂłs, V. T. (1973),
"Some extremal problems on r -graphs" (PDF) , New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich, 1971) , New York: Academic Press, pp. 53â63,
MR
0351888
^
HĂ„stad, Johan ;
Wigderson, Avi (2003),
"Simple analysis of graph tests for linearity and PCP" (PDF) , Random Structures & Algorithms , 22 (2): 139â160,
doi :
10.1002/rsa.10068 ,
MR
1954608
^
Alon, Noga (2002),
"Testing subgraphs in large graphs" (PDF) , Random Structures & Algorithms , 21 (3â4): 359â370,
doi :
10.1002/rsa.10056 ,
MR
1945375
^ Goel, Ashish; Kapralov, Michael;
Khanna, Sanjeev (2012),
"On the communication and streaming complexity of maximum bipartite matching" (PDF) , Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms , New York: ACM, pp. 468â485,
MR
3205231
^ Kapralov, Michael (2013), "Better bounds for matchings in the streaming model", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , Philadelphia, Pennsylvania: SIAM, pp. 1679â1697,
arXiv :
1206.2269 ,
doi :
10.1137/1.9781611973105.121 ,
ISBN
978-1-61197-251-1 ,
MR
3203007
^ Konrad, Christian (2015), "Maximum matching in turnstile streams", AlgorithmsâESA 2015 , Lecture Notes in Comput. Sci., vol. 9294, Heidelberg: Springer, pp. 840â852,
arXiv :
1505.01460 ,
doi :
10.1007/978-3-662-48350-3_70 ,
ISBN
978-3-662-48349-7 ,
MR
3446428
^
Fox, Jacob ; Huang, Hao;
Sudakov, Benny (2017), "On graphs decomposable into induced matchings of linear sizes",
Bulletin of the London Mathematical Society , 49 (1): 45â57,
arXiv :
1512.07852 ,
doi :
10.1112/blms.12005 ,
MR
3653100
^
Frankl, P. ;
Graham, R. L. ;
Rödl, V. (1987), "On subsets of abelian groups with no 3-term arithmetic progression",
Journal of Combinatorial Theory , Series A, 45 (1): 157â161,
doi :
10.1016/0097-3165(87)90053-7 ,
MR
0883900
^
Ellenberg, Jordan S. ; Gijswijt, Dion (2017), "On large subsets of
F
q
n
{\displaystyle \mathbb {F} _{q}^{n}}
with no three-term arithmetic progression",
Annals of Mathematics , Second Series, 185 (1): 339â343,
arXiv :
1605.09223 ,
doi :
10.4007/annals.2017.185.1.8 ,
MR
3583358
^
Gowers, W. T. ; Long, J. (2016), The length of an
s
{\displaystyle s}
-increasing sequence of
r
{\displaystyle r}
-tuples ,
arXiv :
1609.08688