-1
$\begingroup$

Motivation (added)

A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$.

A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by $2^k$ population numbers $n_i$, corresponding to the $2^k$ combinations of predicates, $\sum_{i=1}^{2^k} n_i = n$

A finite $n$-set with 1 binary relation (a graph $G$) can be uniquely described (up to isomorphism) by $k$ population numbers $n_i$, corresponding to its $k$ $Aut(G)$-orbits, provided these are appropriately described, $\sum_{i=1}^{k} n_i = n$.

I want to clarify what an appropriate description of the orbits might be and whether there is something like a canonical description of the orbits.

Definition 1

Let $v$, $w$ be vertices of a finite graph $G$. $v$ and $w$ are conjugate ($v \sim w$) iff there is a $g \in Aut(G)$ with $g(v) = w$.

Question 1 (postponed)

Is there an official and more common name for this equivalence? (Comment: I formerly called it "equivalent" but already changed this to "conjugate", thanks to Pete's hint.)

Definition 2 (third revision)

Let $G$ be a graph, $v \in V(G)$ and $\phi_v(x)$ be a first order vertex property (formulated in the first order language of graphs) such that $(\forall w \in V(G)\ )\phi_v(w) \Leftrightarrow v \sim w$.

Let $\lbrace \phi_v(x)\rbrace_{[v] \in G/_\sim}$ be a family of such properties.

If all graphs $H$ for which there is a bijection $f:V(G)\rightarrow V(H)$ with

$\phi_v(x) \Leftrightarrow \phi_v(f(x))$ for all $[v] \in G/_\sim$

are isomorphic to $G$, we call the family of properties $\lbrace \phi_v(x)\rbrace_{[v] \in G/_\sim}$ distinguishing with respect to $G$.

(Comment: I added w.r.t $G$ to make things clearer and to be more precise.)

Claim

Given a graph $G$ and a distinguishing family of properties w.r.t. $G$ then the population function $f: \lbrace \phi_v(x)\rbrace_{[v] \in G/_\sim} \rightarrow \mathbb{N}$ with $f(\phi_v(x)) = |[v]|$ determines the graph up to isomorphism.

Definition 2a (added)

A distinguishing family of properties is minimal if its overall number of bound variables is minimal.

(Comment: Minimal distinguishing properties might serve as a canonical form of a graph.)

Question 2

Is there an official and more common name for distinguishing properties?

Question 3 (second revision)

Can a distinguishing family of properties be computed from the adjacency matrix in linear time? Or is this problem provably as hard as graph isomorphism?

Addendum: As pointed out in the second answer (Mariano's) it is straight forward to begin with a complete description of the graph (one existential formula, stating that there are exactly $n$ different vertices and their relations) and make successively each single variable free. In the resulting $|G|$ formulas one then has to find the orbits (= equivalent formulas) which is probably as hard as graph isomorphism.

Question 3a (added)

Can a minimal distinguishing family of properties be computed from the adjacency matrix in linear time? Or is this problem provably as hard as graph isomorphism?

Question 4 (postponed)

Which language $L$ is appropriate? Can it always be the language of first order logic with a graph specific signature?

Addendum: Example

The family of properties with the single member $\phi(x)$ = "x has exactly one neighbour" together with the number of vertices that share this property - 2 - fix $K_2$

Addendum: More examples

Definitions:

  1. Let a d-neighbour of x be a vertex d edges away from x.
  2. Let $\phi_d^n$ stand for x has exactly n d-neighbours.
  3. Let $C_l^n$ be the graph consisting of n cycles of lenght $l, l \geq 2$, $C_2^1 = K_2$.
  4. Let $P_l$ be the path graph of length $l$.

(1)

Consider the vertex transitive graphs $C_2^n$.

For each $C$ of them the one-element (vertex transitivity!) family of properties $\lbrace \phi_1^1 \rbrace$ is distinguishing w.r.t. $C$.

(2)

Consider the vertex transitive graphs $C_l^1, l > 2$, $l$ prime or $l = 4$.

For each $C$ of them the one-element family of properties $\lbrace \phi_1^2 \rbrace$ is distinguishing w.r.t. $C$.

For $C = C_3^2$ (vertex transitive, too) $\lbrace \phi_1^2 \wedge \phi_2^0 \rbrace$ is distinguishing w.r.t. $C$.

For $C = C_6^1$ (vertex transitive, too) $\lbrace \phi_1^2 \wedge \phi_2^2 \rbrace$ is distinguishing w.r.t. $C$.

These examples seem to be easily expanded by combinatorical means.

(3)

Consider the path graphs $P_l$ with $\lceil \frac{l}{2} \rceil$ conjugacy classes of vertices. Let $\psi_d$ stand for x has a d-neighbour with degree 1. Then

$\lbrace \phi_1^1 \rbrace\ \cup\ \lbrace \phi_1^2 \wedge \psi_k \rbrace_{k = 1,..,\lceil \frac{l}{2} \rceil - 1}$

is a distinguishing family of properties (not necessarily minimal).

$\endgroup$
12
  • 1
    $\begingroup$ The property "x has exactly one neighbor" does not satisfy the defining condition for all graphs: just because two vertices have exactly one neighbor does not mean they are conjugate. If you want $\phi$ to have this property only with respect to a fixed graph $G$, you need to say so. $\endgroup$ Jan 5, 2010 at 14:27
  • $\begingroup$ In the corrected version I hope to have said so. $\endgroup$ Jan 5, 2010 at 15:12
  • $\begingroup$ Is there a non trivial example? $\endgroup$ Jan 5, 2010 at 16:55
  • $\begingroup$ I will provide some soon! $\endgroup$ Jan 5, 2010 at 17:05
  • 3
    $\begingroup$ Posts that are edited many times automatically become CW. (I don't know why.) $\endgroup$ Jan 5, 2010 at 21:41

1 Answer 1

2
$\begingroup$

If you allow equality then it is trivial that every graph has a distinguishing famil of properties. Since you are considering the property "$v$ has exactly one neighbor", I think you are including equality...

Indeed, let $G$ be a graph, let $v_1,\dots,v_n$ be its vertices, and let me construct a 'distinguishing property' $\phi$ for $v_1$: put $\phi=(\exists x_2,x_2,\dots,x_n)\Phi(v_1,x_2,\dots,x_n)$ with $\Phi(x_1,\dots,x_n)$ being the formula which says that all its arguments are distinct and that the $i$th and $j$th arguments are $\sim$-related iff the vertices $v_i$ and $v_j$ are connected in the graph $G$.

Using formulas constructed like this, I think you can answer your (main?) question.

$\endgroup$
8
  • $\begingroup$ I am not quite sure if I understand your answer: where do you think do I include equality (and which kind of)? And if it should be trivial to construct a "distinguishing family of properties w.r.t to G" - as you point out - I would have to revise my definition since I did not want to pose a trivial question (see my Question 3). $\endgroup$ Jan 5, 2010 at 21:21
  • 1
    $\begingroup$ @Hans: how do you express the property "$v$ has exactly one neighbor" formally? $\endgroup$ Jan 5, 2010 at 21:24
  • $\begingroup$ there is an x with Rvx and for each y holds: Rvy -> x = y $\endgroup$ Jan 5, 2010 at 21:28
  • 1
    $\begingroup$ Well, since you are using equality of vertices, you are indeed including equality in your language :) $\endgroup$ Jan 5, 2010 at 22:17
  • 1
    $\begingroup$ I do not know why you think it is hard to find the conjugate formulas... You just have to pick one representative for each conjugacy class and construct the corresponding formula. The complexity in finding the conjugacy class has absolutely nothing to do with 'distinguishing properties': it is just a hard problem. $\endgroup$ Jan 6, 2010 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.