Skip to main content
added 177 characters in body
Source Link
Adam P. Goucher
  • 12.4k
  • 2
  • 54
  • 105

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} $$

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} $$


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} $$

Source Link
Adam P. Goucher
  • 12.4k
  • 2
  • 54
  • 105

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} $$