Alternative proof for counting problem in graphs

Let $G$ and $H$ be graphs, let $\vec H$ be a fixed orientation of $H$.

Denote by $D(G,\vec H)$ the number of orientations of $G$ that contain a copy of $\vec H$ and denote by $D'(G,H)$ the number of spanning subgraphs of $G$ that contain a copy of $H$.

Claim: $D'(G,H) \leq D(G, \vec H)$.

Note: a spanning subgraph of a graph $G=(V,E)$ is a graph $G_X=(V,X)$, where $X \subseteq E$.

In [1] the claim is proven using some more general results involving set systems and shattering. Is there a simple, elementary (e.g. inductive) proof of the result?

[1] L.Kozma, S.Moran: Shattering, Graph Orientations, and Connectivity, 2012.

• Clearly isolated vertices are forbidden since adding $k$ more of them to $G$ would double the number of counted subgraphs $k$ times but not change the counted orientations. Jan 9, 2013 at 15:35
• No, by subgraph of G=(V,E) I meant a subgraph having vertex set V, so adding isolated vertices doesn't change the number of subgraphs. To be precise, I mean spanning subgraphs, i.e. subsets of E, just that I find spanning subgraph a bit ambiguous, but nevertheless, I changed to text to make it clearer. Jan 9, 2013 at 17:00
• Without that one could have $H$ a single edge and $G$ a single edge plus 3 isolated vertices. then $8=D'(G,H) \not \leq D(G, \vec H)=2.$ Jan 9, 2013 at 19:46
• Assuming the answer is yes, what would such a proof look like? How would it start? Perhaps a combinatorial injection is what you seek? Gerhard "Ask Me About Imaginary Proofs" Paseman, 2013.01.09 Jan 9, 2013 at 20:28
• @Gerhard: An explicit injective mapping between the two sets would be nice. Or maybe just an induction on the number of edges of G. Or perhaps something resembling contraction-deletion, where the two quantities would have the same recurrence but would differ in the base cases. Or something else entirely :) Jan 9, 2013 at 21:08

I think I have a proof. I take it kind of pedantically because I am a little suspicious that it looks both simple in ideas and convoluted in details, but see what you thnk . Following that are very preliminary comments on inductive proofs.

We think of graphs as sets of edges. I will change the notation slightly to have $D'(G,H)$ and $D( G, \vec H)$ denote the things they previously counted. So our goal is to show $|D'(G,H)| \le |D(G, \vec H)|.$

Given a subgraph $S$ of $G$ with a possible orientation, let $\operatorname{emb}(H,S)$ and $\operatorname{emb}(\vec H,\vec S)$ be the sets of embeddings of of $H$ in $S$ which ignore and respect the orientations. The key to my proof is the observation $|\operatorname{emb}(H,S)| \ge |\operatorname{emb}(\vec H,\vec S)|$ so that , when both are positive, $$\frac{1}{|\operatorname{emb}(H,S)|} \le \frac{1}{|\operatorname{emb}(\vec H,\vec S)|}.$$

Consider the various triples $(\vec G,S,f) \in D(G, \vec H) \times D'(G,H) \times \operatorname{emb}(H,G).$ So each consists of an orientation of $G$, a distinguished subset $S$ (which inherits an orientation $\vec S$) and an embedding of $H$ into $G$. Call such a triple viable when the embedded copy of $H$ is inside $S$ and the orientation that it gets from $\vec G$ is the one specified in the problem. We will weight the viable triples in two ways so that they sum to the two quantities we wish to compare, one will depend only on the set $S$ and the other on both the set $S$ and the orientation $\vec G$.

First count the viable triples with various restrictions.

For each fixed $f \in \operatorname{emb}(H,G),$ The number of viable triples $(\cdot,\cdot,f)$ is $(2^{|G|-|H|})^2$ Because the $H$ edges already chosen are going to be in $S$ and already have their orientation in $\vec G$ determined. For each other edge we must decide both which orientation it will get and also if it will or will not be in $S$.

For each fixed subgraph $S \in D'(G,H)$, the number of viable triples $(\cdot,S,\cdot)$ is $|\operatorname{emb}(H,S)|2^{|G|-|H|}$ because we still need an embedding and then it remains to orient all the edges not already determined.

For a fixed orientation $\vec G \in D(G,\vec H)$ it is slightly more involved. If we also fix the embedding $f$ viably, then there are $2^{|G|-|H|}$ ways to pick all, some or none of the other edges for $S$. But if we fix $\vec G$ and $S$ then the number of compatible embeddings is $|\operatorname{emb}(\vec H,\vec S)|.$

So, if we want the sum to come to $|D'(G,H)|$ then each viable triple $(\vec G,S,f)$ should get the weight $\frac{1}{|\operatorname{emb}(H,S)|2^{|G|-|H|}}.$ However, if we want the weights to sum to $|D(G, \vec H)|,$ then each viable triple $(\vec G,S,f)$ should get the weight $\frac{1}{|\operatorname{emb}(\vec H,\vec S)|2^{|G|-|H|}}.$ As remarked above, this establishes $|D'(G,H)| \le |D(G, \vec H)|$ because the weights we sum have $\frac{1}{|\operatorname{emb}(H,S)|2^{|G|-|H|}} \le \frac{1}{|\operatorname{emb}(\vec H,\vec S)2^{|G|-|H|}}$

When $H$ is a single oriented edge we have $D'(G,H)=2^{|G|}-1$ because we can take $S$ to be any nonempty subset of edges. This is just one less than $D(G, \vec H)=2^{|G|}$ because all the orientations are fine. So this suggests one approach: Fix $G$ and then build $\vec H$ one oriented edge at a time.
Swapping roles, another approach is to fix $H$ and build $G$ starting at $H.$ Clearly $D'(H,H)=1$, we need all the edges. But $D(H,\vec H) \ge 1$ because there is certainly at least one viable orientaation. I suppose it depends on if $\vec H$ has any automorphisms.
Finally, in any case we can assume that every edge of $G$ is used in at least one embedding of $H$ into $G.$ Any other edge can be oriented either way and can be included or not in a possible subset. Accordingly, $D'(G,H)=2D'(\hat G,H)$ and $D(G,\vec H)=2D(\hat G,\vec H)$ where $\hat G$ is just $G$ with the useless edge removed.
• When you count the viable triples for a fixed embedding, shouldn't the count also depend on the number of isomorphic reorientations of $\vec H$? For example if both $G$ and $H$ consist of a single edge, the number of viable triples should be 2 (two orientations of G * one subset * one embedding), but the formula gives 1. Jan 10, 2013 at 15:04
• I think this will affect the second part as well, but not the third part. So the proof might still be correct, as we now need $k |emb(H,S)| 2^{|G|−|H|} \geq |emb(\vec H ,\vec S )| 2^{|G|−|H|}$, where $k \geq 1$. Is this correct? Jan 10, 2013 at 15:21
• You are correct, a single edge actually has $2|G|$ embeddings. I suppose that the embedding must say which vertices go to which (which also says which edge goes to which). However that is really only required when $H$ has one or more isolated edges. Otherwise, just the edge to edge map determines the vertex to vertex. So if $H$ consists of $k$ disjoint edges, then $| emb (H,H)|=k!2^k$. I'll think about it more. Jan 11, 2013 at 7:12
• Is it really just for $H$ with isolated edges? Say, $\vec H$ is a directed triangle, and $G$ is a triangle. Then also there are 2 viable triples. Jan 11, 2013 at 11:29
• For my (questionable) "proof" I am happy to give a vertex to vertex assignment but I do think that an edge embedding of a triangle in another graph uniquely determines the vertex assignment. I do have to think over my answer, but for $\vec H$ a directed triangle and $G$ a triangle, $D'(G,H)=1$ and there are $6$ embeddings of $H$ into that unique $S$. Also, $D(G,\vec H)=2$ or $3$ or $3$ depending on $\vec H.$ The number of triples is $\sum_{\vec G}emb(\vec H,\vec G)2^{|G|-|H|}=3\ 2^0+3\ 2^0=6$ in the first case and $1\ 2^0+1\ 2^0+1\ 2^0=3$ in the others. Jan 11, 2013 at 14:36