4
$\begingroup$

In 1979, Hakimi and Schmeichel [1] initiated such a study by determining the maximum number of triangles and 4-cycles possible in an $n$-vertex planar graph (see also [2] for a small correction).

  • [1] S. Hakimi, E. Schmeichel. On the Number of Cycles of Length k in a Maximal Planar Graph. J. Graph Theory 3 (1979): 69–86.

  • [2] A. Alameddine. On the Number of Cycles of Length 4 in a Maximal Planar Graph. J. GraphTheory, 4(1980): 417–422.

In 2019, Győri et al. [3] studied the maximum number of pentagons on planar graphs.

  • [3] Győri E, Paulos A, Salia N, et al. The maximum number of pentagons in a planar graph[J]. arXiv preprint arXiv:1909.13532, 2019.

I have a problem about whether there is a similar result for planar bipartite graphs. For example, an upper bound on the number of 4 cycles (or any other even cycles). I haven't found it yet. If not, it is not clear what the difficulty is.

I once asked a similar question at Math. Stack and did not seem to see any results.

$\endgroup$

1 Answer 1

2
$\begingroup$

Every $n$-vertex planar graph has at most $O(n^k)$ copies of $C_{2k}$. Note that the bipartite assumption is not needed. A more general result is proven in my paper Subgraph densities in a surface with Gwenaël Joret and David Wood, where we prove that the same bound holds for graphs embeddable in any fixed surface. In fact, we determine the maximum number of copies of $H$ in an $n$-vertex graph embeddable in a surface of Euler genus $g$, for every fixed graph $H$ (up to a multiplicative constant).

There is a matching lowerbound, and in the case of an even cycle, the construction is bipartite. Thus, the answer to your question is $\Theta(n^k)$ for $C_{2k}$. For the construction, take $C_{2k}$ and blow-up every other vertex into a stable set of size around $n/k$. This is a bipartite planar graph with $\Omega(n^k)$ copies of $C_{2k}$.

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