Skip to main content
deleted 64 characters in body
Source Link

Let's look at the case $r = 2$ and choose to interpret the question as asking how many $K_{2,2}$ or $C_4$'s one has in a graph with $n$ vertices and ex$(n, C_4)$ + 1 edges, where ex$(n, C_4)$ is the largest number of edges in an $n$-vertex graph with no copy of $C_4$. This is known to be approximately $\frac{1}{2} n^{3/2}$.

The exact value of ex$(n, C_4)$ is only known for certain values of $n$, but for those cases the lower bound constructions come from projective planes. The spirit of the extremal examples is that each vertex has neighbourhood of order $\Theta(\sqrt{n})$ and these neighbourhoods cover the pairs of vertices in the graph, with (almost) every pair appearing in exactly one neighbourhood (if a pair were in two neighbourhoods, we would have a $C_4$).

What happens if we add an extra edge to such a construction? Suppose the new edge is $uv$. Then, for every vertex $w \in N(u)$, the edge $vw$, which was already covered by a neighbourhood, is covered by $N(u)$ and so forms a $C_4$. Similarly, for every $w \in N(v)$, the edge $uw$ produces a $C_4$. Overall, we produce $O(\sqrt{n})$ new copies of $C_4$, different to the expectation of $\Omega(n)$ expressed in the question. I suspect that $\Omega(\sqrt{n})$ is the correct answer in this case. For higher $r$, it's harder to guess at what the truth might be.

Let's look at the case $r = 2$ and choose to interpret the question as asking how many $K_{2,2}$ or $C_4$'s one has in a graph with $n$ vertices and ex$(n, C_4)$ + 1 edges, where ex$(n, C_4)$ is the largest number of edges in an $n$-vertex graph with no copy of $C_4$. This is known to be approximately $\frac{1}{2} n^{3/2}$.

The exact value of ex$(n, C_4)$ is only known for certain values of $n$, but for those cases the lower bound constructions come from projective planes. The spirit of the extremal examples is that each vertex has neighbourhood of order $\Theta(\sqrt{n})$ and these neighbourhoods cover the pairs of vertices in the graph, with (almost) every pair appearing in exactly one neighbourhood (if a pair were in two neighbourhoods, we would have a $C_4$).

What happens if we add an extra edge to such a construction? Suppose the new edge is $uv$. Then, for every vertex $w \in N(u)$, the edge $vw$, which was already covered by a neighbourhood, is covered by $N(u)$ and so forms a $C_4$. Similarly, for every $w \in N(v)$, the edge $uw$ produces a $C_4$. Overall, we produce $O(\sqrt{n})$ new copies of $C_4$, different to the expectation of $\Omega(n)$ expressed in the question. I suspect that $\Omega(\sqrt{n})$ is the correct answer in this case. For higher $r$, it's harder to guess at what the truth might be.

Let's look at the case $r = 2$ and choose to interpret the question as asking how many $K_{2,2}$ or $C_4$'s one has in a graph with $n$ vertices and ex$(n, C_4)$ + 1 edges, where ex$(n, C_4)$ is the largest number of edges in an $n$-vertex graph with no copy of $C_4$. This is known to be approximately $\frac{1}{2} n^{3/2}$.

The exact value of ex$(n, C_4)$ is only known for certain values of $n$, but for those cases the lower bound constructions come from projective planes. The spirit of the extremal examples is that each vertex has neighbourhood of order $\Theta(\sqrt{n})$ and these neighbourhoods cover the pairs of vertices in the graph, with (almost) every pair appearing in exactly one neighbourhood (if a pair were in two neighbourhoods, we would have a $C_4$).

What happens if we add an extra edge to such a construction? Suppose the new edge is $uv$. Then, for every vertex $w \in N(u)$, the edge $vw$, which was already covered by a neighbourhood, is covered by $N(u)$ and so forms a $C_4$. Similarly, for every $w \in N(v)$, the edge $uw$ produces a $C_4$. Overall, we produce $O(\sqrt{n})$ new copies of $C_4$, different to the expectation of $\Omega(n)$ expressed in the question. I suspect that $\Omega(\sqrt{n})$ is the correct answer in this case.

Source Link

Let's look at the case $r = 2$ and choose to interpret the question as asking how many $K_{2,2}$ or $C_4$'s one has in a graph with $n$ vertices and ex$(n, C_4)$ + 1 edges, where ex$(n, C_4)$ is the largest number of edges in an $n$-vertex graph with no copy of $C_4$. This is known to be approximately $\frac{1}{2} n^{3/2}$.

The exact value of ex$(n, C_4)$ is only known for certain values of $n$, but for those cases the lower bound constructions come from projective planes. The spirit of the extremal examples is that each vertex has neighbourhood of order $\Theta(\sqrt{n})$ and these neighbourhoods cover the pairs of vertices in the graph, with (almost) every pair appearing in exactly one neighbourhood (if a pair were in two neighbourhoods, we would have a $C_4$).

What happens if we add an extra edge to such a construction? Suppose the new edge is $uv$. Then, for every vertex $w \in N(u)$, the edge $vw$, which was already covered by a neighbourhood, is covered by $N(u)$ and so forms a $C_4$. Similarly, for every $w \in N(v)$, the edge $uw$ produces a $C_4$. Overall, we produce $O(\sqrt{n})$ new copies of $C_4$, different to the expectation of $\Omega(n)$ expressed in the question. I suspect that $\Omega(\sqrt{n})$ is the correct answer in this case. For higher $r$, it's harder to guess at what the truth might be.