¿Existe algún estudio sobre los límites del número de ciclos pares para grafos bipartitos planares?

Question

En 1979, Hakimi y Schmeichel [1] iniciaron un estudio de este tipo determinando el número máximo de triángulos y 4-ciclos posibles en un $n$ -(véase también [2] para una pequeña corrección).

• [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.

En 2019, Gyori et al. [3] estudiaron el número máximo de pentágonos en grafos planos.

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

Tengo un problema sobre si existe un resultado similar para grafos bipartitos planares. Por ejemplo, un límite superior sobre el número de 4 ciclos (o cualquier otro ciclos pares ). Todavía no lo he encontrado. Si no es así, no está claro cuál es la dificultad.

Una vez hice una pregunta parecida en Matemáticas. Stack y no obtuve ningún resultado.

• El límite superior del número de cuatro ciclos de grafos de cuadrangulación de 3 conexiones.

Answer 1

Cada $n$ -tiene como máximo $O(n^k)$ copias de $C_{2k}$ . Obsérvese que la suposición bipartita no es necesaria. En mi artículo Densidades de subgrafos en una superficie con Gwenaël Joret y David Wood, donde demostramos que el mismo límite es válido para grafos incrustables en cualquier superficie fija. De hecho, determinamos el número máximo de copias de $H$ en un $n$ -grafo de vértices incrustado en una superficie de género Euler $g$ para cada gráfico fijo $H$ (hasta una constante multiplicativa).

Existe un límite inferior coincidente y, en el caso de un ciclo par, la construcción es bipartita. Por lo tanto, la respuesta a su pregunta es $\Theta(n^k)$ para $C_{2k}$ . Para la construcción, toma $C_{2k}$ y ampliar todos los demás vértices en un conjunto estable de tamaño en torno a $n/k$ . Se trata de un grafo plano bipartito con $\Omega(n^k)$ copias de $C_{2k}$ .