6
$\begingroup$

$\DeclareMathOperator\Sym{Sym}\DeclareMathOperator\Coh{Coh}$I have broken my question into a few sections for clarity and to provide sufficient context to the problem. I apologize for the length. The question is asked in the last section titled "Question".

Motivation

The Graph Reconstruction Conjecture states that any two simple graphs with equal decks (hypomorphic graphs) are isomorphic for graphs with $3$ or more vertices. An alternative statement of this conjecture is that for any deck of a simple graph, all corresponding "reconstructions" are isomorphic.

To make "reconstruction" precise, for a deck $D(G)$ of a simple graph of order $n$, we may choose an enumeration of each subgraph so that $D(G)=\{G_1,...,G_n\}$. For each subgraph, we may choose a bijection $\phi_i:V(G_i)\to [n]\setminus\{i\}$ where $V(G_i)$ is the vertex set of $G_i$. Moreover, we must impose that if $\{\phi_i(x),\phi_i(y)\}\in E(G_i)$ then $\{\phi_i(x),\phi_i(y)\}\in E(G_j)$ if $j\ne \phi_i(x)$ and $j\ne\phi_i(y)$. In words, if our choice of labeling on subgraph $i$ implies that if $\{a,b\}$ is an edge then $\{a,b\}$ must be an edge in any other subgraph so long as $a$ and $b$ are both present.

An Algebraic View of Reconstruction Let $D(G)$ be an unlabelled deck of some simple graph $G$ of order $n$. Choose an enumeration of the subgraphs such that $D(G)=\{G_1,...,G_n\}$. For each $G_i$ we may associate an adjacency matrix of size $(n-1)\times(n-1)$ and we would like to append a row and column of all zeros to these matrices so that they have dimension $n\times n$. We will refer to these matrices as $A_i$ for each $i\in \{1,...,n\}$.

Define,

$$\Psi(S)=\displaystyle\frac{1}{n-2} \displaystyle\sum_{i=1}^{n} S_i A_i S_i^T$$

where $S=(S_1,...,S_n)\in \Sym(n)^n$ and $\Sym(n)$ is the group of $n\times n$ permutation matrices. It can be easily demonstrated that,

  1. $\mathrm{tr}(\Psi(S))=0$
  2. $\Psi(S)$ is symmetric

The motivation of $\Psi$ is to encapsulate the reconstruction problem as posed in the motivation section above - the choice of labeling is equivalent to choosing some $n$-tuple of permutations on the "extended" subgraph adjaceny matrices (i.e. $A_i$). We say that $S$ is "coherent" if $\Psi(S)$ is a valid adjacency matrix. Moreover, we denote the set of all coherent values of $S$ as,

$$\Coh(\Psi) = \{S\in \Sym(n)^n \mid \Psi(S)\circ \Psi(S)=\Psi(S)\}$$

where $\circ$ denotes the Hadamard product. It is easy to show that this condition is equivalent to asserting that each entry of $\Psi(S)$ be either $0$ or $1$. This fact coupled with the symmetry and $0$ trace conditions above imply that $\Psi(S)$ would be a valid adjacency matrix.

The motivation of $\Coh(\Psi)$ is to algebraically encapsulate the set of all "coherent" reconstructions from the deck $D(G)$.

Question Is the following statement equivalent to the graph reconstruction conjecture?

For any $S_1, S_2\in \Coh(\Psi)$ there exists $Q\in \Sym(n)$ such that,

$\Psi(S_1) = Q \Psi(S_2) Q^T$

Additional Context For additional context, if this reformulation is in fact valid. I am looking to proceed as follows: Let $S_1, S_2\in \Coh(\Psi)$ and suppose $\Psi(S_1)$, $\Psi(S_2)$ are counterexamples to the GRC. Since these matrices are real and symmetric $\Lambda_1 = Q_1\Psi(S_1)Q_1^T$ and $\Lambda_2 = Q_2\Psi(S_2)Q_2^T$ for orthogonal matrices $Q_1$ and $Q_2$ and diagonal matrices of eigenvalues $\Lambda_1$, $\Lambda_2$. Tutte proved that the characteristic polynomial is reconstructable and thus a counterexample must be cospectral. Thus there exists $P\in \Sym(n)$ such that $\Lambda_1 = P\Lambda_2P^T$. Some algebra implies that,

$$\Psi(S_1) = (Q_1^TPQ_2)\Psi(S_2)(Q_2^TPQ_1)$$

It is clear that $(Q_1^TPQ_2)$ must be orthogonal. If we can show that $(Q_1^TPQ_2)\in \Sym(n)$ then this implies the GRC (of course assuming I have not made a mistake in reformulating).

$\endgroup$
4
  • $\begingroup$ Do you have a source for the claim that the characteristic polynomial is reconstructible? I can only find papers claiming that this is an open problem (up to the year 2000). $\endgroup$
    – M. Winter
    Aug 22, 2021 at 21:52
  • $\begingroup$ I'm glad you mentioned this. After more research it seems many papers claim there is such a result in "W.T. Tutte, All the king’s horses". But other sources seem to imply that either a generalized characteristic polynomial or the Tutte polynomial were proved to be reconstructable in said paper. In either case I cannot find a copy at the moment. I will add and update here if I find something. $\endgroup$ Aug 22, 2021 at 23:27
  • $\begingroup$ Interestingly, even Wikipedia mentions this as known without a source. $\endgroup$
    – M. Winter
    Aug 22, 2021 at 23:57
  • $\begingroup$ When talking about decks which are multisets it is better to use double braces to avoid the confusion with sets i.e: M = {{a,a,b,b,b,c}} $\endgroup$ Dec 21, 2023 at 12:11

1 Answer 1

1
$\begingroup$

If I am not missing anything crucial, the equivalence should be straight forward. However, given how you plan to proceed, you might not need this reformulation.


The equivalence

Let $D=\{G_1,...,G_n\}$ be a deck of graphs.

Your conjecture $\implies$ reconstruction conjecture

Let $G$ and $G'$ be two graphs with adjacency matrices $A$ and $A'$, both with deck $D$. Then there are $S,S'\in\mathrm{Coh}(\Psi)$ so that $\Psi(S)=A$ and $\Psi(S')=A'$. Assuming your conjecture, the permutation matrix $Q$ provides an isomorphism between $G$ and $G'$. Thus, the reconstruction conjecture holds.

Reconstruction conjecture $\implies$ your conjecture

Let $S,S'\in\mathrm{Coh}(\Psi)$. Then, as you already mentioned in your post, $A:=\Psi(S)$ and $A':=\Psi(S')$ are adjacency matrices. Let $G$ and $G'$ be the corresponding graphs. Then by how you defined $\Psi$, both $G$ and $G'$ have deck $D$, and assuming the reconstruction conjecture, $G$ and $G'$ are isomorphic. This isomorphism provides the permutation matrix $Q$ for your conjecture to hold.


Without reformulation

Given how you plan to proceed, I do not think that this reformulation is necessary. Let me rewrite your last paragaph:

Suppose that $G_1$ and $G_2$ are counterexamples to the GRC. Let $A_i$ be the adjacency matrix of $G_i$. Since these matrices are real and symmetric $\Lambda_1 = Q_1A_1 Q_1^T$ and $\Lambda_2 = Q_2A_2 Q_2^T$ for orthogonal matrices $Q_1$ and $Q_2$ and diagonal matrices of eigenvalues $\Lambda_1$, $\Lambda_2$. [...] $$A_1 = (Q_1^TP^TQ_2)A_2(Q_2^TPQ_1)$$ [...] If we can show that $Q_1^TP^TQ_2\in \mathrm{Sym}(n)$ then this implies that $G_1$ and $G_2$ are isomorphic, and thus, the GRC.

$\endgroup$

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.