2
$\begingroup$

Let $ex(n,H)$ denote the maximum number of edges of a graph on $n$ vertices not containing a copy of $H$. Let $ex(n,m,H)$ denote the maximum number of edges of a bipartite graph with parts' sizes $m$ and $n$ not containing a copy of $H$. I'm interested in upper bound on $ex(n, n, C_4)$. It is easy to show with probabilistic argument that $ex(n, n, C_4)\geq c\times n^{4/3}$. Also Erdös, Rényi, Sós (1954) showed that $ex(n,C_4)\sim\frac{1}{2}n^{3/2}$.

So, the question is if there exist a better upper bound for bipartite graph?

$\endgroup$

2 Answers 2

2
$\begingroup$

I find out that this problem is a special case of Zarankiewicz problem and it was solved by István Reiman in 1958 (thanks to Oliver Krüger for correction). The answer is $ex(n,n,C_4)\sim n^{3/2}$.

$\endgroup$
2
  • 3
    $\begingroup$ Not really solved by Bollobás. It was solved by István Reiman in 1958 (who showed that n = 2(q^2 + q + 1) where q is the order of a projective plane (in particular for prime powers q) then ex(n,n,C_4) = (q^2 + q + 1)(q + 1), and therefore ex(n,n,C_4) <= (1/2) (n + n*sqrt(4n-3))). The proof is however availible in Bollobás book "Extremal Graph Theory" from 1978 (which has a 2004 reprint). $\endgroup$ Oct 12, 2016 at 11:28
  • $\begingroup$ ... "for large enough n" it should say for the general upper bound of ex(n,n,C_4) in my previous comment. $\endgroup$ Oct 12, 2016 at 11:37
2
$\begingroup$

Just to point at the details: let the bipartition classes be X and Y. Now $\sum_{x\in X}\binom{\deg(x)}{2}$ counts the number of pairs in $Y$ with a common neighbour in $X$ (with multiplicity). But since no such pair has two common neighbours, the sum is at most $\binom{n}{2}$. By Jensen's inequality, the sum is minimised (for a given total $\sum_{x\in X}\deg(x)$ ) if and only if all vertices in $X$ have the same degree $e(G)/n$. Solving this equation gives the upper bound on $ex(n,n,C_4)$, with equality if and only if all degrees are the same and all pairs have exactly one common neighbour. Of course, point-line incidence graphs of projective planes satisfy both conditions: every point is on the same number of lines, and every pair of lines determines exactly one point. The general asymptotic then follows from the known results on the maximum gap between primes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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