Bipartite algebraic graphs without quadrilaterals

Abstract

Let ${\mathbb{P}}^s$ be the $s$-dimensional complex projective space, and let $X,Y$ be two non-empty open subsets of ${\mathbb{P}}^s$ in the Zariski topology. A hypersurface $H$ in ${\mathbb{P}}^s\times {\mathbb{P}}^s$ induces a bipartite graph $G$ as follows: the partite sets of $G$ are $X$ and $Y$, and the edge set is defined by $\overline{u}\sim \overline{v}$ if and only if $(\overline{u},\overline{v})\in H$. Motivated by the Turán problem for bipartite graphs, we say that $H\cap (X\times Y)$ is $(s,t)$-grid-free provided that $G$ contains no complete bipartite subgraph that has $s$ vertices in $X$ and $t$ vertices in $Y$. We conjecture that every $(s,t)$-grid-free hypersurface is equivalent, in a suitable sense, to a hypersurface whose degree in $\overline{y}$ is bounded by a constant $d=d(s,t)$, and we discuss possible notions of the equivalence. We establish the result that if $H\cap (X\times {\mathbb{P}}^2)$ is $(2,2)$-grid-free, then there exists $F\in \mathbb{C}[\overline{x},\overline{y}]$ of degree $\le 2$ in $\overline{y}$ such that $H\cap (X\times {\mathbb{P}}^2)=\{F=0\}\cap (X\times {\mathbb{P}}^2)$. Finally, we transfer the result to algebraically closed fields of large characteristic.

13 pages, accepted to Discrete Math., corrections suggested by the referees have been incorporated