2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Dec 29, 2015 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$
    – Johnny Cage
    Commented Dec 29, 2015 at 21:48

1 Answer 1

Reset to default
3
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .