3
$\begingroup$

Let $G=(V,E)$ be a simple graph. Recall that an induced subgraph of $G$ is a graph whose vertex set $U$ is a subset of $V$, and whose edge set is $E\cap(U\times U)$. Define an induced subtree to be an induced subgraph which is also a tree.

Consider the following random algorithm to construct an induced subtree in $G$. Pick a uniformly random vertex $v\in V$, and let $U=\{v\}$. Let $O$ be the set of vertices not in $U$ which have a single edge to $U$, that is $$ O=\{w\in V\setminus U\mid|E\cap(\{w\}\times U)|=1\}. $$ Pick a uniformly random element of $O$ and append it to $U$. Repeat until $O$ is empty. Let $T$ be the induced subgraph on $U$, which is a tree by construction.

Equivalently, choose a random walk up the Hasse diagram of the poset of induced subtrees (ordered by inclusion) from the empty set up to a maximal induced subtrees.

Now choose uniformly randomly a maximally distant pair of vertices in $T$; that is, choose $(v,w)$ uniformly randomly from the set $$ \{(v,w)\in U\times U\mid d_T(v,w)\geq d_T(v',w')\text{ for }v',w'\in U\} $$ where $d_T$ denotes path length in $T$. Finally let $d=d_G(v,w)$. For fixed $G$ we can consider $d$ to be a random variable.

Now take $G$ to be an $n\times n$ grid; that is, $V=\{(x,y)\in\mathbb Z^2\mid 1\leq x,y\leq n\}$ and $E=\{(p,q)\in V\times V\mid \|p-q\|=1\}$. Intuitively we might expect $d$ to be similar to the diameter of $G$, namely $2n$. However I observed it is often much lower. In fact the distribution looks bimodal, with a clump around $n$ and a clump around a value which is $o(n)$. See the histogram of $d/n$ below, constructed by running the algorithm $400$ times for several values of $n$.

   n     d/n                                                                        
     0.0-0.2 0.2-0.4 0.4-0.6 0.6-0.8 0.8-1.0 1.0-1.2 1.2-1.4 1.4-1.6 1.6-1.8 1.8-2.0
  10     0.0    78.0   118.0    34.0    73.0    62.0    21.0     5.0     9.0     0.0
  20    43.0    71.0    87.0    48.0    81.0    50.0     7.0     6.0     5.0     2.0
  40    64.0    55.0    50.0    56.0   120.0    48.0     1.0     0.0     2.0     4.0
  80    69.0    71.0    44.0    32.0   128.0    47.0     5.0     0.0     1.0     3.0
 160    82.0    63.0    36.0    22.0   157.0    39.0     0.0     0.0     0.0     1.0
 300    95.0    69.0    21.0     8.0   156.0    47.0     0.0     0.0     0.0     4.0
 400   126.0    72.0    24.0     4.0   132.0    42.0     0.0     0.0     0.0     0.0
 500   107.0    66.0    19.0     5.0   146.0    57.0     0.0     0.0     0.0     0.0
 600   127.0    77.0    12.0     1.0   133.0    50.0     0.0     0.0     0.0     0.0
 700   120.0    64.0    16.0     3.0   142.0    55.0     0.0     0.0     0.0     0.0
 800   129.0    58.0    15.0     3.0   143.0    52.0     0.0     0.0     0.0     0.0
 900   146.0    65.0    12.0     1.0   135.0    41.0     0.0     0.0     0.0     0.0
1000   162.0    69.0    27.0     1.0   108.0    33.0     0.0     0.0     0.0     0.0

Can any of these observations be formalized? For example, can it be shown that $\textrm{median}(d)/n\to0$ as $n\to\infty$?

$\endgroup$
6
  • 1
    $\begingroup$ Experimentally, the same thing seems to happen with random spanning trees of the grid graph, and those might be easier to think about (though I've collected much less data for that case than you have for this one). $\endgroup$
    – Misha Lavrov
    Mar 16, 2020 at 2:22
  • $\begingroup$ What Stewbasic is considering here is exactly the same as a random spanning tree of the grid graph. It was just phrased in terms of induced subgraphs. Basically, the question asked here is: given a random spanning tree $T$ of $G$, how does the diameter of $T$ realised by $v,w$ compare to the distance of $v,w$ in $G$? It may be interesting to see how does $d_T(v,w)$ compares to $d_G(v,w)$. $\endgroup$
    – VECH
    Mar 18, 2020 at 11:58
  • $\begingroup$ @victor T in my question is not a spanning tree; it doesn't contain all vertices of T. I would still be interested if something can be proven about the spanning tree case. $\endgroup$
    – stewbasic
    Mar 19, 2020 at 20:01
  • $\begingroup$ Oh, I see. In that case there's something I am not understanding. I can see how the algorithm you describe does not necessarily give you a spanning tree. However, how come a maximal induced subtree in the poset of induced subtrees is not a spaning tree? Given an induced subtree $T$ we can always extend it to a spaning tree $S$, such that $T < S$, right? $\endgroup$
    – VECH
    Mar 19, 2020 at 22:13
  • 1
    $\begingroup$ @VictorEduardo We can extend it to a spanning tree $S$, but $S$ will not be an induced subgraph. A spanning tree by definition contains all vertices of the initial graph, so it cannot be an induced subgraph (unless the initial graph is already a tree). $\endgroup$
    – stewbasic
    Mar 20, 2020 at 3:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.