A Chromatic Symmetric Function in Noncommuting Variables.
Stanley (i>Advances in Math. 111, 1995, 166194) associated with a graph i>G a symmetric function i>XG which reduces to i>G's chromatic polynomial {\cal X}_{G}(n) under a certain specialization of variables. He then proved various theorems generalizing results about {\cal X}_{G}(n), as well as new ones that cannot be interpreted on the level of the chromatic polynomial. Unfortunately, i>XG does not satisfy a Deletion-Contraction Law which makes it difficult to apply the useful technique of induction. We introduce a symmetric function i>YG in noncommuting variables which does have such a law and specializes to i>XG when the variables are allowed to commute. This permits us to further generalize some of Stanley's theorems and prove them in a uniform and straightforward manner. Furthermore, we make some progress on the (3 1)-free Conjecture of Stanley and Stembridge (i>J. Combin Theory (i>A) J. 62, 1993, 261279).
Introduction
Let G be a finite graph with verticies and edge set
E(G). We permit our graphs to have loops and multiple edges. Let XG (n) be the
chromatic polynomial of G, i.e., the number of proper colorings ng.
(Proper means that vw 2 E implies -(v) 6= -(w).)
In [12, 13], R. P. Stanley introduced a symmetric function, XG , which generalizes
XG (n) as follows. Let be a countably infinite set of commuting
indeterminates. Now define
where the sum ranges over all proper colorings, :g. It is clear
from the definition that XG is a symmetric function, since permuting the colors of
a proper coloring leaves it proper, and is homogeneous of degree j. Also the
specialization XG (1 n ) obtained by setting x
Stanley used XG to generalize various results about the chromatic polynomial as
well as proving new theorems that only apply to the symmetric function. However,
there is a problem when trying to find a deletion-contraction law for XG . To see what
goes wrong, suppose that for e 2 E we let G n e and G=e denote G with the e deleted
and contracted, respectively. Then XG and XGne are homogeneous of degree d while
X G=e is homogeneous of degree d \Gamma 1 so there can be no linear relation involving all
three. We should note that Noble and Welsh [10] have a deletion contraction method
for computing XG equivalent to [12, Theorem 2.5]. However, it only works in the
larger category of vertex-weighted graphs and only for the expansion of XG in terms
of the power sum symmetric functions. Since we are interested in other bases as well,
we take a different approach.
In this paper we define an analogue, YG , of XG which is a symmetric function
in noncommuting variables. (Note that these symmetric functions are different from
the noncommutative symmetric functions studied by Gelfand and others, see [7] for
example.) The reason for not letting the variables commute is so that we can keep
track of the color which - assigns to each vertex. This permits us to prove a Deletion-
Contraction Theorem for YG and use it to derive generalizations of results about XG
in a straightforward manner by induction, as well as make progress on a conjecture.
The rest of this paper is organized as follows. In the next section we begin with
some basic background about symmetric functions in noncommuting variables (see
also [5]). In Section 3 we define YG and derive some of its basic properties, including
the Deletion-Contraction Law. Connections with acyclic orientations are explored in
Section 4. The next three sections are devoted to making some progress on the (3+1)-
free Conjecture of Stanley and Stembridge [14]. Finally we end with some comments
and open questions.
Symmetric functions in noncommuting variables
Our noncommutative symmetric functions will be indexed by elements of the partition
lattice. We let \Pi d denote the lattice of set partitions - of f1;
by refinement. We write a block of -. The
(greatest lower bound) of the elements - and oe is denoted by - oe. We use - 0
to denote the unique minimal element, and - 1 for the unique maximal element.
For - 2 \Pi d we define -) to be the integer partition of d whose parts are the
block sizes of -. Also, if need the constants
We now introduce the vector space for our symmetric functions. Let fx 1
be a set of noncommuting variables. We define the monomial symmetric functions,
where the sum is over all sequences positive integers such that
if and only if j and k are in the same block of -. For example, we get
for the partition
From the definition it is easy to see that letting the x i commute transforms m -
into j-jm -) , a multiple of the ordinary monomial symmetric function. The monomial
are linearly independent over C , and we
call their span the algebra of symmetric functions in noncommuting variables.
There are two other bases of this algebra that will interest us. One of them consists
of the power sum symmetric functions given by
where the second sum is over all positive integer sequences
if j and k are both in the same block of -. The other basis contains the elementary
symmetric functions defined by
where the second sum is over all sequences positive integers such that
are both in the same block of -. As an illustration of these definitions,
we see that
and that
Allowing the variables to commute transforms p - into p -) and e - into -!e -) . We
may also use these definitions to derive the change-of-basis formulae found in the
appendix of Doubilet's paper [3] which show
where -; oe) is the M-obius function of \Pi n .
It should be clear that these functions are symmetric in the usual sense, i.e., they
are invariant under the usual symmetric group action on the variables. However, it will
be useful to define a new action of the symmetric group on the symmetric functions
in noncommuting variables which permutes the positions of the variables. For
we define
where the action of ffi 2 S d on a set partition of [d] is the obvious one acting on
the elements of the blocks. It follows that for any ffi this action induces a vector
space isomorphism, since it merely produces a permutation of the basis elements.
Alternatively we can consider this action to be defined on the monomials so that
and extend linearly.
Utilizing the first characterization of this action, it follows straight from definitions
(2) and (3) that
3 YG , The noncommutative version
We begin by defining our main object of study, YG .
Definition 3.1 For any graph G with vertices labeled in a fixed order,
define
where again the sum is over all proper colorings - of G, but the x i are now noncommuting
variables.
As an example, for P 3 , the path on three vertices with edge set fv 1
can calculate
Note that if G has loops then this sum is empty and
depends not only on G, but also on the labeling of its vertices.
In this section we will prove some results about the expansion of YG in various
bases for the symmetric functions in noncommuting varaibles and show that it satisfies
a Deletion-Contraction Recursion. To obtain the expansion in terms of monomial
symmetric functions, note that any partition P of V induces a set partition -(P ) of
[d] corresponding to the subscripts of the vertices. A partition P of V is stable if any
two adjacent vertices are in different blocks of P . (If G has a loop, there are no stable
partitions.) The next result follows directly from the definitions.
Proposition 3.2 We have
where the sum is over all stable partitions, P , of V .
In order to show that YG satisfies a Deletion-Contraction Recurrence it is necessary
to have a distinguished edge. Most of the time we will want this edge to be between
the last two vertices in the fixed order, but to permit an arbitrary edge choice we will
define an action of the symmetric group S d on a graph. For all ffi 2 S d we let ffi act on
the vertices of G by ffi(v This creates an action on graphs given by
where H is just a relabeling of G.
Proposition 3.3 (Relabeling Proposition) For any graph G, we have
where the vertex order used in both YG and Y ffi(G) .
Proof. Let We note that the action of ffi produces a bijection between
the stable partitions of G and H. Utilizing the previous proposition and denoting the
stable partitions of G and H by PG and PH , respectively, we have
Using the Relabeling Proposition allows us, without loss of generality, to choose a
labeling of G with the distinguished edge for deletion-contraction being d . It
is this edge for which we will derive the basic recurrence for YG .
Definition 3.4 We define an operation called induction, ", on the monomial
, by
and extend this operation linearly.
Note that this function takes a symmetric function in noncommuting variables which
is homogeneous of degree d \Gamma 1 to one which is homogeneous of degree d. Context
will make it clear whether the word induction refers to this operation or to the proof
technique.
Sometimes we will also need to use induction on an edge l so we extend
the definition as follows. For define an operation" l
k on symmetric functions in
noncommuting variables which simply repeats the variable in the k th position again
in the l th . That is, for a monomial x
, define
and extend linearly.
Provided G has an edge which is not a loop, we will usually start by choosing a
labeling such that We also note here that if there is no such edge, then
ae
if G has a loop, (8)
where K d is the completely disconnected graph on d vertices. We note that contracting
an edge e can create multiple edges (if there are vertices adjacent to both of e's
or loops (if e is part of a multiple edge), while contracting a loop deletes
it.
Proposition 3.5 (Deletion-Contraction Proposition) For
where the contraction of labeled v d\Gamma1 .
Proof. The proof is very similar to that of the Deletion-Contraction Property for
XG . We consider the proper colorings of G n e, which can be split disjointly into two
types:
1. proper colorings of G n e with vertices v d\Gamma1 and v d different colors;
2. proper colorings of G n e with vertices v d\Gamma1 and v d the same color.
Those of the first type clearly correspond to proper colorings of G. If - is a coloring
of G n e of the second type then (since the vertices v d\Gamma1 and v d are the same color) we
have
where ~ - is a proper coloring of G=e. Thus we have
We note that if e is a repeated edge, then the proper colorings of G n e are exactly
the same as those of G. The fact that there are no proper colorings of the second
type corresponds to the fact that G=e has at least one loop, and so it has no proper
colorings. Also note that because of our conventions for contraction we always have
cardinality.
It is easy to see how the operation of induction affects the monomial and power
sum symmetric functions. For denote the partition -
with d inserted into the block containing d \Gamma 1. From equations (1) and (2) it is easy
to see that
With this notation we can now provide an example of the Deletion-Contraction Proposition
for the vertices are labeled sequentially, and the distinguished edge is
It is not difficult to compute
This gives us
which agrees with our previous calculation.
We may use the Deletion-Contraction Proposition to provide inductive proofs for
noncommutative analogues of some results of Stanley [12].
Theorem 3.6 For any graph G,
where -(S) denotes the partition of [d] associated with the vertex partition for the
connected components of the spanning subgraph of G induced by S.
Proof. We induct on the number of non-loops in E. If E consists only of n loops,
for n - 0, then for all S ' E(G), we will have
ae p 1=2=:::=d if
This agrees with equation (8).
if G has edges which are not loops, we use the Relabeling Proposition to
obtain a labeling for G with . From the Deletion-Contraction Proposition
we know that by induction
~
It should be clear that
Hence it suffices to show that
~
To do so, we define a map \Theta : f ~
Then, because of our conventions for contraction, \Theta is a bijection. Clearly
-( ~
". Furthermore
and this completes the proof.
By letting the x i commute, we get Stanley's Theorem 2.5 [12] as a corollary. Another
result which we can obtain by this method is Stanley's generalization of Whit-
ney's Broken Circuit Theorem.
A circuit is a closed walk, distinct vertices and edges. Note
that since we permit loops and multiple edges, we can have 2. If we fix a
total order on E(G), a broken circuit is a circuit with its largest edge (with respect to
the total order) removed. Let BG denote the broken circuit complex of G, which is the
set of all S ' E(G) which do not contain a broken circuit. Whitney's Broken Circuit
Theorem states that the chromatic polynomial of a graph can be determined from its
broken circuit complex. Before we prove our version of this theorem, however, we will
need the following lemma, which appeared in the work of Blass and Sagan [1].
Lemma 3.7 For any non-loop e, there is a bijection between BG and BGne [ B G=e
given by
ae ~
~
where we take e to be the first edge of G in the total order on the edges .
Using this lemma, we can now obtain a characterization of YG in terms of the
broken circuit complex of G for any fixed total ordering on the edges.
Theorem 3.8 We have
where -(S) is as in Theorem 3.6.
Proof. We again induct on the number of non-loops in E(G). If the edge set
consists only of n loops, it should be clear that for n ? 0 we will have every edge
being a circuit, and so the empty set is a broken circuit. Thus we have
ae P
which matches equation (8).
For a non-loop, we consider apply
induction. From Lemma 3.7 and arguments as in Proposition 3.6, we have
and X
~
which gives the result.
orientations
An orientation of G is a digraph obtained by assigning a direction to each of its
edges. The orientation is acyclic if it contains no circuits. A sink of an orientation
is a vertex v 0 such that every edge of G containing it is oriented towards v 0 . There
are some interesting results which relate the chromatic polynomial of a graph to the
number of acyclic orientations of the graph and the sinks of these orientations. The
one which is the main motivation for this section is the following theorem of Greene
and Zaszlavsky [8]. To state it, we adopt the convention that the coefficient of n i in
XG (n) is a i .
Theorem 4.1 For any fixed vertex v 0 , the number of acyclic orientations of G with
a unique sink at v 0 is ja 1 j.
The original proof of this theorem uses the theory of hyperplane arrangements.
For elementary bijective proofs, see [6]. Stanley [12] has a related result.
Theorem 4.2 If
then the number of acyclic orientations of G with j
sinks is given by
We can prove an analogue of this theorem in the noncommutative setting by using
techniques similar to his, but have not been able to do so using induction. We can,
however, inductively demonstrate a related result which, unlike Theorem 4.2 implies
Theorem 4.1. For this result we need a lemma from [6]. To state it, we denote the set
of acyclic orientations of G by A(G), and the set of acyclic orientations of G with a
unique sink at v 0 by A(G; v 0 ). For completeness, we provide a proof.
Lemma 4.3 For any fixed vertex v 0 , and any edge
ae
is a bijection between A(G; the vertex of G=e
formed by contracting e is labeled v 0 .
Proof. We must first show that this map is well-defined, i.e., that in both cases we
obtain an acyclic orientation with unique sink at v 0 . This is true in the first case by
definition. In case two, where D n
must be true that D n e has
sinks both at u and at v 0 (since deleting a directed edge of D will neither disturb the
acyclicity of the orientation nor cause the sink at v 0 to be lost). Since u and v 0 are
the only sinks in D nuv 0 the contraction must have a unique sink at v 0 , and there will
be no cycles formed. Thus the orientation D=e will be in A(G=e; v 0 ) and this map is
well-defined.
To see that this is a bijection, we exhibit the inverse. This is obtained by simply
orienting all edges of G as in D n uv 0 or D=uv 0 as appropriate, and then adding in the
oriented edge \Gamma! uv 0 . Clearly this map is also well-defined.
We can now apply deletion-contraction to obtain a noncommutative version of
Theorem 4.1.
Theorem 4.4 Let
c - e - . Then for any fixed vertex, v 0 , the number of
acyclic orientations of G with a unique sink at v 0 is (d \Gamma 1)!c [d] .
Proof. We again induct on the number of non-loops in G. In the base case, if all the
edges of G are loops, then
ae e 1=2=:::=d if G has no edges
if G has loops.
or G has loops
oe
If G has non-loops, then by the Relabeling Proposition we may let
We know that ". Since we will only be interested in the leading
coefficient, let
a oe e oe ;
and
ce
c oe e oe
where - is the partial order on set partitions. By induction and Lemma 4.3, it is
enough to show that (d \Gamma
Utilizing the change-of-basis formulae (6) and (7) as well as the fact that for - 2
\Pi d\Gamma1 we have p - "= p -+(d) , we obtain
-oe+(d)
With this formula, we compute the coefficient of e [d] from Y G=e ". The only term which
contributes comes from ce [d\Gamma1] ", which gives us
ce
-oe+(d)
\Gammac
Thus, from we have that
which completes the proof.
This result implies Theorem 4.1 since under the specialization x
Y
polynomial is divisible by n 2 . Thus the
only summand contributing to the linear term of -G (n) is when and in that
case the coefficient has absolute value (d \Gamma 1)!c [d] .
The next corollary follows easily from the previous result.
Corollary 4.5 If
then the number of acyclic orientations of G with
one sink is d!c [d] .
5 Inducing e -
We now turn our attention to the expansion of YG in terms of the elementary symmetric
function basis. We recall that for any fixed - 2 \Pi d we use - to denote the
partition of [d formed by inserting the element (d into the block of - which
contains d. We will denote the block of - which contains d by B - . We also let -=d+ 1
be the partition of [d formed by adding the block fd + 1g to -.
It is necessary for us to understand the coefficients arising in e - " if we want to
understand the coefficients of YG which occur in its expansion in terms of the elementary
symmetric function basis. We have seen in equation (10) that the expression for
rather complicated. However, if the terms in the expression of e - " are grouped
properly, the coefficients in many of the groups will sum to zero. Specifically, we need
to combine the coefficients from set partitions which are of the same type (as integer
partitions), and whose block containing d+1 have the same size. Keeping track of the
size of the block containing d allow us to use deletion-contraction repeatedly.
To do this formally, we introduce a bit of notation. Suppose
a composition, i.e., an ordered integer partition. Let P (ff) be the set of all partitions
l of [d + 1] such that
2.
3.
The proper grouping for the terms of e - " is given by the following lemma.
Lemma 5.1 If e
1), and for any
composition ff, we have
Proof. Fix - 2 \Pi d . By equation (10)
Hence we may express
where for any fixed -
We first note that if -=d we have the
simple computation shows that c
Similarly, and we can easily compute
We now fix loss of generality
we can let be the blocks of - which are contained
in B -+(d+1) . For notational convenience, we will also let jB
Finally, let fi denote the partition obtained from - by merging the blocks of
- which contain d and d are in the same block of - .
Replacing oe equation (11), we see that
Now for any B ' [d + 1] we will consider the sets
The nonempty L(B) partition the interval according to the content of
the block containing fd; d + 1g and so we may express
To compute the inner sum, we need to consider the following 2 cases.
Case 1) For some k ? q strictly contained in a block of -
In this case, we see that each non-empty L(B) forms a non-trivial cross-section of a
product of partition lattices, and so for this case
Thus these - will not contribute to
Case 2) For all k ? q is a block of - 1). So, by abuse of notation,
we can write Also in this case, we can
assume q - 0, since we have already computed this sum when - 1). Then
we will showjBj \Gamma 1
Indeed, it is easy to see that if and so this part
is clear. Also, if
again and
Otherwise, L(B) again forms a non-trivial cross-section
of a product of partition lattices, and again gives us no net contribution to the
sum.
We notice that since fd; d B, the second case in (12) will only occur if
Adding up all these contributing terms gives us
In order to compute the sum over all - 2 P (ff), it will be convenient to consider
all possible orderings for the block of - containing d. So for
The sequence (B the ordered set partition - . We also define
ae
so
Thus we can see that
To obtain the sum over all - 2 P (ff) we need to sum over all P (ff; 2.
However, if we let k r be the number of blocks which have size r,
then in the sum over all P (ff; j), each - 2 P (ff) appears \Pi m+1
times. Combining
all this information, we see that
Hence it suffices to show that
Using the multinomial recurrence we have,
and so we need only show that
However, we may express
6 Some e-positivity results
We wish to use Lemma 5.1 to prove some positivity theorems about YG 's expansion
in the elementary symmetric function basis. If the coefficients of the elementary
symmetric functions in this expansion are all non-negative, then we say that YG is
e-positive. Unfortunately, even for some of the simplest graphs, YG is usually not
e\Gammapositive. The only graphs which are obviously e\Gammapositive are the complete graphs
on n vertices and their complements, for which we have
Even paths, with the vertices labeled sequentially, are not e\Gammapositive, for we can
compute that Y . However, in this example we can
see that while Y P 3
is not e\Gammapositive, if we identify all the terms having the same type
and the same size block containing 3, the sum will be non-negative for each of these
sets.
This observation along with the proof of the previous lemma inspires us to define
equivalence classes reflecting the sets P (ff). If the block of oe containing i is B oe;i and
the block of - containing i is B -;i , we define
and extend this definition so that
We let (-) and e (-) denote the equivalence classes of - and e - , respectively. Taking
formal sums of these equivalence classes allows us to write expressions such as
c oe e oe
(-)'\Pi d
c (-) e (-) where c
We will refer to this equivalence relation as congruence modulo i.
Using this notation, we have Y P3 j
We
will say that a labeled graph G (and similarly YG ) is (e)\Gammapositive if all the c (-) are
non-negative for some labeling of G and suitably chosen congruence. We notice that
the expansion of YG for a labeled graph may have all non-negative amalgamated
coefficients for congruence modulo i, but not for congruence modulo j. However, if
a different labeling for an (e)-positive graph is chosen, then we can always find a
corresponding congruence class to again see (e)-positivity. This should be clear from
the Relabeling Proposition.
We now turn our attention to showing that paths, cycles, and complete graphs
with one edge deleted are all (e)-positive. We begin with a few more preliminary
results about this congruence relation and how it affects our induction of e - .
We note that in the proof of Lemma 5.1, the roles played by the elements d and
d+1 are essentially interchangeable. That is, if we let ~
P (ff) be the set of all partitions
l of [d + 1] such that
2.
3.
and let ~
- be the partition - 2 \Pi d with d replaced by d then the same proof will
show that
Note that here ~ - + (d) is the partition obtained from ~
- by inserting the element d
into the block of ~ - containing This allows us to state a corollary in terms of the
congruence relationship just defined.
Corollary 6.1 If then for any - 2 \Pi d , we have
and
e (~-=d) \Gammab
The next lemma simply verifies that the induction operation respects the congruence
relation and follows immediately from equation (10) or the previous corollary.
Lemma 6.2 If e
From this we can extend induction to congruence classes in a well-defined manner:
In order to use induction to prove the (e)-positivity of a graph G, we will usually
try to delete a set of edges which will isolate either a single vertex or a complete graph
from G in the hope of obtaining a simpler (e)-positive graph. In order to see how this
procedure will affect YG , we use the following lemma.
Lemma 6.3 Given a graph, G on d vertices let where the vertices in Km
are labeled v d+1
c oe e oe , then
c oe e oe=d+1;d+2;:::;d+m .
Proof. From the labeling of H we have
c oe e oe e [m]
This result suggests we use the natural notation G=v d+1 for the graph G
U fv d+1 g.
We are now in a position to prove the (e)\Gammapositivity of paths.
Proposition 6.4 For all d - 1, Y P d
is (e)\Gammapositive.
Proof. We proceed by induction, having labeled P d so that the edge set is E(P d
and the proposition is clearly
true.
So we assume by induction that
Y P d
(-)'\Pi d
where c (- 0 for all (-) 2 \Pi d . From the Deletion-Contraction Recurrence applied to
6.1 and Lemma 6.3, we see that
(-)'\Pi d
c (-) e
(-)'\Pi d
c (-) e (-) "
(-)'\Pi d
c (-)
(-)'\Pi d
c (-)
Since we know that c (- 0, and jB - j - 1 for all - , this completes the induction
step and the proof.
In the commutative context we will say that the symmetric function XG is e-
positive if all the coefficients in the expansion of the elementary symmetric functions
are non-negative. Clearly (e)-positivity results for YG specialize to e-positivity results
for XG .
Corollary 6.5 X P d
is e\Gammapositive.
One would expect the (e)-expansions for cycles and paths to be related as is shown
by the next proposition. For labeling purposes, however, we first need a lemma which
follows easily from the Relabeling Proposition.
Lemma 6.6 If
Proposition 6.7 For all d - 1, if
Y P d
where we have labeled the graphs so E(P d and E(C d+1
g.
Proof. We proceed by induction on d. If
the proposition holds for
For the induction step, we assume that
and also that
Y C d j d
c (-) e
We notice that if does not have the standard labeling for
paths. But if we let
then we can use the
Deletion-Contraction Recurrence to get
However, since d + 1 is a fixed point for fl; Lemma 6.6 allows us to deduce that
Y C d+1
In the proof of Proposition 6.4 we saw that
Combining these two equations gives
Y C d+1
The demonstration of Proposition 6.4 also showed us that
Y P d
c (-)
c (-)
Applying Corollary 6.1 and Lemma 6.3 yields
Y P d
"j d+1
c (-)
c (-)
c (-)
c (-)
and
Y P d =v d+1
c (-)
c (-)
By the induction hypothesis,
Y C d
c (-) e
c (-)
Plugging these expressions for Y P d =v d+1
" into equation (13), grouping
the terms according to type, and simplifying gives
Y C d+1
c (-)
c (-)
This corresponds to the expression in equation (14) for Y P d
in exactly the desired
manner, and so we are done.
From the previous proposition and the fact that Y C 1
we get an immediate
corollaries.
Proposition 6.8 For all d - 1, Y C d
is (e)\Gammapositive.
Corollary 6.9 For all d - 1, X C d
is e\Gammapositive.
We are also able to use our recurrence to show the (e)-positivity of complete graphs
with one edge removed.
Proposition 6.10 For d - 2, if
YK d ne j d
Proof. Consider the complete graph K d and apply deletion-contraction to the edge
Together with Corollary 6.1 this will give us
Simplifying gives the result.
This also immediately specializes.
Corollary 6.11 For d - 2,
7 The (3+1)-free Conjecture
One of our original goals in setting up this inductive machinery was to make progress on
the (3+1)-free Conjecture of Stanley and Stembridge, which we now state. Let a+b
be the poset which is a disjoint union of an a-element chain and a b-element chain. The
poset P is said to be (a+b)-free if it contains no induced subposet isomorphic to a+b.
Let G(P ) denote the incomparability graph of P whose vertices are the elements of P
with an edge uv whenever u and v are incomparable in P . The (3+1)-free Conjecture
of Stanley and Stembridge [14] states:
Conjecture 7.1 If P is (3+1)-free, then XG(P ) is e-positive.
Gasharov [4] has demonstrated the weaker result that XG(P ) is s-positive, where s
refers to the Schur functions.
A subset of the (3+1)-free graphs is the class of indifference graphs. They are
characterized [13] as having vertices and edges
belong to some [k; l] 2 Cg,
where C is a collection of intervals [k; We note that without
loss of generality, we can assume no interval in the collection is properly contained
in any other. These correspond to incomparability graphs of posets which are both
(3+1)-free and (2+2)-free.
Indifference graphs have a nice inductive structure that should make it possible to
apply our deletion-contraction techniques. Although we have not been able to do this
for the full family, we are able to resolve a special case. For any composition of n,
j-i ff j . A K ff -chain is the indifference graph using the
collection of intervals f[1; ~
This is just a string of complete
graphs, whose sizes are given by the parts of ff, which are attached to one another
sequentially at single vertices. We notice that the K ff -chain for
can be obtained from the K -chain for attaching the graph
to its last vertex.
We will be able to handle this type of attachment for any graph G with vertices
Hence, we define G+Km to be the graph with
and
Using deletion-contraction techniques, we are able to exhibit the relationship between
the (e)-expansion of G +Km and the (e)-expansion of G. However, we will also need
some more notation. For denote the partition given by - with
the additional i elements added to B - . This is in contrast to
which denotes the partition given by - with the element i inserted into B - .
We denote the falling factorial by
and the rising factorial by
We begin studying the behavior of YG+Km " d+j
d with two lemmas, the first of which
follows easily from equation (10).
Lemma 7.2 For any graph G on d vertices and 1 -
Lemma 7.3 If G is a graph on d vertices with
(-)'\Pi d
then
\Theta e

(b)
Proof. We prove the lemma by induction on m. The case merely a
restatement of Corollary 6.1. So we may assume this lemma is true for YG+Km " d+m
d ,
and proceed to prove it for YG+Km+1 " d+m+1
From Lemma 7.2, it follows that for 1 - j - m, we have
Now, from G+Km+1 we may delete the edge set fv d
all the terms YG " d+j
to obtain
d \GammamY G+Km " d+m
d
d \GammamY G+Km " d+m
From this point on, we need only concern ourselves with the clerical details, making
sure that everything matches up properly. We can see from Lemma 5.1, Lemma 6.3
and the original hypothesis on YG , that
c (-)
where
Similarly, the induction hypothesis shows
(b)
where
Simplifying the terms and combining both equations (15) and (16) gives
c (-)
(b)
(b) i+2
Note that modulo d +m
So by shifting indices and simplifying, we obtain
c (-) hmi i
\Theta e

(b)
which completes the induction step and the proof.
This lemma is useful because it will help us to find an explicit formula for YG+Km+1
in terms of YG . Once this formula is in hand, it will be easy to verify that if G is
(e)-positive, then so is G+Km+1 . To complete the induction step in establishing this
formula, we will need the following observation which follows from equation (10).
Lemma 7.4 For any graph G on d vertices, and oe 2 S d ,
We now give the formula for YG+Km+1 in terms of YG .
Lemma
(-)'\Pi d
then
(-)'\Pi d
(b)
\Theta (b \Gamma m+ i)e (-)

Proof. We induct on m. If
This shows
that
c (-)
which verifies the base case.
To begin the induction step, we repeatedly utilize the Deletion-Contraction Recurrence
to delete the edges v d+i v d+m+1 for
d+m \GammaY G+Km+1 " d+m+1
Note that we are able to combine all the terms from YG+Km+1 " d+m+1
using Lemma 7.4, since in these cases the necessary permutation exists.
We now expand each of the terms in equation (17). For the first, using Lemma
6.3,
(b)

where
For the second term, using Corollary 6.1, we have
c (-) hmi i+1
(b)
where
And finally, using Lemma 7.3,
c (-) hmi i
(b)
where
Grouping the terms appropriately and shifting indices where needed gives
c (-) hmi i

(b)
This completes the induction step and the proof.
Examining this lemma, we can see that in YG+Km+1 we have the same sign on
all the coefficients as we had in YG , with the possible exception of the terms where
it is easy to see that in this case we have
This means that in the expression for YG+Km+1 as a sum over congruence classes modulo
m, we can combine the coefficients on these terms. And so upon simplification,
the coefficient on e (-+i=d+i+1;:::;d+m) will be:
(b)
(b) m\Gammai\Gammab
where c (-) is the coefficient on e (-) in YG .
Adding these fractions by finding a common denominator, we see that this is
actually zero, which gives us the next result.
Theorem 7.6 If YG is (e)-positive, then YG+Km is also (e)-positive.
Notice that Proposition 6.4 follows easily from Theorem 7.6 and induction, since
for paths As a more general result we have the following corollary.
Corollary 7.7 If G is a K ff -chain, then YG is (e)-positive. Hence, XG is also e-
positive.
We can also describe another class of (e)-positive graphs. We define a diamond
to be the indifference graph on the collection of intervals f[1; 3]; [2; 4]g: So a diamond
consists of two K 3 's sharing a common edge. Then the following holds.
Theorem 7.8 Let D be a diamond. If G is (e)-positive, then so is G+D.
Proof. The proof of this result is analogous to the proof for the case of G +Km ,
and so is omitted.
8 Comments and open questions
We will end with some questions raised by this work. We hope they will stimulate
future research.
(a) Obviously it would be desirable to find a way to use deletion-contraction to
prove that indifference graphs are e-positive (or even demonstrate the full (3+1)-Free
Conjecture). The reason that it becomes difficult to deal with the case where the last
two complete graphs overlap in more than one vertex is because one has to keep track
of all ways the intersection could be distributed over the block sizes of an e - . Not only
is the bookkeeping complicated, but it becomes harder to find groups of coefficients
that will sum to zero.
Another possible approach is to note that if G is an indifference graph, then for
the edge (where [k; d] is the last interval) both Gn e and G=e are indifference
graphs. Furthermore G n e is obtained from G=e by attaching a K d\Gammak so that it intersects
in all but one vertex with the final K d\Gammak of G=e. Unfortunately, the relationship
between the coefficients in the (e)-expansion of YGne and Y G=e " does not seem to be
very simple.
(b) Notice that if T is a tree on d vertices, we have X T
is a generalization of the chromatic polynomial, it might be reasonable to suppose that
it also is constant on trees with d vertices. This is far from the case! In fact, it has
been verified up to
This leads to the following question posed by Stanley.
Question 8.1 ([12]) Does X T distinguish among non-isomorphic trees?
We should note that the answer to this question is definitely "yes" for Y T . In fact
more is true.
Proposition 8.2 The function YG distinguishes among all graphs G with no loops or
multiple edges.
Proof. We know from Proposition 3.2 that
for the stable partitions
. Construct the graph H with vertex set V and edge
set there exists a -(P ) such that are in the same block of -(P )g:
comes from a stable partition P of G, v i and v j are in the same block of
some -(P ) if and only if there is no edge G. Hence the graph H constructed
is the (edge) complement of G and so we can recover G from H.
Of course we can have YG 6= YH but first step towards answering
Stanley's question might be to see if Y T still distinguishes trees under congruence. It
seems reasonable to expect to investigate this using our deletion-contraction techniques
since trees are reconstructible from their leaf-deleted subgraphs [9]. We proceed in the
following manner.
then by the reconstructibility of trees there must exist labelings of these
trees so that v d is a leaf of T 1 , ~
v d is a leaf of T 2 and
. By induction
we will have Y T 1 \Gammav d 6j Furthermore, our recurrence gives
One now needs to investigate what sort of cancelation occurs to see if these two
differences could be equal or not. Concentrating on a term of a particular type could
well be the key.
(c) It would be very interesting to develop a wider theory of symmetric functions
in noncommuting variables. The only relevant paper of which we are aware is
Doubilet's [3] where he talks more generally about functions indexed by set partitions,
but not the noncommutative case per se. His work is dedicated to finding the change
of basis formulae between 5 bases (the three we have mentioned, the complete homogeneous
basis, and the so-called forgotten basis which he introduced). However, there
does not as yet seem to be any connection to representation theory. In particular,
there is no known analog of the Schur functions in this setting.
Note added in proof: Rosas and Sagan have recently come up with a definition of
a Schur function in noncommuting variables and are investigating its properties.



--R

Bijective proofs of two broken circuit theorems

On the Foundations of Combinatorial Theory.
Incomparability graphs of (3
Noncommutative symmetric functions and the chromatic polyno- mial
Sinks in acyclic orientations of graphs

On the interpretation of Whitney numbers through arrangements of hyperplanes
The reconstruction of a tree from its maximal subtrees
A weighted graph polynomial from chromatic invariants of knots
Acyclic orientations of graphs
A symmetric function generalization of the chromatic polynomial of a graph
Graph colorings and related symmetric functions: Ideas and appli- cations: A description of results
On immanants of Jacobi-Trudi matrices and permutations with restricted position
A logical expansion in mathematics
--TR
On immanants of Jacobi-Trudi matrices and permutations with restricted position
Incomparability graphs of (3 1)-free posets are <italic>s</italic>-positive
Graph colorings and related symmetric functions
Sinks in acyclic orientations of graphs

--CTR
Bruce E. Sagan , Jaejin Lee, An algorithmic sign-reversing involution for special rim-hook tableaux, Journal of Algorithms, v.59 n.2, p.149-161, May 2006
Mark Skandera , Brian Reed, Total nonnegativity and (3+1)-free posets, Journal of Combinatorial Theory Series A, v.103 n.2, p.237-256, August
symmetric function in noncommuting variables;deletion-contraction;graph;chromatic polynomial