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.

  • $\begingroup$ 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$. $\endgroup$ – joro Dec 29 '15 at 16:08
  • $\begingroup$ 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}$...) $\endgroup$ – gaussian-matter Dec 29 '15 at 21:48

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.