In Stefan Geschke's recent question, one of the solutions observed that the graph consisting of a single infinite beaded chain, a $\mathbb{Z}$-chain where each integer is connected to its nearest neighbors, is elementarily equivalent to the disjoint sum of any number of such chains. That is, a single chain has all the same first order properties in the language of graph theory as two chains, or as any number of such chains.

(The reason was that all these graphs are cycle-free and have every element with degree $2$, but the theory asserting this is already complete. This can be seen by observing that every model of this theory having uncountable size $\kappa$ consists of $\kappa$ many $\mathbb{Z}$-chains, and all such models are isomorphic---in other words, the theory is $\kappa$-categorical---and so the theory is complete, since otherwise it would have non-isomorphic models of size $\kappa$.)

My question here is about the extent to which this phenomenon generalizes to other graphs.

Question. Which graphs $G$ are elementarily equivalent to $G\sqcup G$? And how about $\delta$ many copies of $G$ with itself $\bigsqcup_\delta G$?

Let's introduce some terminology and say that a graph $G$ is 2-self-similar if $G$ is elementarily equivalent to $G\sqcup G$, and more generally $G$ is $\delta$-self-similar if $G$ is elementarily equivalent to $\delta$ many copies of $G$.

Further questions: If $G$ is 2-self-similar, does this imply that it is $\delta$-self-similar for every $\delta$? For which $\delta,\gamma\geq 2$ does $\delta$-self-similarity imply $\gamma$-self-similarity? If $G$ is 2-self-similar, does this imply that each copy of $G$ is an elementary substructure of $G\sqcup G$? And similarly for $\bigsqcup_\delta G$?

On the one hand, the argument about $\mathbb{Z}$-chains easily generalizes to many other graphs, such as the connected graph tree $T$ in which every vertex has degree $3$. That is, the theory of cycle-free graphs with every vertex of degree $3$ is $\kappa$-categorical for uncountable cardinals $\kappa$ and hence complete, and so $T$ is elementarily equivalent to any number of disjoint copies of $T$. And we can clearly use trees of any finite uniform degree in this argument. Also, there are non-uniform graphs with self-similarity, such as the graph tree where vertices alternate degree 2, degree 3, etc., and any other definable pattern. And cycle-freeness is not required, since one could add loops of any length to every vertex in a $\mathbb{Z}$-chain, for example, and the original argument would still work fine.

In addition, trivial instances of self similarity arise when $G$ is outright isomorphic to $G\sqcup G$, such as with the infinite edgeless graph, or when $G$ is any infinite sum of a fixed graph (and this is equivalent to $G\cong G\sqcup G$). But the example of $\mathbb{Z}$-chains shows that this isomorphism version of self similarity is not a necessary property for 2-self-similarity, since one $\mathbb{Z}$-chain is obviously not isomorphic to two, even though they are elementarity equivalent.

Meanwhile, there are some easily observed obstacles to $\delta$-self-similarity:

• If $G$ has definable elements, then 2-self-similarity will fail, since every point has automorphic images in $G\sqcup G$.

• Similarly, if $G$ has nonempty finite definable subsets, then it will not be $n$-self-similar for large enough $n$, since again there will be too many automorphic images. (Perhaps this argument can be improved to show $G$ is not 2-self-similar; for example, this is easy to see when the copies of $G$ are elementary substructures of $G\sqcup G$.)

• If $G$ has finite diameter, then again self-similarity will fail, since multiple copies of $G$ will not be connected and hence not have that diameter. (Thus, for example, the countable random graph is not 2-self-similar.)

Finally, it seems that many similar questions can be asked about other mathematical structures.

• Which partial orders $P$ are elementarily equivalent to $P\oplus P$? Or to $\oplus_\delta P$?
• Which groups $G$ are elementarily equivalent to $G\oplus G$? Or to $\oplus_\delta G$?
• Same for rings or whatever structure for which direct sum makes sense.

I am wondering whether there might be a general model-theoretic characterization of self similarity.