Which graphs are elementarily equivalent to their own disjoint sums? 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.
 A: EDIT:  This is now a two-part answer to respond to two of Joel's sub-questions.  (I still don't know about his main question, which seems quite difficult to me.)
Part I: I claim that for any two cardinals $\gamma, \delta \geq 2$, a graph $G$ is $\gamma$-self-similar if and only if $G$ is $\delta$-self-similar.
The idea is to use Ehrenfeucht-Fraisse games to show that $m$-self-similarity for a finite $m \geq 2$ is equivalent to $\gamma$-self-similarity for every cardinal $\gamma$.
First, suppose $G$ is elementarily equivalent to $m$ disjoint copies of itself for some finite $m$.  Then for any finite $k$, $G$ is elementarily equivalent to the disjoint union of $m^k$ copies of itself.  (Why?  You can do an induction on k; if $G$ is equivalent to $G^{m^k}$, then you can show that $G^m$ is equivalent to $G^{m^{k+1}}$ by thinking of the latter as a sum of $m$ copies of $G^{m^k}$, and then get a winning strategy for the verifier for an EF game on $(G^m,G^{m^{k+1}})$ by thinking of the game as a sum of $m$ simultaneous games between each copy of $G$ in $G^m$ and each copy of $G^{m^k}$ in $G^{m^{k+1}}$, using the verifier's winning strategy for $(G, G^{m^k})$ on each subgame.)  It follows that for any infinite $\gamma$, $G$ is elementarily equivalent to a disjoint sum of $\gamma$ copies of itself: to show that the length-$n$ EF game against $G$ and $G^\gamma$ has a winning strategy for the verifier, we simply pick $k$ with $m^k \geq n$ and use the winning strategy for the verifier for $G$ and $G^{m^k}$.
Second, suppose $G$ is elementarily equivalent to $G^\gamma$ for some infinite $\gamma$.  Then for any finite $k$, $G^k$ is also elementarily equivalent to $G^\gamma$: this is because we can write $G^\gamma$ as a disjoint sum of $k$ copies of $G^\gamma$ (since $\gamma$ is infinite), and to get a winning strategy for the verifier for the $n$-step EF game, simply imagine that you are playing $k$ separate games between each copy of $G$ in $G^k$ and each of the $k$ copies of $G^\gamma$.
So if $k$ and $\ell$ are finite and $G^k$ is elementarily equivalent to $G^\omega$, then $G^\ell$ is also elementarily equivalent to $G^\omega$, so by transitivity, $G^k$ is equivalent to $G^\ell$.  Putting all of this together, my claim follows.

Part II: It is possible to give a nice characterization of self-similarity for abelian groups.
Szmielew showed that two abelian groups G and H are elementarily equivalent if and only if they have all the same "Szmielew invariants," where the Szmielew invariants of G are the following (which are defined to be either natural numbers 0, 1, ... or $\infty$):


*

*The exponent of G, the least positive n (if it exists) such that nG = 0, or else $\infty$;

*For each prime p and $n \geq 0$, $\dim {p^n G[p]}/{p^{n+1} G[p]}$, where $G[p]$ is the subgroup of all $p$-torsion elements of $G$ and the dimension is as an $\mathbb{F}_p$ vector space;

*For each prime p, $\lim_{n \rightarrow \infty} \dim {p^n G}/{p^{n+1} G}$;

*For each prime p, $\lim_{n \rightarrow \infty} \dim p^n G[p]$.
Since $G \oplus G$ has the same exponent as $G$ and invariants 2 through 4 commute with direct sums (the invariant of $G \oplus H$ is the sum of the invariants of $G$ and of $H$), it follows that an abelian group $G$ is self-similar if each of its invariants of type 2 through 4 is either $0$ or $\infty$.
(See Hodges' Model Theory or Prest's Model Theory and Modules for nice explanations of Szmielew invariants.)
I don't know how far this generalizes -- i.e. are there many other natural categories with coproducts such that elementary equivalence is determined by such a list of cardinal invariants which commute with taking coproducts?  For graphs, this seems like too much to hope for, but at least maybe for theories of modules over nice rings (like Dedekind domains) you could do something similar.
A: It's a fairly old question, but I think I have the answer for graphs.
Let's define some notations, based on John Goodrick's answer.
Everything below can be formalized by Ehrenfeucht–Fraïssé games, but we'll use the notion of logical type to shorten arguments.
A type denotes any $n$-type for $n<\omega$. The realization of a type $t$ in a graph $G$ is a subset of vertices which is of type $t$.
Definition 1: A theory is abundant if every type is either not realized or realized infinitely often.
Lemma: The theory of a self-similar structure is abundant.
This follows directly from John Goodrick's answer, that self-similar is the same as $\delta$-similar for any $\delta$. Take some realization of a type $t$ in $G$. 
Since $G$ is self-similar, it is equivalent to $\oplus_\omega G$, thus we can find $\omega$ realizations from the copies of $G$. 
Let $d(u,v)$ be the graph distance (or hop distance), which is considered infinite if the two vertices belong to different connected components.
Let the distance $d(U,V)$ over sets of vertices be the minimum over every possible pair of vertices.
Definition 2: A theory is scattered if for every pair of types $t_1$, $t_2$ and every $k$, there exists a realization of $t_1$ and a realization of $t_2$ at distance at least $k$.
(In particular, they can be at infinite distance.) 
Note that if a theory is abundant and scattered, then it is possible to find at least $m$ pairs of realizations at distance at least $k$ for any $m$, since the pair form an instance of a $f(n,k)\leqslant$-type.
Now the result: A structure is self-similar if and only if it is abundant and scattered.
Since we already have the implication 'self-similar $\rightarrow$ abundant', we can focus on the 'scattered' part. 
In the forward direction, take two realizations of any pair of realized types $t_1$ and $t_2$. Since $G$ is elementarily equivalent to $G \oplus G$, we have found a realization of $t_1$ and $t_2$ at distance more than $k$. 
In the other direction, suppose the theory is not scattered, i.e. there is a pair of types $t_1$ and $t_2$ for which there are no realizations at distance more than $k_\star$ for some natural number. Then take in $G \oplus G$ one realization of $t_1$ and one of $t_2$ in each copy of $G$. They are at distance more than $k_\star$, thus $G \oplus G$ and $G$ cannot be elementary equivalent, a contradiction.
