MathDB

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)

3