7
$\begingroup$

Given an infinite planar graph $G$, let's denote by $\{H_1,H_2,\dots,H_m\}$ all the labeled graphs on $n$ vertices that appear as subgraphs of $G$. Also let $$d_n=\frac{\sum_{i=1}^m \#E(H_i)}{nm}$$ denote the "edge density" among the $H$'s.

Question: Does the limit $\lim_{n\to \infty}d_n$ always exist? If yes, what does it say about the graph $G$?

The analogous question when we consider arbitrary infinite graphs, and define $d_n$ as $\frac{\sum_{i=1}^m \#E(H_i)}{\binom{n}{2}m}$, was asked by Peter Cameron here (BCC12.5), in an attempt to define a notion of "edge density" for infinite graphs. As far as I know this version is open, but I was hoping the planar case might be simpler.

Improve this question
$\endgroup$
4
  • $\begingroup$ If it exists for the disjoint union of some $F_n$ where $F_n$ have maximum number of edges $3(n-2)$ would it always exist? IIRC every finite planar graph is subgraph of maximal planar graph. Adding a graph with fewer edges decreases the ratio. $\endgroup$
    – joro
    Aug 27, 2015 at 5:04
  • $\begingroup$ I take it that the vertices of $G$ have an ordering and a labelled graph $H$ with vertices $1,\ldots,n$ is counted if there is a homomorphism $\phi$ from $H$ to $G$ such that $\phi(1)\lt \cdots \lt \phi(n)$. Is that right? If not, please explain. $\endgroup$
    – Brendan McKay
    Aug 27, 2015 at 13:20
  • 1
    $\begingroup$ My reading was that the vertices of $G$ were not labelled, but that the vertices of the subgraphs were labelled (so that if $G$ is an infinite path, for example, then there are $n!/2$ subgraphs of size $n$). $\endgroup$
    – Anthony Quas
    Aug 27, 2015 at 15:15
  • $\begingroup$ I apologize for the unclear wording, but Anthony's interpretation is the one I meant. $\endgroup$
    – Gjergji Zaimi
    Aug 27, 2015 at 21:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.