Let
F be a graph,
k
≥
2 be an integer, and write
ex
χ
≤
k
(
n
,
F
) for the maximum number of edges in an
n‐vertex graph that is
k‐partite and has no subgraph isomorphic to
F. The function
ex
χ
≤
2
(
n
,
F
) has been studied by many researchers. Finding
ex
χ
≤
2
(
n
,
K
s
,
t
) is a special case of the Zarankiewicz problem. We prove an analog of the Kövári‐Sós‐Turán theorem for 3‐partite graphs by showing
ex
χ
≤
3
(
n
,
K
s
,
t
)
≤
1
3
1
−
1
∕
s
t
−
1
2
+
o
(
1
)
1
∕
s
n
2
−
1
∕
s for
2
≤
s
≤
t. Using Sidon sets constructed by Bose and Chowla, we prove that this upper bound is asymptotically best possible in the case that
s
=
2 and
t
≥
3 is odd, that is,
ex
χ
≤
3
(
n
,
K
2
,
2
t
+
1
)
=
t
3
n
3
∕
2
+
o
(
n
3
∕
2
) for
t
≥
1. In the cases of
K
2
,
t and
K
3
,
3, we use a result of Allen, Keevash, Sudakov, and Verstraëte, to show that a similar upper bound holds for all
k
≥
3 and gives a better constant when
s
=
t
=
3. Finally, we point out an interesting connection between difference families from design theory and
ex
χ
≤
3
(
n
,
C
4
).
- The Zarankiewicz problem in 3‐partite graphs
- Michael Tait - Carnegie Mellon UniversityCraig Timmons - California State University‐Sacramento
- Mathematics/Statistics Department
- 06/2019
- National Science Foundation (1606350) Simons Foundation (#359419)
- 99257846886801671; https://hdl.handle.net/20.500.12741/rep:3486; https://doi.org/10.1002/jcd.21654
- English
- 15