Tuesday 15 July 2008

lo.logic - 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 $Gsqcup 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
$Gsqcup 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,gammageq 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 $Gsqcup 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 $Gsqcup G$, such as
with the infinite edgeless graph, or when $G$ is any
infinite sum of a fixed graph (and this is equivalent to
$Gcong Gsqcup 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 $Gsqcup 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 $Gsqcup 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
    $Poplus P$? Or to $oplus_delta P$?

  • Which groups $G$ are elementarily equivalent to $Goplus
    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.

No comments:

Post a Comment