# Extremal combinatorics on bipartite graphs

One open question in extremal graph Theory is the so-called Zarankiewicz problem (see for instance the wikipedia page), which ask for the maximum number of edges in a bipartite graph with a fixed number of vertices without $K_{l,r}$ as a subgraph. A main example of this is $l=r=2$ (namely, cycles of length 4), due to its connection, for instance, with Sidon sets.

My question is the following: what is it known for a similar problem, but when avoiding an 'small' bipartite subgraph, not necessarily a complete $K_{l,r}$?

More precisely, I have in mind the following problem: consider $2n$ vertices, with partition of $n$ and $n$ vertices. Which is the maximum number of edges we can take in the corresponding bipartite graph without creating a $P_4$ (path with 4 edges)? Roughly speaking, the $C_4$ case is a degenerated situation of this.

Knowing references about other small configurations NOT coming from a complete $K_{l,r}$ would be also great appreciated.

• By $P_4$ do you really mean path with 4 edges or with 4 vertices? If you don't mean induced subgraph, then $K_{n,n}$ is solution for all $P_k$, no matter which way you define $P_4$. – joro Dec 29 '15 at 16:08
• I do not get this. This same reason would give that for $C_4$ the same is trivial, and it is not at all (the upper and lower bound are of order $n^{3/2}$...) – gaussian-matter Dec 29 '15 at 21:48

## 1 Answer

Graphs without $P_4$ may be completely classified. It is especially simple if they are bipartite. Each connected component either is a tree or has 4 vertices. Thus the maximal number of edges is $3n$ for even $n$ and $3n-4$ for odd $n$.

• Thank you! definitely I didn't think too much on the problem. Is there something known for more complex subgraphs? – gaussian-matter Dec 29 '15 at 21:02
• A lot is known, of course. See Lovasz' book on graph limits, for example, and references therein. – Fedor Petrov Dec 31 '15 at 16:05