SCHWEITZER 2008 Problem 3

A bipartite graph on the sets $\{ x_1,\ldots, x_n \}$ and $\{ y_1,\ldots, y_n\}$ of vertices (that is the edges are of the form $x_iy_j$ ) is called tame if it has no $x_iy_jx_ky_l$ path ( $i,j,k,l\in\{ 1,\ldots, n\}$ ) where $j<l$ and $i+j>k+l$ . Calculate the infimum of those real numbers $\alpha$ for which there exists a constant $c=c(\alpha)>0$ such that for all tame graphs $e\le cn^{\alpha}$ , where $e$ is the number of edges and $n$ is half of the number of vertices.

(translated by Miklós Maróti)