Leírás
Március 26-án (14:15, Nagyterem)
Yichen Wang: The number of induced paths in outerplanar graphs
Abstract:
Let $P_k$ denote the path with $k$ vertices, and
$\mathrm{ex}_{\mathcal{OP}}(n,H^{\ind},\emptyset)$ be the maximum number
of induced copies of $H$ in an $n$-vertex outerplanar graph.
In this paper, we determine the exact value of
$\mathrm{ex}_{\mathcal{OP}}(n,P_3^{\ind},\emptyset)$ for all $n$, and
give an asymptotic value of
$\mathrm{ex}_{\mathcal{OP}}(n,P_4^{\ind},\emptyset)$.
For general $k$, we give a construction to the lower bound of
$\mathrm{ex}_{\mathcal{OP}}(n,P_k^{\ind},\emptyset)$, which shows
$\mathrm{ex}_{\mathcal{OP}}(n,P_k^{\ind},\emptyset)\geq
h(k)\binom{n}{2}$, where $h(k)$ satisfies $\lim_{k\to
\infty}h(k)^{\frac{1}{k}}\geq 1.499.$
And for the upper bound, we prove
$\mathrm{ex}_{\mathcal{OP}}(n,P_k^{\ind},\emptyset)\leq
\frac{1}{\sqrt{5}} \left( \left(\frac{\sqrt{5}+1}{2} \right)^{k+1}-
\left(\frac{1-\sqrt{5}}{2} \right)^{k+1} \right)\binom{n}{2}$.
This is a joint work with Ervin Győri, and Xiamiao Zhao.
Mindenkit szeretettel várunk
Zoom:
https://zoom.us/j/2961946869?omn=98245035028