# Self-defining structures

The relations $R$ in abstract graphs (with genuinely propertyless vertices) cannot be defined because there is nothing the relations can base on: they have to be presupposed.

But consider derived relations $\Phi(x,y)$ between vertices of a graph which can be defined in terms of the base relation $R$. I don't want to fix a language, but as an example I have in mind relations of the form $\phi(d(x),d(y))$, with $d(x)$ the degree of $x$ (with respect to $R$) and $\phi(n,m)$ a relation between natural numbers.

Definition: $\Phi$ is a self-fulfilling property (SFP) w.r.t. $G$ iff $\Phi(x,y) \equiv Rxy$ for all $x,y \in G$.

The other way round: $G$ is a self-defining structure w.r.t. $\Phi$ iff $\Phi(x,y) \equiv Rxy$ for all $x,y \in G$.

The only SFPs I found so far are $d(x) = d(y)$, which is self-fulfilling exactly w.r.t. complete graphs, and $d(x) \neq d(y)$, which is self-fulfilling exactly w.r.t. empty edgeless graphs. Can anyone come up with more intriguing examples?

What else can be said about SFPs?

• Can we decide whether there is a graph $G$ for which a given $\Phi$ is an SFP? Can we construct such a graph?

• Can we decide whether there is an SFP $\Phi$ for a given graph $G$?

• How can graphs with an SFP be characterized?

-
$d(x)=d(y)$ seems to be self-fulfilling also in the disjoint union of complete graphs of different sizes. – Joel David Hamkins Mar 4 '11 at 0:13
And $d(x) \neq d(y)$ seems to be self-fulfilling for the complement, complete multi-partite graphs with all parts of distinct sizes. By the way, there is only one empty graph. – Aaron Meyerowitz Mar 4 '11 at 2:52
@Aaron: I followed the definition here: en.wikipedia.org/wiki/Null_graph. And unfortunately - opposed to Joel's example - I cannot see how your example should work: two nodes connected iff they have different degree? – Hans Stricker Mar 4 '11 at 7:09
@Joel. I like the question, maybe I am missing some of the nuances. The definition you link to says either no vertices or merely no edges. Now I know which you meant. Wouldn't a path with two edges o_o_o satisfy $\Phi(x,y) \equiv Rxy$ where $\Phi$ is $d(x) \ne d(y)$? I assume $R$ is the adjacent to relation. (correct?) so: yes I did mean two nodes connected iff they have different degree. – Aaron Meyerowitz Mar 4 '11 at 7:53
@Hans : SFP such a nice and close (in sound and acronimy) variation on the classical concept of self-fullfilling prophecy. – Jérôme JEAN-CHARLES Mar 7 '11 at 2:04

I've found a necessary and sufficient characterization for when a relation $\Phi$ is nontrivially self-fulfilling, in the theorem below.

(As Aaron pointed out, every $\Phi$ is realized trivially in the graph with no vertices and also in the graph with one vertex, so by nontrivially self-fullfilling, let us insist that the graph have at least two vertices. Let us speak of undirected graphs with no loops, so that we adopt Aaron's correction that a binary relation $\Phi$ on $\mathbb{N}$ is self-fulfilling in graph $\langle V,R\rangle$ just in case $x\mathrel{R} y\iff \Phi(d(x),d(y))$ and $x\neq y$.)

Theorem. A symmetric binary relation $\Phi$ on $\mathbb{N}$ is nontrivially self-fulfilling in some graph if and only if $\neg\Phi(0,0)$ or $\Phi$ is not a subrelation of $\{0\}\times\mathbb{N}\cup\mathbb{N}\times\{0\}$; that is, if and only if $\neg\Phi(0,0)$ or it has $\Phi(n,k)$ for some $n,k\neq 0$.

Proof. If $\Phi(n,n)$ holds for some $n\neq 0$, then $\Phi$ is self-fulfilling in the complete graph on $n+1$ vertices. All vertices have degree $n$, and so only $d(x)=n$ arises in this graph, and so only $\Phi(n,n)$ is relevant when checking the self-fulfilling property.

Otherwise, if $\Phi(n,k)$ holds for some $n\neq 0\neq k$, but $\Phi(n,n)$ and $\Phi(k,k)$ both fail, then $\Phi$ is self-fulfilling in the bipartite graph $B(n,k)$, having $n$ nodes on the left connected to each of $k$ nodes on the right. In this graph, every vertex has degree either $k$ or $n$, and all such vertices are connected by edges, fulfilling $\Phi$.

If $\neg\Phi(0,0)$, then $\Phi$ is self-fulling in the graph on any number of vertices, but with no edges. Again, every vertex in this graph has $d(x)=0$, and so the only relevant part of $\Phi$ is $\Phi(0,0)$, which fails, and none of them are connected, as required.

Otherwise, $\Phi$ only relates numbers to $0$ and $\Phi(0,0)$ holds. No such $\Phi$ can be self-fullfilling in a graph with at least two nodes $x\neq y$, since if there are no edges in the graph, then $d(x)=d(y)=0$, and so they would have to be connected because of $\Phi(0,0)$, contradiction. And if there is an edge in the graph between some $x$ and $y$, then $d(x)$ and $d(y)$ have some value for which $\Phi(d(x),d(y))$, but by assumption one of those values must be $0$, contradicting the fact that there is an edge. QED

Note that the graphs arising in the proof have vertices only of very few degrees, which makes the self-fulfilling property easier.

Here is the example I gave earlier, which does have vertices of every non-zero degree.

The relation $|d(y)-d(x)|=1$ seems to be self-fulfilling in the following graph, where each node is labeled with its degree. One can construct the graph in levels, where at each level, the degree increases by $1$, and the number of nodes on the next level is determined by the self-fulfilling requirement. Each node on each level is connected to all nodes on any prior or next level.


.......            etc.

11 11 11 11 11   (each 11 is connected to five 10s and six 12s)

10 10 10 10 10   (each 10 is connected to five 9s and five 11s)

9  9  9  9  9   (each 9 is connected to four 8s and five 10s)

8  8  8  8   (each 8 is connected to three 7s and five 9s)

7  7  7     (each 7 is connected to three 6s and four 8s)

6  6  6     (each 6 is connected to three 5s and three 7s)

5 5 5      (each 5 is connected to two 4s and three 6s)
|//\\|
4   4
\ /
3
|
2
|
1


The sizes of the levels grows in the pattern: three of the same size, then one level with one more, then three of the same size one step larger, etc.

It seems that this idea can be generalized to make many more examples where the degrees increase in levels.

-
That's nice! But maybe it's not an accident, that this is an infinite graph? – Hans Stricker Mar 4 '11 at 7:16
@Joel: sorry, in the middle of your proof something seems to be mixed up: you seem to show that a certain bipartite graph [...] has no edges. – Hans Stricker Mar 4 '11 at 9:37
Sorry about that; I have fixed it now. – Joel David Hamkins Mar 4 '11 at 9:48
Just in case it might be interesting: oeis.org/… – Hans Stricker Mar 4 '11 at 15:59

I suppose we are implicitely appending $x \neq y \land \dots$ to all relations lest we get loops. Also, every binary relation is (vacuously) self fulfilling for the empty and 1 point graphs. Hence we should specify at least two vertices.

Graphs with no edges are characterized by any empty relation such as $d(x) \neq d(x)$ or $d(x)d(y) \neq d(x)d(y)$ or merely $\emptyset$. For complete graphs $d(x)=d(x)$ or $d(x)d(y)=d(x)d(y)$ could work.

The relation $\Phi$ has to be symmetric if we want an undirected graph. So, for undirected graphs with at least two points, $d(x)=d(y)^2$ would specify the one edge path.

If the relation was "exactly one of $d(x),d(y)$ is less than 2" we would get stars . If the relation was $\lbrace d(x),d(y) \rbrace=\lbrace 3,7 \rbrace \textbf{ OR } d(x)d(y)=0$ we would get the 10 vertex 21 edge complete multipartite graph $K_{3,7}$. The last condition is intended to forbid isolated vertices.

-
As I pointed out in my question: it's $d(x) \neq d(y)$ that characterizes edgeless graphs, not $d(x) \neq d(x)$. – Hans Stricker Mar 4 '11 at 7:13
I just wasn't sure if $d(x) \ne d(y)$ really only caught edgeless graphs. And thought that $d(x) \ne d(x)$ did. – Aaron Meyerowitz Mar 4 '11 at 7:59
I like $d(x) \neq d(y)$ better, because it's not a contradiction. But you are right, $d(x)d(y) \neq d(x)d(y)$ would also do the job. – Hans Stricker Mar 4 '11 at 8:36

Maybe it's easier than I initially supposed, but I found further families of self-defining graphs:

• Star graphs are self-defining w.r.t. $d(x)\neq d(y)$ (as Aaron clearly pointed out)

• The cycle graph with $k$ nodes is self-defining w.r.t. there is a path of length $k-1$ between $x$ and $y$.

Note: This is a first order property. Note further, that it is self-fulfilling in complete graphs with more than $k-1$ nodes, too.

• The wheel graph with $k$ nodes is self-defining w.r.t. $d(x)\neq d(y)$ OR there is a path of length $k-1$ between $x$ and $y$.

• Trees are self-defining w.r.t. there is no path of length > 1 between $x$ and $y$.

Note: This is a second order property. Note further, that this is just the defining property of trees: there are no detours(=cycles).

-
I'm getting lost. If you allow these kind of properties, then isn't any graph self-defining w.r.t. there is a path of length $1$ between $x$ and $y$? – Emil Jeřábek Mar 4 '11 at 14:18
Sure, but this is trivial: having a path of length 1 between x and y means Rxy. But relations that are logically equivalent to Rxy - e.g. Rxy itself - are not so interesting. Should I make this clearer in my question? – Hans Stricker Mar 4 '11 at 14:23
@Hans . Maybe you should clarify what you are trying for and restate it as a new question. Your wheel graph condition fails from a few directions: unless you say "path of length $k-1$ utilizing only vertices of degree $3$" there are paths of length $k-1$ through the "hub" connecting any two vertices ($k>4$) . And it includes k-cycles and large complete graphs and small stars... – Aaron Meyerowitz Mar 5 '11 at 15:25
Also, My star condition captures stars and only stars (except the 1 and 2 vertex stars..). Stars are a subclass of trees so you could just say that stars are self-defining wrt your tree condition. The $d(x) \ne d(y)$ condition captures exactly: empty graphs AND $K_{p,q}$ $p \ne q$ AND $K_{p,q,r}$ $p \ne q \ne r \ne p$ ..... In other words: complete multipartite graphs with parts of distinct sizes. Stars are $K_{1,r}$ – Aaron Meyerowitz Mar 5 '11 at 15:33
@Aaron: I considered paths as non-self-intersecting. – Hans Stricker Mar 5 '11 at 23:02

A different point of view: Consider asymmetric graphs. In such graphs every single node $v_i$ can be uniquely described by a first order property $(*)$ $\phi_i(x)$ which holds iff $x = v_i$. For finite graphs you have $Rxy \equiv \bigvee_i (x = v_{n_i} \wedge y = v_{m_i})$ for a suitable set of pairs $(v_{n_i}, v_{m_i})$. Now insert $(*)$ and you get

$$Rxy \equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))\ \ \ \(**)$$

This may turn the question partially uninteresting, since almost all graphs are trivially self-defining w.r.t. a first order property. So what might be rescued?

ADDENDUM 1: Assume we define $Rxy :\equiv \bigvee_i (\phi_{n_i}(x) \wedge \phi_{m_i}(y))$ where the $\phi_i(x)$ use the symbol $R$. This definition would be considered circular, but somehow, it's an equation, that can be "solved": by one (and only one?) graph, e.g. the one that gave rise to $(**)$.

How do I have to think about this (kind of circular or impredicative definition)?

ADDENDUM 2: The "solutions" of the informal and sketchy "equation"

$$Rxy \equiv \neg(\exists x_1)...(\exists x_n) Rxx_1 \wedge ... \wedge Rx_ny$$

are exactly the trees.

-