Skip to main content
MathOverflow

Return to Question

The graph may contain two $C_4$s that intersect at a $P_3$. Only the set of cycles chosen need to not have a common $P_3$.
Source Link
edit approved Jun 11, 2020 at 13:54
Balagopal Komarath
edit approved Jun 11, 2020 at 13:54
Balagopal Komarath
  • 103
  • 2

What is the maximum numbersize of the largest set (asymptotic) of four vertex cycles in an $n$-vertex simple, undirected graph such that no two cycles from this set has a common three vertex path?

If we choose four cycles such that no two of them intersect at more than two vertices, then we get $\Theta(n^2)$ four cycles. On the other hand, it is easy to see that the upper bound is $O(n^3)$ because there are only $O(n^3)$ distinct three vertex paths in an $n$-vertex graph.

What is the maximum number (asymptotic) of four vertex cycles in an $n$-vertex simple, undirected graph such that no two cycles has a common three vertex path?

If we choose four cycles such that no two of them intersect at more than two vertices, then we get $\Theta(n^2)$ four cycles. On the other hand, it is easy to see that the upper bound is $O(n^3)$ because there are only $O(n^3)$ distinct three vertex paths in an $n$-vertex graph.

What is the size of the largest set (asymptotic) of four vertex cycles in an $n$-vertex simple, undirected graph such that no two cycles from this set has a common three vertex path?

If we choose four cycles such that no two of them intersect at more than two vertices, then we get $\Theta(n^2)$ four cycles. On the other hand, it is easy to see that the upper bound is $O(n^3)$ because there are only $O(n^3)$ distinct three vertex paths in an $n$-vertex graph.

Source Link
Balagopal Komarath
Balagopal Komarath
  • 11
  • 1

Maximum number of four cycles with no intersecting three vertex paths

What is the maximum number (asymptotic) of four vertex cycles in an $n$-vertex simple, undirected graph such that no two cycles has a common three vertex path?

If we choose four cycles such that no two of them intersect at more than two vertices, then we get $\Theta(n^2)$ four cycles. On the other hand, it is easy to see that the upper bound is $O(n^3)$ because there are only $O(n^3)$ distinct three vertex paths in an $n$-vertex graph.