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.
Subgraph isomorphisms: does large out-expansion imply large in-expansion?
graph theory;graphs;discrete mathematics;graph isomorphism
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)$.