The induced subgraph order on unlabelled graphs (Q870042)

Summary: A differential poset is a partially ordered set with raising and lowering operators \(U\) and \(D\) which satisfy the commutation relation \(DU-UD=rI\) for some constant \(r\). This notion may be generalized to deal with the case in which there exist sequences of constants \(\{q_n\}_{n\geq0}\) and \(\{r_n\}_{n\geq 0}\) such that for any poset element \(x\) of rank \(n\), \(DU(x) = q_n UD(x) + r_nx\). Here, we introduce natural raising and lowering operators such that the set of unlabelled graphs, ordered by \(G\leq H\) if and only if \(G\) is isomorphic to an induced subgraph of \(H\), is a generalized differential poset with \(q_n=2\) and \(r_n = 2^n\). This allows one to apply a number of enumerative results regarding walk enumeration to the poset of induced subgraphs.