Semi-Random Graphs, Robust Asymmetry, and Reconstruction

For a fixed graph $G_0$ and $p\in (0,1)$, consider the random graph $G$ given by independently flipping each edge/nonedge in $G_0$ with independent probability $p$. Note that this is equivalent to independently including edges that do not appear in $G_0$ with probability $p$ and edges that do appear in $G_0$ with probability $1-p$. Moreover, if $p\in O(1/n^2)$, $n$ can be taken sufficiently large so that $G=G_0$ with probability $\mathrm{\Omega }(1)$. This observation suggests one possible measure of progress towards the full conjecture: the smallest $p(n)$ such that graphs perturbed in the manner remain reconstructible asymptotically.

We encapsulate this smoothed perspective by considering a generalization of $𝒢(n,p)$ which allows for non-uniform edges probabilities. Let $n\in \mathbb{N}$ and $N=\left(\genfrac{}{}{0pt}{}{n}{2}\right)$. For a vertex set $V$, $|V|=n$, we fix an arbitrary indexing $\pi :V^{(2)}\leftrightarrow [N]$. For $\text{p}={(p_i)}_i\in {[0,1]}^N$, we denote by $𝒢(n,\text{p})$ the distribution over graphs on $V$ such that each vertex pair $e\in V^{(2)}$ is included as an edge with independent probability $p_{\pi (e)}$. Equivalently, $𝒢(n,\text{p})={⨂}_1^N\mathrm{Ber}(p_i)$. Of course, we will consider probabilities that vary with $n$; in full generality, we let $\text{p}:\mathbb{N}\to {[0,1]}^{\ast }$ such that $\text{p}(n)\in {[0,1]}^N$. In this case, we denote by $𝒢(n,\text{p})$ the distribution given by including an edge $e$ with probability equal to the $\pi (e)$th coordinate of $\text{p}(n)$.

Employing the semi-random perspective, we have some flexibility. For a graph $G=(V,E)$ and subset $S\subset V^{(2)}$, we denote by $B_S(G)$ the family of graphs generated by adding/removing any number of vertex pairs from $S$ in $G$. That is,

For $r\in \mathbb{N}$, we denote by $B_r(G)$ the family of graphs generated by adding/removing at most $r$ vertex pairs anywhere in $G$,

Intuitively, should we allow an adversary to edit a limited number of edges anywhere in $G$, we hope that all graphs in $B_{\epsilon }(G)$ be reconstructible. Should we constrain an adversary’s changes to a (possibly random) set of pairs $S$, we hope that all graphs in $B_S(G)$ be reconstructible. To start, we find it most fruitful to uniformly draw a subset $S\subset V^{(2)}$ of order $\epsilon =\epsilon (n)$ and examine the behavior of $B_S(G)$. Note that for appropriate $\epsilon \in \mathrm{\Omega }(n^2\log (n))$, an asymptotic reconstructibility result for $B_S(G)$ would suffice to prove the Reconstruction Conjecture for sufficiently large $n$ (see Appendix C). This observation furnishes another measure of progress towards the full conjecture: the largest $\epsilon (n)$ such that all graphs in $B_S(G)$ remain reconstructible asymptotically. Loosely, this formalization of the semi-random model can be seen as, instead of uniformly widening the hypercube bound on $\text{p}\in {[0,1]}^N$ (as is our objective under the smoothed interpretation), allowing a random (or adversarially chosen) subset of the entries in this tuple to be arbitrary. Studying these settings, we give strengthened and refined forms of existing probabilistic graph reconstruction results. We summarize our contributions as follows.

In the present work, we are concerned with the Vertex Reconstruction Conjecture. Graph families proven to be reconstructible in this setting include regular graphs, disconnected graphs, and trees [18]. More recently, Farhadian [10] observed connections between the reconstructibility of a graph and the uniqueness and asymmetry of its large subgraphs. On the empirical front, McKay [21, 22] verified that all graphs up to 13 vertices are reconstructible. For an overview of standard results and alternative variants of the conjecture, see [6].

The probabilistic examination of graph reconstruction dates to Müller [23], who proved that for any $\alpha \in (0,1)$, almost all graphs are reconstructible from their multiset of subgraphs on $\frac{n}{2}(1+\alpha )$ vertices. Using an enumerative argument, Müller proved that for $G\sim 𝒢(n,1/2)$, it holds with probability $1-o(1)$ that all sufficiently large subgraphs of $G$ must be asymmetric and mutually non-isomorphic, a sufficient condition for reconstructibility. The seminal work of Bollobás [3] refined the analysis for $𝒢(n,p)$ with $p\in \mathrm{\Omega }(\log (n)/n)$, proving that asymptotically almost surely $G\sim 𝒢(n,p)$ is reconstructible from any three subgraphs on $n-1$ vertices. More recently, [28] used the asymmetry result of Müller to prove that for $\mathrm{\ell }\le \frac{n}{2}(1-\alpha )$, almost all graphs are reconstructible from some multiset of $\left(\genfrac{}{}{0pt}{}{\mathrm{\ell }+2}{2}\right)$ subgraphs on $n-\mathrm{\ell }$ vertices.

The literature on graph asymmetry is even more extensive. Erdős and Rényi [9] initiated the study of this notion by proving that almost all graphs are asymmetric. In particular, they proved that asymptotically almost surely, one must remove and add a total of at least $\frac{n}{2}(1-\alpha )$ edges to make $G\sim 𝒢(n,1/2)$ symmetric. In recent years, this result has joined the literature on property resilience [29, 12, 5]. More generally, it is folklore that for $1-p,p\ge \log (n)/n$, one must asymptotically almost surely add and remove at least $(2+o(1))np(1-p)$ edges somewhere in $G\sim 𝒢(n,p)$ to achieve symmetry. Kim et al. [19] refined this result by proving that for the same range of $p$, one must asymptotically almost surely add and remove at least $(1+o(1))np(1-p)$ edges adjacent to a single vertex. A number of works have also studied asymmetry in different graph distributions [19, 2, 20, 26]. The work of [26] comes closest to ours in terminology; examining hardness in a robust variant of the Graph Isomorphism problem, they prove that the uniform distribution over graphs on $n$ vertices and $m\in \mathrm{\Omega }(n)$ edges satisfies a strengthened notion of global asymmetry that decays with $n$ if $m$ is super-linear.

Also related to the sensitivity of graph asymmetry is the work of [7] and [15]. These works examine changes in the graph automorphism group under addition and deletion of carefully chosen edges. [7] take on a dual perspective to that of Erdős and Rényi [9], studying the minimum number of edges one must add and delete in order to make a graph asymmetric. [15] prove that for any two finite groups, there exists a graph from which one can remove a vertex so that the automorphism group passes between these groups. This result can be seen as a barrier to proving the Reconstruction Conjecture via characterization of subgraph symmetries.

For $r\in ℝ$, we let $\lfloor r\rfloor$ denote the greatest integer $m\le r$. For $m\in \mathbb{N}$, we let $[m]=\{1,2,\mathrm{\dots },m\}$. For a finite set $U$ and natural numbers $k\le |U|$, $\mathrm{\ell }\le \left(\genfrac{}{}{0pt}{}{|U|}{k}\right)$, we let $U^{(k)}$ denote the set of all $k$-element subsets of $U$, and $U^{(k,\mathrm{\ell })}=U^{(k)(\mathrm{\ell })}$ denote the set of all $\mathrm{\ell }$-element subsets of $U^{(k)}$. For a random variable $X$ and event $E$, we let ${\mathbb{P}}_X$ denote the distribution of $X$ and $𝕀[E]$ denote the indicator of $E$. For a finite set $U$, we let $𝒰(U)$ denote the uniform distribution over $U$. For any distribution $𝒟$ supported on $U$ and $k\in \mathbb{N}$, we let ${𝒟}^{\otimes k}$ denote the $k$-fold product of $𝒟$, supported on $U^k$.

We direct our attention exclusively to finite undirected graphs; for an introduction to standard notation, see [4, 5]. For a graph $G=(V,E)$, we denote $v(G)=|V|$ and $e(G)=|E|$. For a set of vertices $U\subseteq V$, $G[U]$ denotes the induced subgraph of $G$ on $U$, i.e., $G[U]=(U,\{e\in E:e\subset U\})$. For a vertex $v\in V$, we let $G-v=G[V\setminus \{v\}]$. More generally, for any subset $U\subset V$, we let $G-U=G[V\setminus U]$. Analogously, for any subset $F\subset V^{(2)}$, we let $G+F=(V,E\cup F)$ and $G-F=(V,E\setminus F)$. Henceforth, for concision, we refer to induced subgraphs simply as subgraphs.

A graph isomorphism $\phi :G\stackrel{\cong }{\to }H$ is a bijection $\phi :V(G)\to V(H)$ such that $xy\in E(G)$ if and only if $\phi (x)\phi (y)\in E(H)$. If there exists an isomorphism $\phi :G\stackrel{\cong }{\to }H$, we say that $G$ and $H$ are isomorphic and write $G\cong H$. A graph automorphism on $G$ is an isomorphism $\phi :G\stackrel{\cong }{\to }G$. We let $\mathrm{Aut}G$ denote the set of automorphisms on $G$. The identity is always an automorphism; if no other automorphism exists, we call $G$ asymmetric. If $G$ is not asymmetric, we call it symmetric. We say that two vertices $x,y\in V(G)$ are similar, and write $x\sim y$, if there exists $\phi \in \mathrm{Aut}G$ such that $\phi (x)=y$. We say that a set of vertices $U\subset V(G)$ is fixed in $G$ if $\phi (U)=U$ for all $\phi \in \mathrm{Aut}G$. We say a subgraph of $G$ is unique if it is isomorphic to no other subgraph of $G$.

A hypomorphism $\sigma :G\stackrel{\sim }{\to }H$ is a bijection $\sigma :V(G)\to V(H)$ such that $G-v\cong H-\sigma (v)$ for all $v\in V(G)$. If there exists a hypomorphism $\sigma :G\stackrel{\sim }{\to }H$, we say that $G$ and $H$ are hypomorphic and write $G\sim H$. Naturally, $G\cong H$ implies $G\sim H$. The Reconstruction Conjecture asserts the converse, for graphs on at least three vertices.

In general, we say that a graph $G$ is reconstructible if whenever $G\sim H$, it holds that $G\cong H$. A family of graphs $𝒞$ is reconstructible if all $G\in 𝒞$ are reconstructible. We let ${\Re }_n$ denote the family of reconstructible graphs on $n$ vertices, and ${\overline{\Re }}_n$ the family of nonreconstructible graphs on $n$ vertices. A classical tool in graph reconstruction is Kelly’s lemma, which we state below alongside two relevant facts.

Asymmetry properties are commonly leveraged in probabilistic reconstruction arguments. Namely, such arguments often invoke the asymmetry of all sufficiently large (induced) subgraphs of the underlying random graph. The dependence of this technique upon all subgraphs enjoying this property can occasionally be avoided by instead assuming the uniqueness of certain subgraphs. Farhadian [10] exploited this approach, demonstrating that all graphs containing a unique and asymmetric subgraph on $n-2$ vertices are reconstructible. As our first lemma, we present a mild generalization of this result, which admits a constructive proof.

Let us begin by articulating subgraph uniqueness properties that will play a central role in our forthcoming results. Recall that for a graph $G=(V,E)$ and subset $S\subset V^{(2)}$, $B_S(G)$ denotes the set of graphs generated by adding/removing any number of vertex pairs from $S$ in $G$,

Informally, $E_{\delta }(G)$ records the condition that all subgraphs of $G$ on $n$ vertices are asymmetric and mutually non-isomorphic, while $E_{\delta }(G,S)$ records whether this is true even when one is permitted to add/remove any vertex pairs in $S$ from $G$. Note that the negation of $E_{\delta }(G,S)$ is monotonic in $S$. We are now equipped to state our primary lemma.

Here and in the remaining results, it makes no difference whether we draw $\epsilon =\epsilon (n)$ or $\epsilon =\epsilon (n+\delta )$ pairs. For simplicity in the proofs, however, we take $\epsilon =\epsilon (n)$ and require that its image be contained in $\mathbb{N}$. A crucial difference between the cases where $\beta =o(1)$ and $\beta =\mathrm{\Theta }(1)$ is the adaptivity of our constants. In the former case, we can choose $\alpha$ to scale the convergence rate by any $\rho$ of our choosing. This property will be useful when we examine downstream implications.

After some simple observations on the front end, our proof of Lemma 12 closely follows that of [3]. Roughly, we upper bounds the probability of any single isomorphism $\phi$ by the probability that its orbits on $V^{(2)}$ consist entirely of edges or entirely of nonedges. We find that we can fit in additional cross-terms that account for the edits contributed by $S$. Here and in the sequel, proofs for $\beta \in \mathrm{\Theta }(1)$ are entirely similar to those for $\beta \in o(1)$; we leave such proofs to Appendix B.