Size reconstructibility of graphs

Lemma 2.1.$0\le \tilde{m}-m\le \frac{k\left(n-1\right)}{n-2-k}$.

Proof of Lemma 2.1.Suppose that we have the entire deck of $G$. Every edge of $G$ is on exactly $n-2$ cards and therefore ${\sum }_{i=1}^{n}e\left(G_i\right)=\left(n-2\right)m$. Furthermore, for every $v_i\in V\left(G\right)$, we have that $e\left(G_i\right)=m-d\left(v_i\right)$. It follows that

The claimed bounds follow from the fact that $0\le d\left(v\right)\le n-1$ for all $v\in V\left(G\right)$. $\square$

Lemma 2.2.We have $d_t\left(G_i\right)\le d_t+d_{t+1}$ and

In particular, $0\le s_t-{\tilde{s}}_t\le k\left(d_t+d_{t+1}\right)$.

Proof.A vertex of degree $t$ on a card $G_i$ can either have degree $t$ in the graph $G$ or degree $t+1$ (in the case where it is a neighbor of $v_i$). This shows that $d_t\left(G_i\right)\le d_t+d_{t+1}$ for all $i$.

A vertex of degree $t+1$ gets counted exactly once in ${\sum }_{i=1}^n{d}_t\left(G_i\right)$ for each of its neighbors; a vertex of degree $t$ gets counted on all cards except for its own and those of its neighbors. This proves (2). The last claim follows by combining the fact that $s_t-{\tilde{s}}_t={\sum }_{j=n-k+1}^n{d}_t\left(G_j\right)$ with the first claim. $\square$

Observation 2.3.If $\mathcal{D}\left(G\right)=\left\{G_1,\text{…},G_n\right\}$, then $\mathcal{D}\left(\overline{G}\right)=\left\{{\overline{G}}_1,\text{…},{\overline{G}}_n\right\}$. Moreover, we have that $d_t\left(\overline{G}\right)=d_{n-1-t}\left(G\right)$ for any $t\in \left\{0,\text{…},n-1\right\}$.

Lemma 2.4.Suppose that $k\le \frac{n}{3}$. For each $t\in \left\{0,\text{…},n-1\right\}$ we can calculate a value $d_t^{*}$ from the cards that satisfy $\frac{1}{4}{d}_t-1\le d_t^{*}\le d_{t-1}+d_t+d_{t+1}$.

Proof.We will consider two cases: when $t<\frac{n}{2}$ and when $t\ge \frac{n}{2}$.

Case 1. $t<\frac{n}{2}$.

Define

Note that $d_t^{*}$ can be calculated from the given cards and that $d_t^{*}\le d_t+d_{t+1}$ by Lemma 2.2.

Let $N$ be the number of times a vertex of degree $t$ in $G$ is seen as a vertex of degree $t-1$ in the cards $G_1,\text{…},G_{n-k}$. We will find upper and lower bounds for $N$. For the upper bound, note that a vertex of degree $t$ appears as a vertex of degree $t-1$ on the card $G_i=G-v_i$ if and only if $v_i$ is one of its neighbors. Therefore, $N\le t{d}_t$.

Now consider the card $G_i$ for some $i\in \left[n-k\right]$. We claim that there are at least $d_t-1-d_t\left(G_i\right)$ vertices that have degree $t-1$ in $G_i$ but degree $t$ in $G$. Indeed, the only missing vertex is $v_i$ (which might have degree $t$) and at most $d_t\left(G_i\right)$ of the other vertices with degree $t$ in $G$ have degree $t$ in $G_i$. It follows that $N\ge {\sum }_{i=1}^{n-k}\left(d_t-1-d_t\left(G_i\right)\right)$. We combine these bounds on $N$ to get

Rearranging and using the assumptions that $t<\frac{n}{2}$ and $n-k\ge \frac{2n}{3}$, we find $\frac{2}{3}{d}_t^{*}\ge \frac{1}{6}{d}_t-\frac{2}{3}$. It follows that $d_t^{*}\ge \frac{1}{4}{d}_t-1$.

Case 2. $t\ge \frac{n}{2}$.

Define

As $n-1-t<\frac{n}{2}$, this is well defined. From the argument above, we have By Observation 2.3, we see that As $d_{t-1}$ and $d_{t+1}$ are both nonnegative for every value of $t$, the result follows. $\square$

Lemma 2.5.Suppose $0\le \beta <1$ and let $\gamma =\frac{3}{4}+\frac{1}{4}\beta$. Suppose $n$ is sufficiently large and $k=O\left(n^{\beta }\right)$. Then, for any graph $G$ of order $n$ and any deck of $n-k$ cards, the value of $d_t$ can be calculated exactly for all but $O\left(n^{\gamma }\right)$ values of $t$.

Proof.Recall from Lemma 2.2 that

and that ${\tilde{s}}_t={\sum }_{i=1}^{n-k}{d}_t\left(G_i\right)$ approximates $s_t$ where $0\le s_t-{\tilde{s}}_t\le k\left(d_t+d_{t+1}\right)$. Let $q=\frac{t+1}{n}\in \left[0,1\right]$. Then $\frac{s_t}{n}=\left(1-q\right)d_t+q{d}_{t+1}$ and Our goal will be to find values of $t$ for which there is only one choice of $\left(a,b\right)$ such that $\left|\left(1-q\right)a+qb-\frac{{\tilde{s}}_t}{n}\right|\in \left[0,\frac{k\left(d_t+d_{t+1}\right)}{n}\right]$.

To achieve this, we first restrict to those values of $t$ for which we can calculate an upper bound on $d_t$ and $d_{t+1}$ from the cards. Assume that $n$ is sufficiently large to ensure $k\le \frac{n}{3}$. Lemma 2.4 then applies to ensure that, for all $t$ the quantity $d_t^{*}$ (which is defined in (3) and (4) and can be calculated from the cards) satisfies $\frac{1}{4}{d}_t-1\le d_t^{*}\le d_{t-1}+d_t+d_{t+1}$. By the lower bound, if $d_t^{*}$ is small, then $d_t$ is small as well. We use the upper bound to show that $d_t^{*}$ is small for most values of $t$. Indeed, let $K=n^{1-\gamma },I=\left\{0,\text{…},n-1\right\}$, and $A=\left\{t\in I:d_t^{*}+1\ge \frac{1}{4}K\right\}$. Then

and hence $\mid A\mid \le 16n∕K=16n^{\gamma }$. For all $t$ in the set $I\prime =\left\{t\in I:t,t+1\notin A\right\}$, we know that $d_t,d_{t+1}<K$. Since $\mid \left\{t\in I:t+1\in A\right\}\mid \le \mid A\mid$, by restricting to $I\prime$, we remove at most $O\left(n^{\gamma }\right)$ potential $t$.

For all $t\in I\prime$, we know that

It remains to determine for which $q=\frac{t+1}{n}$ the following holds: any two elements in $X=\left\{\left(1-q\right)a+qb:a,b\in \left\{0,\text{…}\lfloor K\rfloor \right\}\right\}$ take values that are at least $\frac{4Kk}{n}$ apart, so that there is at most one $\left(1-q\right)a+qb\in X$ within $\frac{2Kk}{n}$ of ${\tilde{s}}_t$. For all such $t\in I\prime$, we can then reconstruct $d_t$ and $d_{t+1}$ from the cards as the unique choices for $a$ and $b$.

Let $M=\frac{4Kk}{n}$. Suppose that, for some $\delta <M$, we are able to find elements $a>a\prime$ and $b<b\prime$ within $\left\{0,\text{…},\lfloor K\rfloor \right\}$ satisfying $a\left(1-q\right)+bq=a\prime \left(1-q\right)+b\prime q+\delta$. Rearranging, we get

In particular, $\left(b\prime -b+a-a\prime \right)q+\delta$ is an integer. As $b\prime -b+a-a\prime \in \left\{1,\text{…},\lfloor 2K\rfloor \right\}$, it suffices to ensure that, for all $y\in \left\{1,\text{…},\lfloor 2K\rfloor \right\}$, $yq$ is at distance at least $M$ from all integers $x\in \left\{1,\text{…},\lfloor K\rfloor \right\}$. Let and As argued above, for each $t\in I\prime \backslash S$ we are able to “guess” the values of $d_t$ and $d_{t+1}$. It remains to bound the size of $S$. The set $R$ has size less than $2K^2$. For each choice of $r\in R$, there are at most $2Mn$ elements of the form $\frac{i}{n}$ with $i\in \left\{0,\text{…},n-1\right\}$ that are within $M$ of $r$. This shows that $\mid S\mid \le 2Mn\mid R\mid \le 16k{K}^3$. Recall that $k=O\left(n^{\beta }\right)$, $16K^3=O\left(n^{3\left(1-\gamma \right)}\right)$, and $\gamma =\frac{3}{4}+\frac{1}{4}\beta$. We calculate Let $J=I\prime \backslash S$. For every $t\in J$, we can calculate $d_t$ exactly and furthermore $\mid I\backslash J\mid =\mid \left(I\backslash I\prime \right)\cup S)\mid =O\left(n^{\gamma }\right)$ as desired. $\square$

Theorem 1.2.For $n$ sufficiently large and $k\le \frac{1}{20}\sqrt{n}$, the number of edges $m$ of a graph $G$ on $n$ vertices is reconstructible from any $n-k$ cards.

Proof.Let $n$ be sufficiently large and $k=\lfloor \frac{1}{20}\sqrt{n}\rfloor$. Let $G$ be a graph on $n$ vertices and let $G_1,\text{…},G_{n-k}$ be the $n-k$ cards of $G$ that we are given.

Our goal is to determine $d_t$ for many values of $t$. We will handle values of $t$ for which $d_t>\sqrt{n}$ separately from those $t$ where $d_t\le \sqrt{n}$. For this reason, it will be convenient to say that $d_t$ is big if $d_t>\sqrt{n}$ and little if $d_t\le \frac{3}{4}\sqrt{n}$.

Claim 1.Suppose that, for some $t\le \frac{2n}{3}-1$, the value of $d_{t+1}$ is known exactly and is not big. Then either $d_t$ can be calculated exactly or $d_t$ can be identified as being big.

Proof.Since we can calculate ${\tilde{s}}_t={\sum }_{i=1}^{n-k}{d}_t\left(G_i\right)$ from the cards, if $d_{t+1}$ is known, then we can calculate

from the cards. By Lemma 2.2, where $0\le s_t-{\tilde{s}}_t\le k\left(d_t+d_{t+1}\right)$. In particular $d_t\ge d_t^{\prime }$, so we recognize that $d_t$ is big if $d_t^{\prime }>\sqrt{n}$. We now show that, if $d_t^{\prime }\le \sqrt{n}$, then the closest integer to $d_t^{\prime }$ equals $d_t$.

Since $t+1\le \frac{2n}{3}$ and $d_{t+1}$ is not big,

We conclude that $d_t-d\prime <\frac{1}{2}$ if $d_t\le 2\sqrt{n}$. Hence the closest integer to $d_t^{\prime }$ equals $d_t$ in this case.

From the calculation in (5) we also find

if $d_t>2\sqrt{n}$. Hence either $d_t^{\prime }>\sqrt{n}$ (in which case $d_t$ is big) or rounding it to the nearest integer gives us $d_t$ exactly. $\square$

Claim 2.Suppose that, for some $t\ge \frac{n}{3}+1$, the value of $d_{t-1}$ is known exactly and is not big. Then either $d_t$ can be calculated exactly or $d_t$ can be identified as being big.

Proof.If $t\ge \frac{n}{3}+1$, then $n-t-1\le \frac{2n}{3}-1$. By Observation 2.3, we have $d_{n-t}\left(\overline{G}\right)=d_{t-1}\left(G\right)$. Apply Claim 1 to $\overline{G}$ to see that either $d_t\left(G\right)=d_{n-t-1}\left(\overline{G}\right)$ can be calculated exactly or it can be identified as being big. $\square$

Claim 3.The interval $\left[\frac{n}{3},\frac{2n}{3}\right]$ contains $2k$ consecutive values of $t$ such that every $d_t$ can be calculated exactly and they are all little.

Proof.Let $I=\left[\frac{n}{3},\frac{2n}{3}\right]\cap \mathbb{N}$. Lemma 2.5 with $\beta =\frac{1}{2}$ gives a set $J\subseteq I$ and a constant $c$ such that $\mid J\mid \le c{n}^{\frac{7}{8}}$ and we can calculate $d_t$ exactly if $t\in I\backslash J$.

Partition $I$ into $\lfloor \frac{n}{6k}\rfloor$ intervals of length $2k$. At most $\lfloor \frac{c{n}^{7∕8}}{2k}\rfloor$ of them are completely contained in $J$. For $n$ sufficiently large, $\lfloor \frac{n}{6k}\rfloor -\lfloor \frac{c{n}^{7∕8}}{2k}\rfloor \ge \frac{n}{8k}$. Therefore, for these values of $n$, there are at least $\frac{n}{8k}$ intervals which are not completely contained within $J$. By Claims 1 and 2, we are able to calculate $d_t$ exactly for all values of $t$ in each of these intervals unless the interval happens to contain a value of $t$ for which $d_t$ is big.

We know that there are at most $\frac{4}{3}\sqrt{n}$ values of $t\in \left\{0,\text{…},n-1\right\}$ for which $d_t$ is not little. Therefore, as $\frac{n}{8k}\ge \frac{5}{2}\sqrt{n}>\frac{4}{3}\sqrt{n}$, there exists an interval which is not completely contained within $J$ and which only contains values of $d_t$ that are little, each of which we can calculate exactly. $\square$

By Claim 3, we can find an interval $\mathcal{I}=\left\{b,b+1,\text{…},b+2k-1\right\}\subset \left[\frac{n}{3},\frac{2n}{3}\right]$ such that, for every $t\in \mathcal{I}$, we can calculate $d_t$ exactly and it is little. We may then recursively apply Claim 1, starting with $t+1=b$. We continue until either we reach $d_0$ or we hit a big vertex $d_{t_{\ell }}$ for some $t_{\ell }<b$. Similarly, we may recursively apply Claim 2, starting with $t-1=b+2k-1$. Again, we will either calculate $d_{n-1}$ or we will identify that $d_{t_r}$ is big for some $t_r>b+2k-1$.

If we are able to calculate both $d_0$ and $d_{n-1}$, then we will know $d_t$ for every $t\in \left\{0,\text{…},n-1\right\}$. This tells us the degree sequence of $G$ and hence we can directly calculate $m$.

Therefore, we may assume that we have the following situation: there exists an interval $\mathcal{J}\supseteq \mathcal{I}$ with endpoints $t_{\ell }$ and $t_r$ such that $t_{\ell }<t_r$. For every $t\in \mathcal{J}\backslash \left\{t_{\ell },t_r\right\}$, the value $d_t$ is known exactly and is not big. At least one of $d_{t_{\ell }}$ and $d_{t_r}$ has been identified as being big. By Observation 2.3, we may assume that $d_{t_{\ell }}$ is big.

By Lemma 2.1, the estimate $\tilde{m}$ for $m$ that we can obtain from the cards $G_1,\text{…},G_{n-k}$ satisfies $\tilde{m}=m+\alpha$ with $0\le \alpha \le \lfloor \frac{k\left(n-1\right)}{n-2-k}\rfloor$. For $n$ sufficiently large, we have $n-1<2\left(n-2-k\right)$ and hence $\alpha <2k$. Recall from the proof overview that ${\tilde{d}}_t=\mid \left\{i\in \left\{1,\text{…},n-k\right\}:\tilde{m}-e\left(G_i\right)=t\right\}\mid$ can be calculated from the cards and that our goal is to discover the “shift” $\alpha =\tilde{m}-m$ in this sequence. The overall shape of ${\tilde{d}}_0,\text{…},{\tilde{d}}_{n-1}$ will be the same as the overall of shape of $d_0,\text{…},d_{n-1}$ but shifted to the right by $\alpha$. Moreover, we are “missing” $k$ values, so that ${\sum }_{t=0}^{n-1}\mid d_t-{\tilde{d}}_{t+\alpha }\mid =k$. (Note that we need to calculate ${\tilde{d}}_t$ for $0\le t\le n+2k$ and that, for $t+\alpha \ge n$, it is possible for ${\tilde{d}}_{t+\alpha }$ to take a nonzero value.)

Although we do not know the exact value of $d_{t_{\ell }}$, it is sufficient to redefine each $d_t$ and ${\tilde{d}}_t$ to be the minimum of their current value and $\sqrt{n}$. After doing this, we still have ${\sum }_{t=0}^{n-1}\mid d_t-{\tilde{d}}_{t+\alpha }\mid \le k$. It follows that ${\sum }_{t=t_{\ell }}^{t_r-1}\mid d_t-{\tilde{d}}_{t+\alpha }\mid \le k$. We now show that $\alpha$ can be recognized as the unique “shift” $s$ in a given interval that ensures ${\tilde{d}}_{t+s}$ is sufficiently close to $d_t$.

Claim 4.For $s\in \left\{0,\text{…},2k-1\right\}$, ${\sum }_{t=t_{\ell }}^{t_r-1}\mid d_t-{\tilde{d}}_{t+s}\mid \le k$ if and only if $s=\alpha$.

By Claim 4, we see that $\alpha$ is the only value $s\in \left\{0,\text{…},2k-1\right\}$ satisfying ${\sum }_{t=t_{\ell }}^{t_r-1}\mid d_t-{\tilde{d}}_{t+s}\mid \le k$. As we have calculated ${\left(d_t\right)}_{t=t_{\ell }}^{t_r}$ and $\left({\tilde{d}}_t\right)$ from the cards, and we know $k$ as well, we are able to find the value $s\in \left\{0,\text{…},2k-1\right\}$ satisfying ${\sum }_{t=t_{\ell }}^{t_r-1}\mid d_t-{\tilde{d}}_{t+s}\mid \le k$, and hence identify $\alpha$. Once we have identified $\alpha$, we can then calculate $m=\tilde{m}-\alpha$, the number of edges in $G$. $\square$