1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

EDIT: This answer pertains to a misinterpretation of the question before it was later clarified, so does not answer the question as currently stated:

Two distinct 4-cycles share a 3-vertex path if and only if the union of those two 4-cycles is isomorphic to the complete bipartite graph $K_{2,3}$.

So, you are effectively asking for the maximum number $M_n$ of 4-cycles in a $K_{2,3}$-free graph on $n$ vertices.

Now, a graph is $K_{2,3}$-free if and only if every pair $x, y$ of vertices have at most two common neighbours -- and, if there are exactly two neighbours, $x$ and $y$ are diametrically opposite points on a 4-cycle. An upper bound on the number of 4-cycles in such a graph is therefore:

$$ M_n \leq \frac{1}{2} \binom{n}{2} $$

since there are $\binom{n}{2}$ pairs of distinct vertices (each of which can be the diagonal of at most one 4-cycle) and every 4-cycle has two diagonals.

A good lower bound can be extracted from https://arxiv.org/pdf/1306.5167.pdf by taking their Construction 3.15. In particular, let $p$ be an odd prime and take the graph $G_p$ whose vertex set is $(\mathbb{F}_p^2 \setminus \{(0, 0)\}) / \{ \pm 1 \}$ and contains an edge between $(a, b)$ and $(x, y)$ if and only if $ax + by \in \{ \pm 1 \}$.

$G_p$ has $\frac{1}{2}(p^2 - 1)$ vertices. For every pair of vertices $(a, b)$ and $(a', b')$, the common neighbours are the solutions to:

$$ ax + by, a'x + b'y \in \{ \pm 1 \} $$

Now, since the vertices are distinct there are four solutions, which we'll call $(c, d)$, $(-c, -d)$, $(c', d')$, and $(-c', -d')$. After taking the quotient, these four solutions correspond to two vertices. As $p \rightarrow 0$, the fraction of original pairs of vertices for which $\{ (a, b), (a', b'), (c, d), (c', d') \}$ are all distinct approaches 1. This implies that in these cases, the number of 4-cycles is asymptotically optimal: $\left(\frac{1}{2} - o(1)\right) \binom{n}{2}$.

For arbitrary $n$, we can let $p$ be the largest prime such that $\frac{1}{2}(p^2 - 1) \leq n$, and take the $n$-vertex graph to be the disjoint union of $G_p$ with $n - \frac{1}{2}(p^2 - 1)$ extra isolated vertices. Results on prime gaps (such as the theorem that there is a prime between every pair of sufficiently large cubes) show that the number of extra isolated vertices is $o(n)$.

Putting this all together, we get the following asymptotically tight bounds:

$$ \left(\frac{1}{2} - o(1)\right) \binom{n}{2} \leq M_n \leq \frac{1}{2} \binom{n}{2} $$

$\endgroup$
4
  • $\begingroup$ A union of two $C_4$ without a common $P_3$ can have a $K_{2,3}$. For example, consider the $K_{2,4}$ where one partition has vertices $\{x, y\}$ and the other partition has $\{1,2,3,4\}$. This graph is the union of two cycles $1,x,2,y,1$ and $3,x,4,y,3$. These cycles do not have a common $P_3$. $\endgroup$ Commented Jun 11, 2020 at 8:13
  • $\begingroup$ But your graph still has two 4-cycles -- such as $1,x,2,y,1$ and $3,x,2,y,1$ -- which share a common 3-vertex path ($x,2,y$). If you didn't mean that (and you're only interested in finding a large collection of 4-cycles on a common vertex set which pairwise share no common 3-vertex path), then your mention of 'an $n$-vertex simple undirected graph' is a red herring. $\endgroup$ Commented Jun 11, 2020 at 12:36
  • 1
    $\begingroup$ Yes. I was only asking for a large collection with no common $P_3$. I can see how my question is confusing. I will edit it. $\endgroup$ Commented Jun 11, 2020 at 13:10
  • $\begingroup$ For the corrected question, a similar argument used for your lower bound works to obtain an $\Omega(n^3)$ bound. $\endgroup$ Commented Jun 11, 2020 at 13:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .