DMAT_L13

Edge Reconstruction Conjecture

Theorem 1(Conjecture).

Let $G$,$H$ be two graphs on $n$ vertices with $m$ edges, with $m\ge 4$. Let the edge sets of $G$ and $H$ be $E(G)=\{e_1,...,e_m\}$ and $E(H)=\{f_1,...,f_m\}$. Suppose $G\setminus e_i\cong H\setminus f_i$ for all $1\le i\le m$. Then, $G\cong H$.

Info

Recall that a “homomorphism” is a structure preserving map, which in this context means mapping edges to edges. So, any map $\varphi$ which preserves edges is called a homomorphism. Just like in group theory, a bijective homomorphism is called an isomorphism, and two graphs are said to be isomorphic if there exists an isomorphism between them. Isomorphic graphs have the same structure up to relabelling of vertices.

The conjecture does not hold when $m=3$. The graphs $G=(V,E_1)$ and $H=(V,E_2)$ with $V=\{1,2,3,4\}$, $E_1=\{\{1,2\},\{2,3\},\{3,1\}\}$ and $E_2=\{\{1,2\},\{1,3\},\{1,4\}\}$ are a counterexample.

Theorem 2(Lemma).

Let $G$ be a graph with $E(G)=\{e_1,e_2,\dots ,e_m\}$. Then, it is sufficient to know the set of all maximal proper subgraphs of $G$, that is, $S=\{G\setminus e_i|i\in [m]\}$ to compute the number of edge-proper subgraphs of $G$ that are isomorphic to a given graph $T$.

Proof
Let $T$ be a graph with $j$ edges, $1\le j<m$. Let $\alpha$ be the number of subgraphs of $G$ that are isomorphic to $T$. Let ${\alpha }_i$ be the number of subgraphs of $G$ that are isomorphic to $T$ and contain the edge $e_i$. Then, $\alpha -{\alpha }_i$ is known since it is the number of subgraphs of $G\setminus e_i$ that are isomorphic to $T$. Thus from $S$ and $T$ we know $m$, $j$, and $\alpha -{\alpha }_i$. So, we also know

$$M=\sum _{i=1}^m(\alpha -{\alpha }_i)=m\alpha -\sum _{i=1}^m{\alpha }_i.$$

Note here that ${\sum }_{i=1}^m{\alpha }_i=j\alpha$, since every subgraph of $G$ that is isomorphic to $T$ is counted $j$ times in the sum. Thus, we have $M=(m-j)\alpha$. Since $m\ne j$, we have $\alpha =M/(m-j)$. Thus, the knowledge of $S$ an $T$ are sufficient to determine $\alpha$.

Theorem 3(Theorem (Lovasz)).

The Edge Reconstruction Conjecture is true when $m>\frac{1}{2}\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

Original paper by Lovasz

Proof

Let $\hat{G}\to \hat{H}$ (where $\hat{G}$ and $\hat{H}$ have the same number of vertices) represent the set of all isomorphisms from $\hat{G}$ to $\hat{H}$. We have to show that $G\to H$ is non-empty.

Let $A_i$ be the set of all bijections $\varphi$ from $V(G)$ to $V(H)$ such that if $e_i=\{x_{i_1},x_{i_2}\}\in E(G)$ then $\{\varphi (x_{i_1}),\varphi (x_{i_2})\}\in E(\overline{H})$, that is, $\varphi$ maps edge $e_i$ of $G$ to a non-edge of $H$. We want $|G\to H|=\left|X\setminus {\bigcup }_{i=1}^m{A}_i\right|$.By the principle of inclusion and exclusion, we have

$$\left|X\setminus \bigcup _{i=1}^m{A}_i\right|=\sum _{I\subseteq [m]}(-1{)}^{|I|}{A}_I.$$

For any $I\subseteq [m]$, define ${\hat{G}}_I=(V(\hat{G}),\{e_i|i\in I\})$. $A_I$ is the set of all bijections that map $e_i$ into $\overline{H}$ for all $i\in I$. So, $|A_I|=|G_I\to \overline{H}|$. Thus,

$$\begin{array}{rlr}|G\to H|& =\sum _{I\subseteq [m]}(-1{)}^{|I|}|G_I\to \overline{H}|.& (1)\end{array}$$

Similarly considering $H\to H$ we get

$$\begin{array}{rlr}|H\to H|& =\sum _{I\subseteq [m]}(-1{)}^{|I|}|H_I\to \overline{H}|.& (2)\end{array}$$

Denote the number of edge-proper subgraphs of $G$ which are isomorphic to a graph $T$ by ${\mathcal{S}}_G(T)$. Note from the preceding lemma that for any given graph $T$ with $1\le E(T)<m$, ${\mathcal{S}}_G(T)$ is completely determined by $\{G\setminus e_i|i\in [m]\}$. Similarly, ${\mathcal{S}}_H(T)$ is completely determined by $\{H\setminus f_i|i\in [m]\}$. From our hypothesis, we know that $\{G\setminus e_i|i\in [m]\}=\{H\setminus f_i|i\in [m]\}$, up to isomorphism. Thus, ${\mathcal{S}}_G(T)={\mathcal{S}}_H(T)$ for all $T$.

Now, let $\mathcal{T}$ be the set of all graphs possessing $j$ edges, where $1\le j<m$. Then,

$$\begin{array}{r}\sum _{I\subset [m]}(-1{)}^{|I|}|G_I\to \overline{H}|=\sum _{T\in \mathcal{T}}(-1{)}^{|E(T)|}{\mathcal{S}}_G(T)|T\to \overline{H}|\\ \\ \sum _{I\subset [m]}(-1{)}^{|I|}|H_I\to \overline{H}|=\sum _{T\in \mathcal{T}}(-1{)}^{|E(T)|}{\mathcal{S}}_H(T)|T\to \overline{H}|\end{array}$$

Thus, the terms in $(1)$ and $(2)$ with $I\ne [m]$ are equal. For $I=[m]$, note that $|G\to \overline{H}|=0$ and $|H\to \overline{H}|=0$ since $m>\frac{1}{2}\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Hence, $|G\to H|=|H\to H|>0$ (the identity isomorphism!), and we are done.

---

Generalizing the Inclusion Exclusion Principle

In order to further generalize the principle of inclusion and exclusion, we will develop some more theory on posets.

The Incidence Algebra of a Poset

Info

An algebra over a field $F$ is a vector space over $F$ that is also equipped with a bilinear multiplication operation $\cdot :V\times V\to V$.

Suppose that $P=(X,\le )$ is a poset and $|X|=n$. Define the incidence algebra of $P$ by

$$I(P)\equiv \{f:X\times X\to \mathbb{R}|f(x,y)=0\text{ unless }x\le y\}.$$

For $f,g\in I(P)$, define $(f+g)(x,y)\equiv f(x,y)+g(x,y)$ for all $x,y\in X$. Clearly, $f+g\in I(P)$.
For $\alpha \in \mathbb{R}\text{ and }f\in I(P)$, define $(\alpha \cdot f)(x,y)=\alpha f(x,y)$ for all $x,y\in X$ so that $\alpha \cdot f\in I(P)$.
For $f,g\in I(P)$, define

$$(f\cdot g)(x,y)\equiv \sum _{x\le z\le y}f(x,z)g(z,y)\forall x,y\in X,$$

and note that $(f\cdot g)\in I(P)$. Bilinearity is easily verified. Thus, with these definitions, the incidence algebra is indeed an algebra.

Matrix Representation of the Algebra

Info

A linear extension of a poset $P=(X,\le )$ is a totally ordered set $P^{\prime }=(X,{\le }^{\prime })$ that respects the poset’s structure. That is, if $x,y\in X$, $x\le y$ $⟹$ $x{\le }^{\prime }y$.

Let $P^{\prime }=\{x_1{\le }^{\prime }{x}_2{\le }^{\prime }\cdots {\le }^{\prime }{x}_n\}$ be a linear extension of $P$. Let ${\mathcal{M}}_n(\mathbb{R})$ denote the algebra of $n\times n$ real matrices. Define a map $\phi :I(P)\to {\mathcal{M}}_n(\mathbb{R})$ by $f\mapsto M_f\equiv [f(x_i,x_j){]}_{n\times n}$.

We claim that $\phi$ is an injective homomorphism. The injective part being obvious and trivial properties being easily proved, we will only check that $\phi (fg)=\phi (f)\phi (g)$. Let $M_{(i,j)}$ denote the $i,j$th entry of $M$.

$$\begin{array}{rl}\phi (fg{)}_{(i,j)}=(fg)(x_i,x_j)& =\sum _{x_i\le z\le x_j}f(x_i,z)g(z,x_j).\\ & \\ (\phi (f)\phi (g){)}_{(i,j)}& =\sum _{k=1}^{n}f(x_i,x_k)g(x_k,x_j)\\ & =\sum _{x_i\le x_k\le x_j}f(x_i,x_k)g(x_k,x_j).\end{array}$$

Note that $M_f$ is always upper triangular, and that the set of all upper triangular matrices in ${\mathcal{M}}_n(\mathbb{R})$ forms a subalgebra of ${\mathcal{M}}_n(\mathbb{R})$. Since $\phi$ is an injective homomorphism, $I(P)\cong \mathrm{Im}\phi$, so $I(P)$ is isomorphic to a subalgebra of the algebra of upper triangular $n\times n$ matrices.

Now we shall have a look at a few important functions in $I(P)$.

Invertible elements in I(P)

The identity element of $I(P)$ is

$$e(x,y)=\{\begin{array}{ll}1,& x=y\\ 0& \text{otherwise.}\end{array}$$

It is easy to verify that for any $f\in I(P)$, we have $f\cdot e=e\cdot f=f$. Note that the identity is unique, since the identity matrix is unique in $\phi (I(P))$. Having defined the identity, we can talk about invertible elements.

Clearly,

$$\begin{array}{rl}& f\text{ is invertible }\\ ⟺& M_f=\phi (f)\text{ is invertible}\\ ⟺& \text{All diagonal entries of }{M}_f\text{ are nonzero}\\ ⟺& f(x,x)\ne 0\forall x\in X.\end{array}$$

Since $I(P)\cong \mathrm{Im}\phi$, $f^{-1}$ is given by $M_f^{-1}$. Indeed, $f{f}^{-1}=e$. If the $f(x,x)=1$ for all $x\in X$ and $f(x,y)\in \mathbb{Z}$ for all $x,y\in X$, then $f^{-1}$ is also integer valued for all $x,y\in X$. This is because if a upper triangular matrix $M$ has integer valued entries and all diagonal entries equal to 1, $M^{-1}$ is also diagonal with integer valued entries. We have $M=I-N$ for a strictly upper triangular (and hence nilpotent) matrix $N$. Thus, $M^{-1}=I+N+N^2+\cdots +N^k$ for some $k\in \mathbb{N}$.

The Möbius function

Define the incidence function $i$ of $I(P)$ to be

$$i(x,y)=\{\begin{array}{ll}1& x\le y\\ 0& \text{otherwise.}\end{array}$$

The Möbius function is defined to be the inverse $\mu$ of the incidence function $i$. From the previous section, we know that $\mu$ must be integer valued. Since $\mu i=e$, we know that for all $x\in X$,

$$\begin{array}{rl}& \mu i(x,x)=1\\ ⟹& \mu (x,x)i(x,x)=1\\ ⟹& \mu (x,x)=1.\end{array}$$

If $x\ne y$,

$$\begin{array}{rl}& \mu i(x,y)=0\\ ⟹& \sum _{x\le z\le y}\mu (x,z)i(z,y)=0\\ ⟹& \sum _{x\le z\le y}\mu (x,z)=0\\ ⟹& \mu (x,y)=-\sum _{x\le z<y}\mu (x,z).\end{array}$$

Thus, we get an inductive definition for $\mu$:

$$\mu (x,y)=\{\begin{array}{ll}1& \text{if }x=y\\ -{\sum }_{x\le z<y}\mu (x,z)& \text{if }x\ne y.\end{array}$$

Example 4(The Möbius function of a total order).

Suppose $P$ is a total order $a_1<a_2<\cdots <a_r$.
Then it is easily verified that

• $\mu (a_i,a_i)=1\forall 1\le i\le r$
• $\mu (a_i,a_{i+1})=-\mu (a_i,a_i)=-1\forall 1\le i\le r-1$
• $\mu (a_i,a_j)=0\forall j>i+1$

Lemma 5(Lemma).

The power set $\mathcal{P}([n])$ is order isomorphic to the cartesian product ${\prod }_{i=1}^n{P}_i$ where $P_i=\{a_i,b_i\}$ such that $a_i<b_i$

Proof
Indeed, $A\mapsto ({\alpha }_1,{\alpha }_2,...,{\alpha }_n)$ where ${\alpha }_i=a_i$ if $i\notin A$ and ${\alpha }_i=b_i$ if $i\in A$ is an order preserving bijection

Lemma 6(Lemma).

Let $P_1,P_2,...,P_n$ be posets with Möbius functions ${\mu }_i$. if $P={\prod }_{i=1}^n{P}_i$, then its Möbius function $\mu$ is defined by $\mu (({\alpha }_1,{\alpha }_2,...,{\alpha }_n),({\beta }_1,{\beta }_2,...,{\beta }_n))={\prod }_{i=1}^n{\mu }_i({\alpha }_i,{\beta }_i)$

Proof
call the product function on the right hand side $r$. Let $i$ be the incidence function of $P$. it is easily verified that $r\cdot i=i\cdot r=e$ and since inverses are unique, we have that the two functions are identical

---

Chains and antichains in posets

Note that if $C$ is a chain and $A$ is an antichain in a poset, then $|C\cap A|\le 1$. From this, we immediately see:

Theorem 7(Lemma).

1. If a poset $P$ has a chain of size $r$, then it cannot be partitioned into fewer than $r$ antichains.
2. If a poset $P$ has an antichain of size $r$, then it cannot be partitioned into fewer than $r$ chains.

So, if $r$ is the size of the longest chain in $P$, we know that $P$ cannot be partitioned into fewer than $r$ antichains. Can $P$ be partitioned into $r$ antichains?

Theorem 8(Theorem).

If $r$ is the maximum chain length in a poset $P$, then $P$ can be partitioned into $r$ antichains (and no fewer).

Proof
Define the height of an element $x\in P$ to be the greatest number of elements in a chain whose greatest member is $x$. Let $A_i$ be the set of elements of height $i$. Then, by hypothesis, $A_i=\varnothing$ for $i>r$, so $P=A_1\bigsqcup \cdots \bigsqcup A_r$; and each $A_i$ is an antichain, since if $x\in A$ and $x<y$, then there is a chain $x_0<\cdots <x_i=x<y$, so $y$ has a height greater than $i$. The no fewer part follows from the previous lemma.

The proof of the dual result is more involved.

Theorem 9(Dilworth's theoem).

If $r$ is the maximum antichain length in $P$, then $P$ can be partitioned into $r$ chains (and no fewer).

Proof
The proof is by induction on $|P|$. Clearly, the result holds for singleton posets. So suppose that it is true for all posets with fewer points than $P$. Let $x$ be a minimal element of $P$ (recall that a minimal element is one which is not greater than any other element in the poset).

Case 1: $x$ is incomparable with everything else in $P$. Then the largest antichain in $P\setminus \{x\}$ has size $r-1$, since adjoining $x$ gives a larger antichain. By induction, $P\setminus \{x\}$ can be partitioned into $r-1$ chains; we add the singleton chain $\{x\}$ to produce the required partition.

Case 2: Some other points are comparable with $x$.

Note that the length of the longest antichain in $P\setminus \{x\}$ will remain $r$, since if required $x$ can be replaced with any other element it is comparable to. By induction, we can partition $P\setminus \{x\}$ into $r$ chains $C_1,\dots ,C_r$. For each $i$, let $T_i$ be the set of elements of $C_i$ which are comparable to $x$., and define $B_i\equiv C_i\setminus T_i$. Note that every element in $T_i$ is greater than $x$ for all $i$, since $x$ is a minimal element. Also, $T_i$ must be above $B_i$ for all $i$, since otherwise the elements of $B_i$ would be comparable to $x$. Color the elements of $B_i$ with color $c_i$.

Next, define $B\equiv B_1\bigsqcup \cdots \bigsqcup B_r$. $B$ is the set of all elements incomparable with $x$. By the argument in Case 1, $B$ can be written as the union of $r-1$ chains $C_1^{\prime },\dots ,C_{r-1}^{\prime }$.

---

Let $\varphi$ be a map from $V$ to $V$ which maps $f$ to $g$.

It can be represented by a $2^n\times 2^n$ matrix. Let Let $X^{\prime }=\{x_1\le x_2\le \cdots \le x_n\}$ be a linear extension of the poset $\mathcal{P}(X)$.