Oxford Mathematician Carla Groenland talks about her and Oxford colleagues' work on graph reconstruction.
A graph $G$ consists of a set of vertices $V(G)$ and a set of edges $E(G)$ which may connect two (distinct) vertices. (There are no self-loops or multiple edges.)
A very basic question about graphs is: Is a graph determined by its induced subgraphs? For a graph $G$ and a vertex $v$, a card of the graph is an induced subgraph $G-v$ obtained by removing the vertex $v$ and all adjacent edges. The deck of the graph is the collection of cards $\{G-v:v\in V(G)\}$, allowing multiples. An example of a deck of card is given below.
Below the cards, we see how the cards can be obtained by removing vertices from a single graph, removing one at a time and removing each vertex exactly once. Can two non-isomorphic graphs have the same deck of cards? Yes, if the graphs have two vertices.
If we see a single vertex twice, then we know the original graph had two vertices but there is no way for us to know whether there is an edge between them.
More than 60 years ago, Kelly and Ulam made the beautiful conjecture that if two graphs on at least three vertices have the same deck, they must be isomorphic. In 1977, Bondy and Hemminger wrote the following about this conjecture:
"The Reconstruction Conjecture is generally regarded as one of the foremost unsolved problems in graph theory. Indeed, Harary (1969) has even classified it as a "graphical disease'' because of its contagious nature. According to reliable sources, it was discovered in Wisconsin in 1941 by Kelly and Ulam, and claimed its first victim (P. J. Kelly) in 1942. There are now more than sixty recorded cases, and relapses occur frequently (this article being a case in point)."
There are many subtleties in the problem which might not be apparent at first sight; for example, if two vertices $u$ and $v$ have the same card (i.e. $G-u\cong G-v$) then they are not necessarily "similar'' in the graph, that is, there does not necessarily exist a graph automorphism mapping $u$ to $v$.
Rather than reconstructing the entire graph, can we at least read off some information about the graph? If a graph has vertices $v_1,\dots,v_n$ then \[ \sum_{i=1}^n |E(G-v_i)|=(n-2)|E(G)| \] since each edge appears in all cards except for the two corresponding to vertices it is adjacent to. So we can read off the number of edges of the graph (the size) if we are given a full deck of cards. What if we have only access to a subset of the cards? In Size reconstructibility of graphs, Alex Scott, Hannah Guggiari and I describe a way to reconstruct the size of the graph if at most $\frac1{20}\sqrt{n}$ cards are missing from the deck (for $n$ large). The best previous result in this direction was the case in which two cards are missing.
Our proof works as follows:
* We first note that if we have been given the cards $G-v_1,\dots,G-v_{n-k}$, we can still compute \[ \widetilde{|E(G)|}=\frac{\sum_{i=1}^{n-k} |E(G-v_i)|}{n-2-k}\approx|E(G)| \] which is an (over)estimate on the number of edges.
* The degree $d(v)$ of a vertex is the number of edges adjacent to it. Note that on the card $G-v$, exactly the edges adjacent to $v$ are missing. Hence $|E(G)|-|E(G-v)|=d(v)$. We will try to approximate the degree sequence $(d_t)$, where $d_t$ gives the number of vertices of degree $t$, in two different ways.
* Firstly, using our estimate on the number of edges, we can still approximate the degree of the vertices of the cards that have been given: \[ \widetilde{d(v)}=\widetilde{|E(G)|}-|E(G-v)|.\] Since we overestimate the number of edges, we also overestimate $d(v)$ for every vertex, but always by the same amount $\alpha = \widetilde{|E(G)|}-|E(G)|.$ This means our approximated degree sequence $(\widetilde{d}_t)$ is the actual degree sequence $(d_t),$ but shifted to the right, and moreover some values have been underestimated (since some of the cards are missing). If we could recover the shift $\alpha,$ we could find $|E(G)|$ since we know $\widetilde{|E(G)|}.$
* Secondly, we discover many small values $d_t$ exactly. We use these to either reconstruct the entire degree sequence (then we can read off the number of edges from this) or discover some large values. Suppose that we find a segment as in the picture below: one large value, and to one side of it a bunch of known values, many of which are small. We "match up'' the known values to various shifts of $(\widetilde{d}_t).$ For the correct shift, the error will be small, whereas for any other shift the error is lower bounded by the difference between large and small in the figure below. This allows us to recover $\alpha$ and then the number of edges.
Some interesting open problems include:
* The original graph reconstruction conjecture, for which the edge variant is also unknown. (The directed graph, infinite graph and hypergraph analogues are false.) This is also unknown for "nice'' graph classes such as bipartite graphs or planar graphs.
* Improving our result beyond $\sqrt{n}$ or extending it to recovering different information about the graph, such as the degree sequence or the number of triangles.