5
$\begingroup$

Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)

A subgraph isomorphism $\varphi$ from $G$ to $H$ is a graph isomorphism from some subgraph of $G$ to $H$. In other words, it is a bijective function $\varphi:V\to V$ (where $V$ is the vertex set of $G$) such that if $(\varphi(u),\varphi(v))$ is an edge in $H$, then $(u,v)$ is an edge in $G$.

Let $\Phi$ denote the set of all subgraph isomorphisms from $G$ to $H$. For a vertex $v \in V$, define the out-expansion of $u$ in $\Phi$ to be $|\{\varphi(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that $v$ can be mapped to, under some subgraph isomorphism), and the in-expansion of $v$ to be $|\{\varphi^{-1}(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that can map to $v$, under some subgraph isomorphism).

Consider the following proposition:

If every vertex has out-expansion $\ge k$, then every vertex has in-expansion $\ge k$.

Is this proposition true for all $G,H$?

I haven't been able to find any reason why it should be true. (For instance, I don't think $\Phi$ is closed under inversion: $\varphi \in \Phi$ doesn't seem to imply $\varphi^{-1} \in \Phi$.) However, playing with a few small examples, I haven't found a counter-example yet. That said, I only tried a few simple examples, so it's possible that more trial-and-error might give a better sense. But I thought I'd check whether anyone here has any suggestions for how to answer this.

Motivation: this problem arises in the security analysis of a proposed scheme for obfuscating/protecting circuits. The graph represents the circuit (actually, they use a colored graph, where each vertex is given a color, and the isomorphism has to respect the color scheme; but that can probably be ignored, for simplicity), and subgraph isomorphisms represent different possible ways that the circuit might have been hidden/obfuscated.

$\endgroup$
3
$\begingroup$

Yes: if each vertex maps to at least $k$ vertices by a set $S$ of bijections of a finite set, then there are at least $k$ vertices that map to each vertex by these bijections.

In fact, the in-spectrum (the sequence of in-expansions) is a permutation of the out-spectrum (the sequence of out-expansions). Note that $f$ is a bijection iff $f^{-1}$ is a bijection. Hence one can define a bijection between $S$ and $S^{-1} = \{f^{-1}\mid f\in S\}\ $ so the spectra are then permutations of each other.


An aside: this doesn't necessarily hold for bijections of infinite sets. Let $f_i$ be the map $1\mapsto i, 2\mapsto 1, 3\mapsto 2, \dots, i \mapsto i-1, i+1\mapsto i+1,\dots$, and take the collection of all these maps. Then the out-spectrum is $(\omega,2,2,\dots)$ while the in-spectrum is $(2,2,2,\dots)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.