Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
1  
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. –  Pete L. Clark Jan 5 '10 at 14:27
    
In the corrected version I hope to have said so. –  Hans Stricker Jan 5 '10 at 15:12
    
Is there a non trivial example? –  Mariano Suárez-Alvarez Jan 5 '10 at 16:55
    
I will provide some soon! –  Hans Stricker Jan 5 '10 at 17:05
3  
Posts that are edited many times automatically become CW. (I don't know why.) –  Reid Barton Jan 5 '10 at 21:41

1 Answer 1

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.

Let me give an example: consider the graph alt text

Then the formula $\phi_1(v)$ corresponding to the vertex $v_1$ in this construction is:

$$(\exists x_2,x_3,x_4,x_5)(v\neq x_2\land v\neq x_3\land v\neq x_4\land v\neq x_5\land x_2\neq x_3\land x_2\neq x_4\land x_2\neq x_5$$ $$\land x_3\neq x_4\land x_3\neq x_5\land x_4\neq x_5\land v\sim x_2\land v\sim x_3\land v\not{\sim}x_4\land v\not{\sim}x_5 \land x_2\sim v\land x_2\not{\sim}x_3$$ $$\land x_2\sim x_4\land x_2\not{\sim}x_5\land x_3\sim v\land x_3\not{\sim}x_2\land x_3\sim x_4\land x_3\not{\sim}x_5\land x_4\not{\sim}v\land x_4\sim x_2\land x_4\sim x_3$$ $$\land x_4\sim x_5\land x_5\not{\sim}v\land x_5\not{\sim}x_2\land x_5\not{\sim}x_3\land x_5\sim x_4)$$

share|improve this answer
    
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). –  Hans Stricker Jan 5 '10 at 21:21
1  
@Hans: how do you express the property "$v$ has exactly one neighbor" formally? –  Mariano Suárez-Alvarez Jan 5 '10 at 21:24
    
there is an x with Rvx and for each y holds: Rvy -> x = y –  Hans Stricker Jan 5 '10 at 21:28
1  
Well, since you are using equality of vertices, you are indeed including equality in your language :) –  Mariano Suárez-Alvarez Jan 5 '10 at 22:17
1  
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. –  Mariano Suárez-Alvarez Jan 6 '10 at 14:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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