\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Craig A. Sloss}
%
%
\medskip
\noindent
%
%
{\bf The Induced Subgraph Order on Unlabelled Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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\geq 0}$ 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.
\bye