Abstract
Let $G$ be a 3-partite graph with $k$ vertices in each part and suppose that
between any two parts, there is no cycle of length four. Fischer and
Matou\u{s}ek asked for the maximum number of triangles in such a graph. A
simple construction involving arbitrary projective planes shows that there is
such a graph with $(1 - o(1)) k^{3/2} $ triangles, and a double counting
argument shows that one cannot have more than $(1+o(1)) k^{7/4} $ triangles.
Using affine planes defined by specific planar polynomials over finite fields,
we improve the lower bound to $(1 - o(1)) k^{5/3}$.