How to define the infinite (countable) graph which is constructed as follows?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ The picture depicts a finite graph. $\endgroup$– WojowuMar 27, 2020 at 11:33
-
$\begingroup$ Where is the infinity!? $\endgroup$– ShahroozMar 27, 2020 at 11:39
-
4$\begingroup$ If I understand your picture correctly, let $V$ be the set of all dyadic rationals in $[0,1]$, and let $(p,q)$ be an edge if and only if $p = \frac{k}{2^n}$, where $k$ is an odd number (or $0$), and $q = p + \frac{1}{2^m}$ for some $m \geq n$. Is this what you have in mind? $\endgroup$– Will BrianMar 27, 2020 at 12:16
-
$\begingroup$ @WillBrian Yes, that's it. Thanks! $\endgroup$– Markiian KhylynskyiMar 27, 2020 at 18:29
-
$\begingroup$ This easy question could be community. I had 1: a nicer construction, and 2: an axiomatization. $\endgroup$– Wlod AAMar 27, 2020 at 19:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
To do this formally, first formulate a definition by induction, and then take the union.
The basis step is a graph $G_0$ with two vertices and one edge.
For the inductive step, assuming $G_i$ is defined, embed $G_i$ into a graph $G_{i+1}$ as follows: for any edge $a$---$b$ of $G_i$ that is not an edge of $G_{i-1}$, attach a new vertex $v_{a,b}$ and edges $a$---$v_{a,b}$, $v_{a,b}$---$b$.
Now define the final graph to be the union of the nested sequence of graphs $G_0 \subset G_1 \subset G_2 \subset \cdots$.
As said in the comments, this construction can also be encoded with a tiny bit of number theory.
answered Mar 27, 2020 at 13:04
-
4$\begingroup$ In the construction of $G_{i+1}$, you probably want to add a new $v_{a,b}$ only for those edges $a-b$ of $G_i$ that were not already in $G_{i-1}$. Otherwise, a single edge $a-b$ will result in "new" vertices and edges at all later stages. $\endgroup$ Mar 27, 2020 at 17:35
-
$\begingroup$ This is a right remark. Thanks! $\endgroup$ Mar 27, 2020 at 18:33
-
$\begingroup$ Thanks for the correction @AndreasBlass $\endgroup$ Mar 27, 2020 at 19:14