Planar polynomials and an extremal problem of Fischer and Matousek

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 Matouusek 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}$.