llll

‘ llllll'llllllllllllllllllllll

3 1293 01688 5

This is to certify that the

dissertation entitled

iiD€\€*1OT\-CDV\JTVQC\V‘\OH Teckniyxes :0? fine.
(\fiVOMQHC Symmetric Pundits“ 0? a 6?ka

presented by

"Dana D. seem-A

has been accepted towards fulfillment
of the requirements for

?\'\o D: degree in Ma‘i’kemaltlcS

l Major proféor g;

 

Date é/s/‘I 8

MS U is an Affirmative Action/Equal Opportunity Institution 0-12771

 

 

 

 

' {LIBRARY

Michigan State
Unlverslty

 

 

 

PLACE IN RETURN BOX
to remove this checkout from your record.
TO AVOID FINES return on or before date due.

 

MTE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1/98 chlRCIDabDuapGS—p.“

 

Deletion-Contraction Techniques for the

Chromatic Symmetric Function of a Graph

By

David D. G ebhard

A Dissertation

Submitted to
Michigan State University
in partial fulfillment of the requirements

for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1998

ABSTRACT

Deletion-Contraction Techniques for the

Chromatic Symmetric Function of a Graph
By

David D. G ebhard

Recently, R. P. Stanley defined and studied a symmetric function, XG, which
generalizes the chromatic polynomial of a graph, G. This generalization has both ad—
vantages and disadvantages. The main advantage is that it gives us more information
about the colorings of G than the chromatic polynomial. However, one disadvantage
is that this new symmetric function does not satisfy a deletion-contraction recurrence
similar to the one for the chromatic polynomial.

In this thesis, we define a similar graph invariant called YG. .This invariant is
defined using noncommutative variables, and from it we can recover XG by allowing
the variables to commute. This new invariant is also a symmetric function. More
importantly, by using noncommutative variables we will be able to obtain a deletion-
contraction recurrence for YG. We may then obtain some of Stanley’s results for X G
in a uniform manner by using induction. In addition, this will allow us to make some

progress on the 3+1 Conjecture of Stanley and Stembridge.

ACKNOWLEDGMENTS

I would like to thank my advisor, Bruce Sagan, for just about everything you
can imagine. The patience he showed as he went over the first draft of this thesis
was nothing short of remarkable. His help and support on my way to finishing this
work were wonderful, and for that I give him my thanks. The way he went over
this manuscript with a fine-toothed comb and made it a readable document was
impressive, and for that you should give him thanks!

I would also like to thank Mark McCormick for all his help with my [MEX files,
for his friendship and for helping to keep me in shape. Similarly, I would like to thank
Kevin and Melissa Dennis for their friendship, their food, and fun and games.

Finally, I need to thank my family, especially my parents and my brother for their
love, support, and encouragement through this (to them) seemingly endless journey
towards my Ph.D.

iii

TABLE OF CONTENTS

INTRODUCTION

1

Preliminaries
1.1 Symmetric Functions ...........................
1.2 The Chromatic Symmetric Function, XG ................

The N oncommutative Case
2.1 Symmetric Functions in Noncommuting Variables ...........
2.2 Development and Results for YG ....................

Orientations and Sinks
3.1 Acyclic Orientations ...........................
3.2 The Modified Blass-Sagan Algorithm ..................

Results on e-positivity

4.1 Inducing e,r ................................
4.2 Some e-positivity Results .........................
4.3 The (3+1)-free Conjecture ........................

Open Problems and Conjectures
5.1 Partitioning Acyclic Orientations ....................
5.2 X0 and Trees ...............................

BIBLIOGRAPHY

iv

1

7
7
10

15
15
20

29
29
34

41
41
48
56

67
67
70

74

INTRODUCTION

As early as 1912, Whitney [19] began to study graph colorings from a mathematical
point of View. Today the theory of graph coloring has many applications to both
scheduling problems and efficient network design. [11]. Here we will use symmetric
functions to enumerate graph colorings. While this section contains much of the
background leading up to our study, we will try to introduce notation and definitions
as they are needed throughout the text, rather than all at once. We will generally
follow Stanley [15, 14] for combinatorial notation or anything specifically related to
the symmetric function of a graph, X0, and MacDonald [10] for symmetric functions
in general.

To begin, let G be a finite graph with vertex set V(G) and edge set E (G), where
the edges consist of unordered pairs of the vertices. We mention here that if the edge
set consisted of ordered pairs of vertices we would have had a graph with directed
edges, referred to as a digraph. A vl—vn walk in a graph is a sequence of vertices,
221,112,... ,2)” such that 22,--122, is an edge for all 2 g i S n. A graph, G, is connected
if there is a u,v walk for every pair of vertices, u and v in V(G). The connected
components of G are just the maximal connected subgraphs of G. Finally, H is a
spanning subgraph of G if V(H) = V(G) and E(H) Q E(G). In our study we will
actually consider multigraphs, in which multiple edges and loops are allowed. The
other definitions above extend in the natural way to multigraphs.

Since our main interest here is in coloring graphs, we define a coloring of G to be

 

1 2 2
c o 0
v1 v2 123

Figure 1. A coloring (not proper) of P3.

 

 

1 2 3 1 2 1
k t o o 4 0
’U 1 02 ’03 ’01 v2 03

Figure 2. Two prOper colorings of P3

a map a : V(G) -—> C, where C is the color set. In particular, a proper coloring of G
is a coloring such that no two adjacent vertices are the same color, i.e., 0(1),) 75 01(2),)
if vivj is an edge of the graph. For an example, we show a coloring for the path on
three vertices, P3, which is not a proper coloring in Figure 1 and two proper colorings
for P3 in Figure 2.

Whitney’s object of study was the chromatic polynomial of a graph, XG(n), which
is defined to be the number of ways to properly color G using the color set C =
{1,2, . . . ,n déf [n]. For P3, since there are n ways to color 111 from a set of n colors,
and n—1 ways to color each of the remaining vertices, we see that Xp3(n) = n(n—1)2.
It is somewhat surprising that XG(n) is always going to be a polynomial in n. One
easy way to see this is to use induction along with the Deletion-Contraction Lemma,
which we will now discuss.

Given a graph G and an edge e E E (G), we can define the graph G -— e to be the

graph G with the edge e deleted from its edge set. The contraction of G by e, G / e, is
obtained from G by contracting e (in the topological sense) to a single vertex. Given

these definitions, the Deletion-Contraction Lemma states that

XG(n) = XG_e(n) — XG/e(n).

This gives us a recursive way to compute the chromatic polynomial of a graph, as well
as to establish various properties of XG(n) by induction. Two of Whitney’s results

that can be proven using this method are stated here.

Theorem 1 [1.9] For a finite graph, G,

260(71): 2: (—1)'3'nc<5>,

sc_:E(c)

where C(S) is the number of connected components of the spanning subgraph of G with

edge set S, which by abuse of notation we just denote by S. I

As an illustration, we will use this theorem to again calculate Xp3(n). If we let the

edge set of P3 be {e1,e2}, where el = 111112 and e2 = v2v3, then we can make the

 

 

 

 

 

following table.
S C E(G) (—1)lSl 7245)
1 n3
e1 —1 72.2
e2 —1 n2
e1,e2 1 nl

 

 

 

 

 

This shows us that according to the Theorem, Xp3(n) = n3 — 2n2 + n :2 n(n - 1)2,

which agrees with our previous calculation.

The other theorem of Whitney’s in which we will be interested is the one known as
the Broken Circuit Theorem. A cycle or circuit is a closed walk with distinct vertices
and edges, v1,v2,. .. ,vm,u1, for m 2 1. 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 the broken circuit complex 80 of G denote the set of all S g E (G) which do
not contain a broken circuit in our fixed ordering on the edges. The Broken Circuit

Theorem then asserts:

Theorem 2 [19] For any finite graph, G, on d vertices we have

xG(n) = Z (—1)|Slnd-IS|.

5630

I
If we again calculate Xp3(n) using this theorem, we will come out with exactly

what we had before, only with n3 and n1 reversing positions in the table, since P3
contains no circuits and hence no broken circuits. As a less trivial example, we will
use this theorem to verify that the chromatic polynomial for K 3, the complete graph
on 3 vertices is indeed given by n(n — 1)(n — 2), which can be obtained by noticing
that there are n ways to color the first vertex, n —1 colors left available for the second
vertex, and n — 2 colors allowed for the last vertex. We label E(K3) = {e1,e2, e3},
where the fixed order on the edges is the obvious one induced by the subscripts.
Since the only circuit in K 3 is {e1, e2, e3}, the only broken circuit will be {e1, e2}.

This gives us the following table, where we notice that here d = 3.

 

 

 

 

 

 

 

 

S 6 Ba (—1)|5| rid—'5'
d) 1 n3
e1 —1 n2
e2 —1 n2
e3 —1 77.2

e1, e3 1 it1
e2, e3 1 n1

 

 

 

 

This gives us XK3 = n3 — 3n2 + 2n, which again agrees with the previous calculation.

Following these early results, some of the more interesting applications are those
of Zaslavsky in [20, 21, 22]. In that series of papers he introduces the notion of
colorings for certain generalizations of graphs called signed graphs. These colorings
have very nice connections to characteristic polynomials of certain types of hyperplane
arrangements. A related result by Zaslavsky and Greene [7] concerns the sinks of
acyclic orientations for G. An orientation of G is a digraph D obtained by assigning
a unique direction to each edge of G. An orientation is acyclic if it has no directed

cycles. We also define a sink of D to be a vertex v E V(D) such that fit’ ¢ E (D) for

all a: E V(D). Also, for notational convenience we adopt the convention that

XG(n) = a0 + aln + agn2 + - - - + akn".

Theorem 3 ([7] Theorem 7.3) Let v0 be any vertex of G. The number of acyclic

orientations of G with a unique sink at v0 is [a1]. I

This theorem is related to one of Stanley, which states:

Theorem 4 [13] The number of acyclic orientations ofG is Z, |a,~[. I

All of these theorems are actually specializations of results which can be obtained
from Stanley’s symmetric function generalization of the chromatic polynomial. The
first three theorems listed previously can all easily be derived from the recurrence
relation for the chromatic polynomial. However, this symmetric function does not
satisfy any similar deletion-contraction recursion, which eliminates induction as a
tool for these proofs. In what follows we will extend the Stanley’s definition by
using symmetric functions in noncommutative variables. This setting will allow us to

establish a recurrence and again allow induction as a valid approach to our proofs.

CHAPTER 1

Preliminaries

1 . 1 Symmetric Functions

Here we will review the basic facts about symmetric functions in commuting variables.
Our development will closely mirror that found in Sagan’s book [12]. The interested
reader should consult either MacDonald [10] or Sagan [12] for a more comprehensive
discussion.

We will begin with the monomial symmetric functions. Let x = {$1, $2,223, . . .}
be a countably infinite set of commutative variables, and let A = (A1,A2, . .. ,Ak)
be an integer partition of n, denoted A l- n, where the A, form a weakly decreasing
sequence of positive integers such that 2le A,- = n. If we allow r,- to be the number of
parts of A equal to i, then we may also express A = (1", 2’2, . . . ,n'") as an alternate

notation. The monomial symmetric function corresponding to A is given by

_§:A1A2,H )‘k
mA— (11111132.? (III-k,

where the sum is over all distinct monomials having exponents A1, . .. ,Ak. As an

example we can see that
2 2 2 2 2
m(2,1) —$1$2+$1$3+”'+$2$1+$2$3+°"+$3$1 +"' .

We then define the ring of symmetric functions as the vector space over C spanned
by the monomial symmetric functions. It is an elementary fact that the monomial
symmetric functions are actually linearly independent over C and so form a basis for
the vector space of symmetric functions. It is important to note here that while we
will usually consider the symmetric functions as a vector Space in this thesis, the fact
that they form a closed set under multiplication also makes the symmetric functions
a ring.

While it is clear from our development that the monomial symmetric functions
form a standard basis for the symmetric functions, there are other nice bases for
this vector space which are routinely used. These include the elementary, power
sum, and complete homogeneous symmetric functions as well as the Schur functions.
We will define the power sum symmetric functions and the elementary symmetric
functions here, as they will be relevant to the rest of this thesis. For a description of
the complete homogeneous symmetric functions and the Schur functions, please see
either [10], [12], or [4]

The rth power sum symmetric function is

Pr =m<ri = Zah-

2‘21

and the rth elementary symmetric function is

6,- : Til/(1r) = E (1711' ' '17,}.

i1<...<ir

While these are seemingly natural definitions based on the monomial symmetric func-

tions, they obviously do not form bases since they are not even indexed by integer
partitions. Hence we must extend these definitions to p; and e,\ where A l- n. We

will do this multiplicatively, by defining

def def
p(’\l,/\2,---9’\k) : pAlpAz ° ° 19% and e(/\1.r\2.m¢\k) : eAieAz ' ' ' eAk'

These are the power sum and elementary symmetric functions, respectively. They

also form bases for the space of symmetric functions. To illustrate these definitions,

two simple examples are computed. For the integer partition (2,1) we have

P(2,1) =p2p1 =($i+x§+---)(x1+x2+-~)
=$¥+$3+-~+x‘fx2+$§xl+...

= me) + m(2.1)
and

e(2,l) =€2€1 =($132+1‘11L‘3+'°'+.’L'2£L'3+---)(xl+$2+x3+...)
=$i$2+$3171+---+3:r:1;1:2:v3+-~

—_— m(2,1) + 3m(1,1,1).

These functions are referred to as symmetric functions for the following reason.
Given a permutation in the symmetric group on n elements, 6 6 Sn, we define a

natural action on the set of functions in C[x] by

6f($1,$2,$3, ' ' ') : f(x6(1)3$6(2)3$6(3)1' ° ')'

It should be clear that, for any permutation 6, the elements in our space of symmetric
functions will remain invariant under this action.

Given this information about the space of symmetric functions, we now have

10

sufficient background to introduce Stanley’s chromatic symmetric function.

1.2 The Chromatic Symmetric Function, XG

In “A Symmetric Function Generalization of the Chromatic Polynomial of a
Graph” [15] (see also [16]), R. P. Stanley introduced a symmetric function, X6, which
generalizes the chromatic polynomial associated with a labeled graph on d vertices.

Definition 1.2.1 Let G have vertex set V(G) = {v1,v2, . .. ,vd}. We define

X0 = Xg(.’131,$2, . . .) = anwl) . . .2341“),
It

where the sum ranges over all proper colorings, k : V(G) —> IP, and IP’ is the set of

positive integers.

Note that XG is homogeneous of degree d = [V(G)], where [4:] denotes cardinality.
We also notice that if G has loops this sum is empty, giving X0 = 0. To illustrate
this definition, we will compute the chromatic symmetric function for our standard
example of the path on three vertices, P3. We can see that any proper coloring of this
graph will have one of two possible types: the coloring could have v1 and v3 one color
with v2 3 different color, or it could have all three vertices different colors. Since there
are 6 different ways to color the three vertices with the same set of three different

COIOTS, we Obtain
_ 2 + 2 Q . I 6 + 6 + o . .
X123 — 313:2 11321131 + + 1131172233 231332234

It should be clear from the definition that X0 is a symmetric function, since any
permutation of the subscripts simply permutes the colors and doesn’t affect the set of

colorings. We can also see it more explicitly in this case, since the previous expression

11

clearly shows that

X133 2 m(2,1) + 67720,”).

For A l- n having r,- parts of size i, we can also use the notation A =
(1’1,2’2,... ,n’"), and define [A] = r1! - - -r,,!. We say that a partition of the ver-
tex set of G is stable if no block of the partition contains adjacent vertices. Then
it is not hard to see [15] that X0 = 2A a,\|A|m,\, where a), is the number of stable
partitions whose block sizes correspond exactly to the parts of A. We are also easily
able to see that for the disjoint union of two graphs, G = H as], we have X G = X EX 1.

We can verify that this symmetric function is a generalization of the chromatic
polynomial, XG(n), since setting :51 = x2 = = a2" = 1 and 1:,- = 0 for all i > n
in X0, denote by XG(1"), yields XG(n). To see this, note that this substitution will
produce a term equal to 1 for each monomial in X0 which comes from a proper
coloring of the graph using the first it colors, and a term equal to zero for each
monomial arising from a proper coloring which uses a color not in [77.]. Hence the sum
of all these monomial terms after this substitution will just be the number of proper
colorings of G which only use the first n colors. This is precisely XG(n).

Once we are assured that this is a generalization of the chromatic polynomial,
one might expect that previous results about the chromatic polynomial should also
generalize. It is also natural to study the expansion of this chromatic symmetric
function in terms of the different symmetric function bases. The calculation of X0
for various specific graphs is also of interest. Stanley pursues all of these lines of
inquiry in his paper.

Several of Stanley’s results for XG are extensions of Whitney’s [19] theorems for
the chromatic polynomial. For example, Stanley’s symmetric function extension of

Theorem 1 utilizes the power sum symmetric functions.

12

Theorem 1.2.2 [15, Theorem 2. 5] Let G be a finite graph of order d. We have

X0 = Z (‘Ulslpusp
599(0)
where A(S) = (A1, A2, . .. ,Ak) is the integer partition of d with A,- being the number

of vertices in the it” component of S. I

We can see that this result directly implies Whitney’s first theorem by noticing
that pr(1") = n for any r, and so pA(1") = n“), where l(A) is the number of parts of
A. Hence p,\(3)(1") = n45), completing the reduction.

Not surprisingly, Stanley also has a generalization of Theorem 2.

Theorem 1.2.3 [15, Theorem 2.9] For any finite graph G, we have

XG : Z (—1)lslp,\(5).

3630 I

In this thesis, we will be studying an analogue of Stanley’s chromatic symmet-
ric function X0, called Ya, which is defined using noncommutative variables. We
wish to consider this analogue because we know that many results for the chromatic
polynomial can be proven easily using induction and the deletion-contraction recur-
rence. Unfortunately, Stanley’s symmetric function has no such deletion-contraction
property, which deprives him of induction as a tool for his proofs.

To see where the problem lies, note that X0 is homogeneous of degree d, while
XG/e is homogeneous of degree d — 1. In order to find a recurrence, we would need to
add another variable to each monomial in X G )8. But which variable? In the proof of
the deletion-contraction rule for the chromatic polynomial, we have proper colorings
of G / e corresponding to colorings of G - e with u and v the same color, where e = uv.
However, while XG/e gives us more information about the colorings of G / e than the

chromatic polynomial, it does not give us the explicit information we need to fix the

13

problem: namely, what color was assigned to the vertex obtained by contracting uv.
We lost that information when we allowed the variables to commute.

To correct this difficulty, in Chapter 2 we introduce an analogue of X0 which is a
symmetric function in noncommutative variables. That is, for any multigraph G with

vertices labeled v1, v2, . . . ,vd in a fixed order we define the analogue of X0 as

Y0 = 2%(voxnaz) ' ' '$n(v.)

where again the sum is over all proper colorings of G, but the 12:,- are now noncom-
muting variables.

The reason for using noncommuting variables is so that we can keep track of the
color which n assigns to each vertex. Since we still have the homogeneity problem
in YG/e, we define an operation on the non-commutative symmetric functions which
will allow us to use deletion-contraction techniques for computing Ya. In this chapter
we also provide some basic expansions of YG which closely resemble Whitney’s and
Stanley’s theorems.

In Chapter 3 we will further explore the interrelationships between chromatic
polynomials, chromatic symmetric functions, acyclic orientations and sinks. There is
an interesting connection between Theorem 2 and the result of Green and Zaslavsky,
Theorem 3. From Theorem 2 we can interpret the coefficients of the chromatic poly-
nomial as the number of sets S E BG of a certain size. From Theorem 3, we see the
coefficient of n in XG(n) is the number of acyclic orientations of G with a unique
sink at any fixed vertex of G. It follows that the number of acyclic orientations of
G with a unique sink at the fixed vertex is the same as the number of sets S 6 BC
with IS] = d — 1. Elementary graph theory tells us that this is also be the number
of spanning trees of G which contain no broken circuits. We will provide a bijective

proof of this fact by modifying an algorithm due to Blass and Sagan [1]. Finally,

14

we will also extract some of the information that the non-commutative chromatic
symmetric function can give us about acyclic orientations and sinks.

In Chapter 4 we will consider a conjecture about the coefficients of Xg, when it is
expanded in terms of the elementary symmetric function basis. We will make some
progress here on the (3 + 1)-free conjecture of Stanley and Stembridge, proving it in
some special cases.

We finish in Chapter 5 with some other partial results about acyclic orientations
and sinks, as they relate to the (3 + l)-free conjecture. We conclude with some
open problems, as well as a few ideas on how they might be approached using our
techniques. Before we begin, however, we will need to discuss symmetric functions in
noncommuting variables and our analogue of X0 in that setting. This is the focus of

our next chapter.

CHAPTER 2

The Noncommutative Case

2.1 Symmetric Functions in Noncommuting Vari-

ables

We begin with some background on symmetric functions in noncommuting variables.
Much of this follows from the work of Doubilet [4], although he does not explicitly
mention these functions in his work. These noncommutative symmetric functions will
be indexed by set partitions, which form a lattice under a certain partial order, which
we will define here.

A lattice is a poset (partially ordered set) .C such that every pair 2:, y E C has a
least upper bound (or join) denoted by a: V y and a greatest lower bound (or meet)
denoted :1: /\ y. Any finite lattice has a unique minimal element denoted by D and
a unique maximal element denoted by 1. We let IId denote the set partitions of
{1,2, - - - , d} = [d]. This forms the set partition lattice, where the partial order is
defined as follows. Ifo = Al/Ag/ - - -/A;c and r = Bl/Bg/ - n/Bm, then a g r if and
only if for all 1 g i _<_ k there exists some 3' with 1 S j S m 30011 that Ai g B)"
That this partial order on 114 actually forms a lattice is an elementary result. As an

example, We have included the Hasse diagram for I14 in Figure 2.1. Given a poset,

15

 

Figure 2.1. The partition lattice I14.

P, we also recursively define the Mb'bius function, u, of P on intervals [33, y] in P by

p(:r,:c) = 1 and u(a:,y) = — Z n(x, z) for all x,y E P.
zSz<y
It can be shown that for o, r 6 IL; with o = A1/A2/‘ - -/A,c and r = Bl/Bg/ - - -/Bm,

and a S 7-, then

Mon) = Hens-1a.. -1)!.

n=1
where an is the number of blocks of 0 contained in B".

Since we will be using both integer and set partitions in this thesis, our convention
will be that A and a generally denote integer partitions, while a, r, and 7r are usually
set partitions.

If 7r 6 IL, we define A(7r) to be the integer partition of d whose parts are the block
sizes of 71'. So if 7r = 81/82/ . . . /B,,, where the block sizes are in weakly decreasing

order, we have A(W) = ([31], lel, - -- ain|)' Further, if M”) = (1r1’2r2, ' -- ,d’d), we

17

define

[7f] 2 Tli’l‘gi'Hle

and

7r! 2 1!“2!’”2 - - -dl'd.

We can now introduce the vector space for the noncommutative symmetric func-
tions. Let x :2 {11:1,:z:2,:r3, . . .} be a set of noncommuting variables. We define the

noncommutative monomial symmetric functions, m”, by:

m”: 2 z,,:z:,-2---:t,d, (2.1)
d

il’i2,vco ,i

where the sum is over all multisets (collections in which repetitions are allowed)
{{i1,i2, . . . ,id}} of the positive integers I? such that i,- = ik if and only if j and k are

in the same block of 7r. For example,
m13/24 2 11311132231552 + xgxlzgrtl + xlxgxlxg + 2:351:1233131 + - --

is the monomial symmetric function in noncommuting variables corresponding to the
partition it = 13/24.

We notice, from [4] that letting the 2:,- commute transforms m,r into |7r|m,\(,,). The
noncommutative monomial symmetric functions, {m,r : 7r 6 H4, d E N}, are linearly
independent over C, and we call their span the set of noncommutative symmetric
functions. (Note that this is different from the noncommutative symmetric functions
studied in [6])

Another useful basis will be the noncommutative power sum symmetric functions

18

given by
d r
p7f é Zma : Z $i1$i2 ° ' 'xida (22)
021T i1,i2, ..,id
where the second sum is over all multisets {{i1,i2, . .. ,id}} of IP’ such that i, = ik

if j and k are both in the same block of it. In a similar manner we will define the

noncommutative elementary symmetric function basis elements by

2 m0: 2 515,123,2- ~27,“ (2.3)

o:aA7r=D ilvi21‘" n}:

where the second sum is over all multisets {{i1,i2, . . . ,id}} of IP’ such that i, 75 ik if
j and k are both in the same block of it. With these definitions one may derive the

formulae found in the appendix of Doubilet’s paper [4] which show

= 2M”, (7)290

and

 

m,=z:fl'(7T T) )2: u(a,r)ea. (2.4)

T>1r [1(0,T) a<r

This verifies that these are actually bases for the noncommutative symmetric func-
tions.

As an illustration of these definitions, we see that

4 4
Pia/24 = 11311132171172 + 3313;311:1333 + - - - + 531+ :52 + . ..

= m13/24 + m1234

19

and that

2 2 2 2
e13/24 = x1x2+---+x1$2z1+---+:rla:2m3+~-

2 2
+$1$2$3 + ' ' ° + 11315525133 + ' ' ' + 23123211732714” ' ' ' + 171112113334 ' ' °

= m12/34 + m14/23 + m12/3/4 + m1/23/4 + m1/2/34 + m14/2/3 + m1/2/3/4-

Allowing the variables to commute transforms p,r into pm.) and e,r into 7rle,\(,,).
It should be clear that these noncommutative symmetric functions are symmetric
in the usual sense, i.e., they are invariant under the previously defined symmetric
group action on the variables. However, it will be useful to define a new action of the
symmetric group on the noncommutative symmetric functions which permutes the

positions of the variables. For 6 E 8d, we define
6 O m‘ll’ déf m6(1r)i

where the action of (5 E 3,; on a set partition of [d] is the obvious one acting on
the elements of the blocks. It follows that for any 6 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

def

6 o (xilxh ' ' . xik) : xi6‘1(1)$i6‘1(2). . . CD’S-10:)

and extend linearly.
Utilizing the first characterization of this action, it follows straight from definitions

(2.2) and (2.3) that (5 Op,r = p5(,r) and 6 0 8n = 65(70'

20
2.2 Development and Results for YG

We begin this section by reviewing the definition of Y0.

Definition 2.2.1 For any multigraph G with vertices labeled v1, v2, . . . ,vd in a fixed

order, define

YG : Z $K(v1)$n(v2) ' ' ' xK(Ud)’
n

where again the sum is over all proper colorings of G, but the :13,- are now noncom—

muting variables.

As an example, we can calculate

Y3, = $117231 + 3322:1232 + xlxgscl + - - - + 5131;102:133 + 2313:3232 + - - - + 113323211 + - ~-

= m13/2 + m1/2/3-

We again mention that if G has loops then this sum is empty and we would have
Y0 = 0. Furthermore, YG depends not only on G, but also on the labeling of its
vertices. In this section we verify that YG does indeed satisfy a deletion-contraction
recurrence and use this to prove some results about the expansion of Y0 in certain
bases for the noncommutative symmetric functions. In order to get such a recurrence,
it is necessary to have a distinguished edge.

We want to be able to uniformly choose such an edge, and so we will also define an
action of the symmetric group on a graph. For all 6 6 8,1 we let 6 act on the vertices
of G by 6(v,-) = um). This creates the action on graphs given by 6 (G) = H, where
H is just a relabeling of G. Finally, any partition P of V(G) induces a set partition

n(P) of [d] correSponding to the subscripts of the vertices.

21

Proposition 2.2.2 (Relabeling Proposition) For any finite multigraph G, we

have

5 0 Y0 = Yam),
where the vertex order v1, v2, . .. ,vd is used in both Y6 and Yam)-

Proof. Recall that a stable partition of the vertex set of G is a set partition of V(G)
such that no two vertices in the same block of the partition are adjacent. (If G has

a loop, there are none.) It should be clear from the definitions that

Y0 = Emma) (2.5)
P

where the sum is over all stable partitions, P, of V(G).

If we have two different labelings of G, say G and H, we choose (5 E 5.1 such that
6(G) = H. We note that the action of 6 produces a bijection between the stable
partitions of G and H. Utilizing the above characterization (2.5) of YG and denoting

the stable partitions of G and H by PG and PH respectively, we have

YH = 2 mm”) = Z mum’s» = Z 5 ° mare) = 5 0 Z mWU’G) = 5 0 Ya- I
PH PG PG PG

We now turn our attention to deletion-contraction techniques. Using the Rela-
beling Pr0position allows us, without loss of generality, to choose a labeling of G so
our distinguished edge is e = vd-1vd. It is this edge for which we will derive the

deletion-contraction recurrence for Y0.

Definition 2.2.3 We define an operation called induction, T, on the monomial

22
xii$i2 ' ' ' mid—215124, by

— a ' O O I ' 2
(xiixiz ' ' ' mid—2xid—1)T _ $¢1$12 mid—zxid_1

and extend this operation linearly.

Note that this function takes a noncommutative symmetric function which is homo-
geneous of degree d — 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.

This definition will only be used for deletion-contraction on the edge e = vdvd_1.
We can extend induction to any edge e : vkv, as follows. For k < I, define an oper-
ation T], on noncommutative symmetric functions which simply repeats the variable

lth

xk in the position. That is, for a monomial 12,, - - -x,~k - - -x,- 4-1, define

def

l
($i1°"xik "°$il_l.'17il OHxid—1)Tk : $11 -..$ik

and extend linearly.
At this point it will be useful to adOpt the convention that provided G has an
edge which is not a loop, we choose a labeling such that e = vd_1vd. We also note

here that if there is no such edge, then

Y0 = 61/2/.../d = p1/2/.../d If G = R: (2.6)

0 if G has a loop.

We mention here that K, is the complete graph on d vertices, i.e., the graph (not
multigraph) on (1 vertices having all possible edges. Its edge complement is H}, the
completely disconnected graph which has d vertices and no edges. In order to allow
for multiple edges and 100ps, we note that contracting a multiple edge will form a

loop, and adopt the convention that to contract a loop, we simply delete it.

23

Proposition 2.2.4 (Deletion-Contraction Proposition) For e = vd_1vd, we

have Y0 = YG_8 — YG/eT, where the contraction of e = vd_1vd is labeled vd_1.

Proof. The proof is very similar to that for the deletion-contraction property of

X9. We consider proper colorings of G — e. They can be split disjointly into two

types:
1. Proper colorings of G — e with vertices v4-1 and vd different colors;
2. Proper colorings of G — e with vertices vd_1 and vd the same color.

Those of the first type clearly correspond to proper colorings of G. If k is a
coloring of G - e of the second type then, since the vertices vd_1 and vd are the same

color, we have

$~(v1)x~(v2) ' ' '$~(vd-.)$~(vd) = ($k(v1)$n(v2) ° ' °$~<vd_.>)T= 552T

where it is a proper coloring of G /e, and the vertex obtained from the contraction
is labeled vd_1. Thus we have Yg_e 2 Ya + YG/e T. Rearranging the terms gives

YG = YG—e — YG/eT- I

We note that if e is a repeated edge, then the proper colorings of G — 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 a loop, and so it has no proper colorings.

Also note that since we allow multiple edges when contracting e we have

|E(G - ell = |E(G/6)| = |E(G)l - 1-

The Deletion-Contraction Proposition for Ya gives us a tool for using induction.

For 7? 6 I'Id_1 we let it + (d) 6 IL; denote the partition 7r with d inserted into the

24

block containing (1 — 1. From equations (2.1) and (2.2) it is easy to see that
mnT: m1r+(d) and 19an pn+(d)-

With this notation we can now provide an example of the deletion-contraction propo-

sition for P3, where the vertices are labeled sequentially, and the distinguished edge

is e = v2v3.

YP3 : YP2BJ{U3} _ YP2T '

It is not difficult to compute

YP2w{v3} = m1/2/3 + m1/23 + "113/2,
YP2 = ml/Za
YP2T = 7711/23-
This gives us
YPs = m1/2/3 + "ll/23 + m13/2 — m13/2

— m1/2/3 + "113/2,

which agrees with our previous calculation.

We may use this recurrence to provide noncommutative analogues of the previ-

ously cited results of Stanley, where the proofs now follow from induction.

Theorem 2.2.5 For any finite labeled graph G,

Y0 = Z(—1)Islpn(5),

s<_:E

where 7r(S) denotes the partition of {1, 2, . . . ,d} associated with the partition of V(G)

25

into the connected components of S.

Proof. We induct on the number of non-loops in E (G) If E (G) consists only

of n loops, for n 2 0, then for all S Q E(G), we will have 7r(S) = 1/2/ ' - -/d. This
shows us that

P1/2/.../d if n = 0,

Z(—1)|Slp7r(s) =Z(-1)ISIP1/2/.../d :2: (i) (_1) P1/2/.../d =
i=0 0 if n > 0.

sge ng

This agrees with equation (2.6).

Now, if G has edges which are not 100ps, we use the Relabeling Pr0position to
obtain a labeling for G with e = vd_1vd. From the Deletion-Contraction Proposition
we know that YG = YG__e — Yg/eT and that both G —— e and G / e have one fewer edge

than G. This allows us to apply induction to YG_e and Ya/e, obtaining

Ya: Z) (—1>'S'p.(5)— Z (—1>'§'p.(S-,T.

S§E(G—e) S§E(G/e)

It should be clear that

Z (‘1)IS'PMS): Z (-1)'S'pn(3).

S§E(G—e) S§E(G)
e¢S

Hence it suffices to show that if e E S,

— Z (‘Ulglpfigfl = Z (—1)'S|Pn(5)-

S§E(G/e) sgsga)
8E

To do so we define a map 6 : {S g E(G/e)} -> {S Q E(G) 3 6 E S} by

9(S) = S, where S = S U e.

26

Then 9 is a bijection, since we allow multiple edges to occur when we contract e to

vd_1 . We know that [S] +1 2 IS] and n(S) = 7r(S) + (d), giving p,,(5) = pfigfl‘. Thus

we have
" Z (‘1l'S'Pn(S)T = Z (_lllswl’rw?)T
S§E(G/e) S§E(G/e)
= Z (-1)'S'P«(S)-
S§E(G)
e65
This completes the proof. I

By letting the x,- commute, we then obtain Theorem 1.2.2 as a corollary. There
are also other results which we may obtain by this method, such as Stanley’s gener-
alization of Whitney’s Broken Circuit Theorem. Before we prove this, however, we
will need the following lemma, which appeared in [1]. For the sake of completeness,

we include a proof here.

Lemma 2.2.6 For any non-loop e, there is a bijection between BG and 80.3 U Bg/e

given by

~

S=S—eeBG/e ifeeS
SZSEBG_3 ife¢S,

S——>

where we take 6 to be the first edge ofG in the total order on the edges .

Proof. It is enough to show that this map is well-defined, and that it has a well-
defined inverse.

To show that it is well-defined, we let S E BC with e E S. Notice that e is neither
a loop nor a multiple edge: if e were a loop, then d) is a broken circuit, and so e gt S.

If e and e’ have the same endpoints, then by the assumption that e is minimal, e is

27

a broken circuit, and so again e g! S.

If e a! S it is clear that S E BG_e, since any broken circuit of G — e is also a broken
circuit of G.

If e E S, we let S = {e, e2, . .. ,ek} be listed in increasing order, according to the
total order, 3, on the edges. Then S 2 {e2, . .. ,ek} does not contain any broken
circuits of G / e, for if S’ was a broken circuit of G / e contained in S, then S’ U{em}
would be a circuit of G/e for some em larger than any element of S’. But then
S’ U{em, e} would contain a circuit of G. So S’ U{e} would contain a broken circuit
of G, since e g em. This contradicts S 6 Ba. To construct the inverse, we simply

map

In

- S If S 6 80-8
S ——-> ~ ~
SU{€} if S E BG/e-

It is clear that this is the inverse, provided again that the map is well-defined. An

argument similar to the one given above shows that this is indeed the case. I

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 2.2.7 We have

ya = Z (‘1)ISIPn(S),

3686

where again n(S) denotes the partition of {1,2, . .. ,d} with blocks corresponding to

the connected components of S. I

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 > O we will have every edge

28

being a circuit, and so the empty set is a broken circuit. Thus we have

Zse¢(—1)|S|Pn(5) : 0 if n > 0,

Zse{¢}(-1)IS|P7r(S) = P1/2/.../d if R = 0.

Y0 =

This again matches equation (2.6).
For n > 0 and e a non-loop, we again consider Y0 = YG_e — YG/CT, where G —- e and
G / e both have one less edge than G, and so induction applies. From the preceding

lemma and arguments as in Proposition 2.2.5, we have

2 (-1)Sp..(5)= Z (-1)Spn(5)

SGBG SEB _
eQS G c

and

Z (—1)'S'p.(3)=— Z (—1)'§'p.(S-,t

S93(0) SEB c
865 G/

which gives the result. I

CHAPTER 3

Orientations and Sinks

3.1 Acyclic Orientations

As we have seen in the introduction, there are some interesting results which relate
the chromatic polynomial of a graph to the number of acyclic orientations of the graph
and to the sinks of these acyclic orientations. We begin here by proving Theorem 3.
While the result is not new, we do offer a new proof here more in keeping with the
spirit of the other proofs in this thesis. 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 v0 by A(G, v0).

We also recall our notation that XG(n) = a0 + aln + ' - - + aknk.

Lemma 3.1.1 For any fixed vertex v0, and any edge e = uvo, u 75 v0, the map

D—e€A(G—e,v0) ifD—eEA(G——e,v0)
D/e E A(G/e,v0) ifD — e ¢ A(G — e, v0),

D—->

is a bijection between A(G, v0) and A(G—e, vo) ErJA(G/e, v0), where the vertex of G/e

formed by contracting e is labeled v0.

Proof. We must first prove that this map is well-defined, by showing that in both

cases we actually obtain an acyclic orientation with unique sink at v0. This is clear

29

30

in the first case by definition. In the second, where D — e 5! A(G — 6, v0), it must
be true that D — c has sinks both at u and at v0 (since deleting a directed edge of
D will not change the acyclic property of the orientation, nor can it cause us to lose
the sink at v0). So the orientation D/e will be in A(G / e, v0): since u and v0 were the
only sinks in D — uvo the contraction must have a unique sink at v0, and there will
be no new cycles formed. Hence this map is well-defined.

To see that this is actually a bijection, we need only exhibit the inverse. This is
obtained by simply orienting all edges of G as in D — uvo or D/uvo as appropriate,

and then adding in the oriented edge 2E3. It should be clear that this map is also

well-defined. I

Lemma 3.1.2 IfG is connected, then any D E [A(G)| has at least one sink.

Proof. While this is a well-known graph theory result, we prove it here for complete-
ness, by way of contradiction. Consider the finite set of directed walks in A(G) given

by

S={’Uil—)’Ui2—>...—)’Uikivi,EV(G) fOI‘ISlSk, andk§|V(G)[+1}.

Clearly S 75 d5, since for any vertex v E G, the trivial walk given by v will be an
element of S. So we may consider a walk, W, in S with maximum k. If k = |V(G)|+1,
then W contains a cycle, contradicting D E A(G). If k _<_ |V(G)|, then we claim that
wk will be a sink of D. If it is not a sink, then there is a directed edge e = 17,15,
for some w E E (G) Adding this directed edge to W will again give us a walk in S.
But this contradicts our choice of W. Hence vi, must be a sink of D, completing the

proof. I

As an immediate corollary we have the following result.

 

31

Corollary 3.1.3 For any D E |A(G)|, the number of sinks is greater than or equal

to the number of components of G. I

Using Lemma 3.1.1 and Corollary 3.1.3, we may now prove Theorem 3 by showing
that the boundary conditions and recurrence relations for [all and the number of

acyclic orientations with a unique sink at a fixed vertex, v0, are the same.

Theorem 3.1.4 [7] For any fixed vertex v0, the number of acyclic orientations of G

with a unique sink at v0 is [a1].

Proof. We prove this theorem by showing that the boundary conditions and recur—
rence relations for |a1| and |A(G, v0)| both match. Our recurrence will only be valid
when there is a non-loop incident with v0, and so our boundary condition will occur

in the case where only loops are incident with v0. If d = 1, then

Tl If G 2 K1,
X601) =
0 if G has loops.
So in this case,
1 If G 2 K1,
[all = = me, 210)].

0 if G has loops

If d > 1, then having only loops incident with v0 is equivalent to having at least
two components in G. In this case we see from Theorem 1 that [a1] = 0 and from
Corollary 3.1.3 that [A(G, v0)[ = 0 as well. Thus the boundary conditions match.
Now if there is a non-loop e incident with v0, we can see that [all is the sum of
the absolute values of the coefficients of n from XG_e and XG/e since the signs on
the coefficients of the chromatic polynomial alternate. Hence it follows from Lemma

3.1.1 that the recurrence relations are also the same and so the theorem is proven. I

Stanley has a stronger version of this result.

 

32

Theorem 3.1.5 [15] If X0 = Z, cAeA, then the number of acyclic orientations ofG

with j sinks is given by Z c,\. I
l(A)=J’

We can prove an analogue of this this theorem in the noncommutative setting by

using techniques similar to his, have not been able to do so using induction. We can

inductively demonstrate the weaker versions which follow.

Theorem 3.1.6 Let YG = 2 one”. Then for any fixed vertex, v0, the number of
«611,,

acyclic orientations of G with a unique sink at v0 is (d — 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 100ps, then

el/g/W/d if G has no edges
Y0 =

0 if G has loops.

Cid] = = [A(G,’U0)|.

0 ifd>1orGhasloops

If G has non-loops, then by the Relabeling Proposition , we may let e = vd_1vd.
We know that Y0 = YG\e - YG/e T. Since we will only be interested in the leading

coefficient, let

Y0 = aem + Z aaea,
o<[d]

Ya. = bet] + Z baa...

a<[d]

33

and

YG/e : C€[d—1] + Z Coed
o<[d-—1]

where S is the partial order on set partitions. By induction and Lemma 3.1.1, it is
enough to show that (d — 1)!a = (d — 1)!b + (d — 2)!c. For 7r 6 IId_1 we recall that
7r + (d) 6 IL; is obtained by inserting d into the block of it which contains d — 1. It
was noted before that for it E 11.1-1, we have p,,T= p,,+(d). We utilize the change of

basis formulae from equations (2.2) and (2.4) to obtain

 

enT= Z ”(0 a) )2 p( 7‘, o +( (3.1)

)r<0'+(d)

With this formula, we compute the coefficient of em from YG/CT. The only term which

contributes comes from ce[d_1]T, which gives us

 

ce[d_1]T = c X [NO/fooffil) )2 p(,(dro+

o€Hd_1)r<a+(d)

2 CM( w—11)de
#(0 d1) THEE, ’

: :cle[a(]+ZdeT

T<ldl

 

Thus, from Y0 = YG\e — YG/eT we have that

 

(d—1)!a = (d—l)!b+(d—1)!d_1

= (d —1)!b + (d -— 2)!c,

 

34

which completes the proof. I

The following corollaries follow easily from this result.

Corollary 3.1.7 If YG :2 2 one,” then the number of acyclic orientations of G
«end

with one sink is dlcm.

Proof. From the proof above it follows that the number of acyclic orientations of
G with a unique sink at v is independent of the choice of 22. Since there are (1 vertices,
the above prOposition implies that the total number of acyclic orientations of G with

only one sink is dlcm. I

Corollary 3.1.8 If Y0 = Z ewe,” then the number of acyclic orientations of G'

WEI-Id
with one source is dlcm. I

This should be obvious, since reversing an acyclic orientation with a unique sink
at a given vertex produces an acyclic orientation with a unique source at that vertex,
and vice-versa.

Also following immediately from Theorem 3.1.4 and Proposition 3.1.6, we have

coronary 3-1-9 If Y0 = 2 67.87,, and XG(n) = a0 + aln + - - - + aknk then
WEI-Id

(d— 1)lc[d] = |a1|.

3.2 The Modified Blass-Sagan Algorithm

From Theorem 3.1.4 we know that the number of acyclic orientations of G with a
unique sink at no is given by |a1|. From Whitney’s Theorem, we also see that I01] is

the number of sets, S E 30 with |S| = d — 1. We would like to prove that these two

 

35

quantities are equal directly without using the chromatic polynomial. To do so, we
introduce the notation that for any arc a = 2713, the oppositely oriented arc is denoted
a’ = «m. We also say that to unorient an arc, a, in a digraph we will just add the
oppositely oriented arc a’. Since we are interested in acyclic digraphs, it is necessary
to adopt the convention that a digraph is acyclic if it has no cycles of length 2 3.
With this convention, unorienting an arc will not necessarily produce a cycle. Also
for any acyclic digraph D, we will need to let c(D) be the contraction of D, which
simply contracts all unoriented arcs of D. If D has no unoriented arcs, then it is clear

that D = c(D). We notice that c(D) is still acyclic and has no unoriented arcs.

Corollary 3.2.1 For any fixed vertex UO 6 V(G), the number of acyclic orientations

of G with a unique sink at be is the same as the number of sets, S 6 BC with

|S|=d—1.

Proof. Here we present a bijective proof of this result. We shall do this by means
of modifying an algorithm first introduced by Blass and Sagan in [1]. This modified
algorithm will examine the arcs of an acyclic orientation of G one at a time, and
either delete the arc, or unorient it.

We now present the algorithm. Let us fix an orientation of G, which we will
refer to as the normal orientation of G, and also choose a fixed vertex 120 of G. The
algorithm will accept any acyclic orientation D of G which has a unique sink at no,
and consider each arc in turn, using the total order on the edges which defines the
broken circuits. At the stage when an arc a = M is being considered, the algorithm
will delete the arc a = M if either:

I) D + a’ has a cycle, or

II) c(D) — a has only one sink, and a is not normally oriented.

Otherwise, the algorithm will unorient a. For an example of how this algorithm works,

see Figure 3.1. The steps of the algorithm in this figure are labeled by either I, II,

 

Normal Orientation: - 4\
AA

 

 

 

Figure 3.1. An example of the Algorithm

or 11, indicating if the algorithm deleted the edge for reason I or II, or unoriented it.

To show that this algorithm actually does produce a bijection, we shall first in-
troduce a sequence of sets, D0, D1, . .. ,‘D,, such that Do is the set of all acyclic ori-
entations of G with a unique sink at 220 and 1),, (where q = |E(G)|) is the set of all
5 6 BC with |S| = d — 1. Equivalently, D, is the set of all spanning trees, T, of G
such that E (T) contains no broken circuits.

We will show that the kth step in the algorithm produces a bijection, Ak, from
Dbl to Dk, where Dk is defined as the set of all spanning subdigraphs D of G
satisfying the following conditions:

(a) Each of the first k edges of G is either present in D (as an unoriented edge)

or absent from D, but each of the remaining q -— k edges is present in D in exactly

37

one orientation.

(b) D is acyclic.

(c) D has a :r —-> 220 path for every 3: E V(D).

(d) The unoriented part of D contains no broken circuit.

From these conditions, it should be clear that Do is indeed the set of acyclic
orientations of G with a unique sink at no, since any finite weakly connected acyclic
digraph has at least one sink. It is also clear that any element of R, will be an acyclic,
connected graph, which implies that the elements of Q, must be trees with exactly
d — 1 edges. So provided the algorithm produces a bijection at each step, we will
produce the desired bijection between acyclic orientations of G with a unique sink at
110, and edge sets of size d — 1 which contain no broken circuits.

We should also note here that conditions (b) and (c) together imply that c(D)
must have a unique sink which occurs at the vertex identified with uo. That this is
the only possible sink of c(D) is clear from condition (c). We also know that 220 must
be a sink of c(D), since if it is not, then there is a vertex u and are a = m in c(D).
But from condition (c) there would have to be a u —-> v0 path in D. This contradicts
(b), which asserts that D is acyclic.

To show that the algorithm does indeed produce a bijection at each step, we use

the following three lemmas. We also use the notational convention that a digraph in

D1, will be denoted by Dk.
Lemma 3.2.2 Ak maps ’Dk_1 into Dk.

Proof. We need only prove that each of the properties (a)-(d) listed above is
satisfied after the algorithm is applied at the kth step. We proceed to prove each one
in turn.

(a) Since at the kth step the algorithm will either delete or unorient the kth edge,

this is clear.

38

(b) Since any edge which would form a cycle if unoriented will be deleted by the
algorithm, this also is clear.

(c) Since unorienting an arc can never destroy an a: ——> '00 path, we need only
consider the case where the algorithm deletes an arc. In fact, if the arc a 2 17b in
Dk_1 was deleted, we need only show that there is still a w —+ uo path.

Now, if the arc a = 171% in Dk-1 was deleted for the first reason, then we must
have had another (different) w —+ u path in Dk_1. Since there was a u ——> v0 path in
Dk_1, (in fact, one which didn’t use the arc a) we can then extend our other w —> u
path into a walk containing a w —> 110 path in Dk.

If the arc a = 21713 in Dk_1 was deleted for the second reason, again we need only
consider the possibility that for the vertex w, there is no w —> uo path in DC. But
then there is no oriented arc 1172’ with u 75 u’, since otherwise all u’ —+ on paths must
also use the arc a, as there are no w —> v0 paths in Dk. Thus Dk_1 would have a cycle
containing w. Contracting all unoriented arcs from w and repeating this argument
as necessary, we see that w would then be a sink of c(Dk_1) — a, which contradicts
our reason for deleting a.

(d) Suppose for the sake of contradiction that the unoriented part of D, contains
a broken circuit, C — x, where :1: is the greatest element of the cycle G. Since the un-
oriented part of Dk_1 didn’t contain any broken circuits, and since the only difference
between Dk_1 and Dk is at the kth edge a, we see that a must be unoriented in Dk
and that a E C — 1:. But then a: is greater than a, and so :2: is present in DC in one of
its orientations. But all the other edges in C’ are also present and unoriented. Hence,

C forms a cycle in Dk, contradicting the previously verified fact that Dk is acyclic. I

Lemma 3.2.3 Ak is one-to-one.

Proof. Suppose D1 and D2 are two distinct elements of Dbl which are both

mapped to D by the algorithm. Since the algorithm only affects the kth edge, we

39

note that D1 and D2 (and consequently c(Dl) and c(D2)) must only differ in the are
a. Without loss of generality, we may assume that a has an abnormal orientation in
D2 and a normal orientation in D1.

We note that D was not obtained from D1 and D2 by the deletion of the arc
a: we know that a could not have been deleted from either D1 or D2 for forming a
cycle, as the other would then have contained that cycle. Also, if a was deleted by
the algorithm from both D1 and D2 for the second reason, then a was abnormally
oriented in both D1 and D2, which is not possible.

If a was not deleted by the algorithm, then c(Dg) — a has an additional sink. So
if a = u'J—b is the arc in C(Dg), then w 79 220 since 220 is a sink, and so w must be the
additional sink in c(D2) — a . But this means that w was already a sink in c(Dl),

contradicting D1 6 ’Dk_1. I

Lemma 3.2.4 A, maps Dk_1 onto Dk.

Proof. Given Dk 6 Pk we must construct Dk_1 E ’Dk_1 which maps onto it.
Hence for any digraph, D1,, 6 Dk, we must construct a digraph Dk_1 and verify that
the algorithm does indeed map Dk_1 onto D1,, and that Dk_1 satisfies properties (a)-
(d). For all of the following cases, it will be immediate that the Dk_1 we construct will
satisfy properties (a), (b), and ((1), so we will only show the verification of property
(c). Let a be the kth edge of G. There are two cases.

The first case is when a $4 Dk. If there exists a unique orientation of a in which
Dk would remain acyclic, we give a that orientation in Dk_1. If both orientations of
a would preserve the acyclicity of D1,, then we choose the abnormal orientation for a
in Dk-1. We note that at least one of the orientations of a must preserve acyclicity,
since otherwise a completes two different cycles in Dk_1. These two cycles together

would contain a cycle in DC, which is a contradiction.

40

That the algorithm maps the digraph Dk_1 obtained in the previous paragraph to
D, is obvious when only one orientation of a produces an acyclic orientation of Dk_1.
However, if both produce acyclic orientations, we need to check that c(Dk_1) —a has a
unique sink at 220. This is true, since it is easy to see that c(Dk_1) —a = c(Dk_1— a) =
c(Dk). To verify that c(Dk_1) constructed above still satisfies property (c), we note
that adding an arc cannot destroy any existing paths.

For the other case, we suppose that a is present in Dk as an unoriented edge e,
and so neither orientation can produce a cycle in Dk_1 . We note that there must be
at least one orientation of e = wu such that there remains an a: —> 220 path for every
x E Dk_1. If all a: —> 110 paths p use the are a = M for some 1', and if all y —+ 210
paths q use a’ = M, then the a: —+ w portion of P together with the w —> v0 portion
of Q contains an a: —> v0 path avoiding a, which contradicts our assumption about 11:.

If there is a unique orientation of e = wu so that there remains an a: ——> uo path
for every :1: E Dk_1 we choose that one to maintain property (c) for Dk_1, say a = 13%.
Using the same argument we used to prove the second case of (c) in Lemma 3.2.2, it
is easy to verify that the algorithm will take the Dk_1 so constructed and map it to
D], by unorienting a since c(Dk_1) — a has an additional sink at w .

In the subcase where e = uw is present in D], as an unoriented edge and we would
still retain prOperty (c) with either orientation of e, we will consider the digraph Dk_1
obtained from D by giving 6 the normal orientation, say a = 27715. It is clear that the
algorithm maps Dk_1 to D1,, since Dk_1 + a’ = D1,, is acyclic and a has the normal

orientation. I

CHAPTER 4

Results on e-positivity

4. 1 Inducing e7r

We now turn our attention to the expansion of Y0 in terms of the elementary sym-
metric function basis. We recall that for any fixed 1r 6 IL, we use 7r + (d+ 1) to denote
the partition of [d + 1] formed by inserting the element (d + 1) into the block of 7r
which contains d. We will denote the block of 7r which contains d by B,,. We also let
7r/d + 1 be the partition of [d + 1] formed by adding the block {(1 + 1} to 7r.

In order obtain information about the coefficients for the expansion of Y0 in non-
commutative elementary symmetric functions using our deletion-contraction results,
it is necessary for us to understand the coefficients arising in e,r T. We have seen
that the expression for ewT is rather complicated (see equation (3.1)). However, if
the terms in the expression of enT are grouped properly, the coefficients in many of
the groups will sum to zero. To see that such a grouping should exist, we use the

following lemma.

Lemma 4.1.1 For 7r 6 11¢, let esz Z: CTeT. Then

76 r1«1+1

41

42

1/|B,,| if /\('r) = /\(7r/d+1),
Z 0.: —1/|B,.| if/\(r)=)\(7r+(d+1)),

Tend-H

A(T)fixed 0 8188.

Proof. Let 7r : Bl/Bg/ . . . /B,,/ . . . /B,c E Iln. We also let b,- denote the size of

the block 8,. We may now consider the graphs on d + 1 vertices given by
GwZKB,EHKBQEHH'HZWKB,+6)EH°"L+JKBk,

where K B, is the complete graph on b, vertices labeled with the elements of Bi, and
where K 3,, + e is the complete graph on b,r dr‘if b vertices labeled with the elements
of B, which also contains an additional vertex labeled (1 + 1, and an additional edge
from d to d + 1.

By the recurrence relation for Ya, we can see that Y0, = YG”_8 - Yaw/8T. Equiv-
alently, this gives us that YG,/eT= Ya”-.. — YG,- It is easy to see that YGt/e = e,” and
so this gives us that eWTz Y0”-.. — YG,- If we let G be the operator which allows the
variables to commute, we get C(ewT) = XG,_e -— X0".

We now proceed to calculate XGFC and X0". Since it is easy to see that G,r — e 2
K3, EH KB, ha - - ° t6 K13,r H5 K{d+1} Lu - - - t6 K3,, we may use the product rule for XG to

show that XG,__e = 7r!e(,\(,r),1). To calculate X0, we again will use the product rule,

together with the fact that

XKB, = Z: (Ml/Wm)”

Al—d-l—l

where a,\ is the number of stable partitions of the vertex set of K B. of type A. Letting
u = A(Bl/Bg/ - - - /B3,/ - - - /Bk), we can easily count the number of stable partitions

of K B. to obtain the equation

43

X0, = uleu [(b —1)(b — 1)!m(1b—1,2) + (b +1)!m(1b+1)] .

We may then use the fact that ”bub—1’2) = e<b,1)—- (b+1)e(b+1) and mum) = 6“,“),

combining this with the previous results to obtain:
C(BWT)= 714804701) - ,uleu [(b —1)(b —l)l(€(b,1)—(b +1)6(b+1)) + (b +1)!e(b+1)] .

Following simplification, this leads to

7r d+1 ! 7r+ d+1 !
L/_b_)-e()‘(7r)’l) — ( (b )) eA(7r+(d+1))- (4.1)

 

C(ewT) =

This essentially completes the proof, as we know that if en: 2 C167, then

Tend“

C()=€.T Z W ()6.

Tenn-+1

Hence we can see that

E c, T!

Tend“
A(T) fixed

is the coefficient of 8W) in C(eWT). Putting this together with equation (4.1) gives

the result. I

This lemma show us that the coefficients of various terms from an can be com-
bined in a nice way and even indicates exactly how to do so. We need to sum together
the coefficients from set partitions which are of the same type (as integer partitions),
and whose block containing d have the same size. If we do this, then almost all
these amalgamated coefficients will drop out. We need to know, however, if there

is a pattern to these combinations which will allow us to repeatedly use deletion-

44

contraction techniques. We see that the contributing coefficients of e,,T will have type
A(7r + (d + 1)) or A(ir/d + 1). If we want to be able to repeat this process, though, it
will be necessary to know the size of the block of enT which contains (1 + 1. We want
all those terms of an which do not have type A(7r + (d + 1)) or A(ir/d + 1), and whose
block containing at + 1 is not the same size as the block containing d + 1 in 7r + (d + 1)
or 7r / d + 1 to drOp out. With one more bit of notation, we may show this is indeed
the way the coefficients will behave. Let P(a) = P(a1, 012, . .. ,Oq) be the set of all
partitions of [d + 1] which are less than or equal to 7r + (d + 1), have blocks of size
ahaz, . .. ,al, and for which d + 1 is in a block of size al. The proper grouping of

the terms of eWT is given by the following lemma.

Lemma 4.1.2 If e7r T = Z creT, then c, = 0 unless r 3 7r +(d+1), and for
Tend-H

any a l- (d+ 1), we have

1/IB.I ifP(a)={7r/d+1},
Z c.-- —1/|B,.| ifP(a)={7r+(d+1)},

rEP(a)
0 else.

Proof. Fix 7r 6 H4. By equation (3.1)

 

en: 2 ”(0’0) 2 n(r, a + (d +1))e,.

as" u(0,a+(d+1)) 730%,“)

Hence we may express

en: E 6.6.,

TS1T+(d+1)

where for any fixed 1' 3 7r + (d + 1) we have

—1
c. = Z l—B_I“ (7,0 + (d+1)). (4.2)
a+(f1§-I)ZT

45

We first note that if T = 7r/d+1 E P(a), then |P(a)| = 1 and we have the interval
[7,7r + (d + 1)] g H2. A simple direct computation shows that cfl/dH = 1/|B,,|.
Similarly, ifr = 7r +(d+1) E P(a), then again |P(a)| = 1 and we can easily compute
C1r+(d+l) = -1/|B‘rr]-

We now fix 7 = Bl/Bg/°"/Bq+2/°"/B( E P(a) such that |B,-| = a,- for all
1 g i g l. For q 2 —1, we let 81,82, - - - ,Bq+2 be the blocks of T which are contained
in BMW“). For notational convenience, we will also let |B,,+(d+1)| = m + 1, where
m _>_ 1. Finally let fl denote the partition obtained from r by merging the blocks of
T which contain d and d + 1, allowing [3 = r if d and d + 1 are in the same block of

r. Replacing a + (d + 1) by a E IId+1 in equation (4.2), we see that

 

—1
CT: 2: lBa|_1#(T,0').

fiSaSn+(d+l)
Now for any B Q [d + 1] we will consider the sets

L(B)={o€lld+1:{d,d+1}§B€o, wherefigogr+(d+1)}.

The nonempty L(B) partition the interval [5, it + (d + 1)] according to the content of

the block containing {d, d + 1} and so we may express

 

—1
01:; IBl—l 2 ”(7,0)

o€L(B)

To compute the inner sum, we need to consider the following 2 cases.
Case 1) For some k > q + 2, 8,. is strictly contained in a block of 7r + (d + 1).

In this case, we see that each non-empty L(B) forms a non-trivial cross-section of a

46

product of partition lattices, and so for this case

2 p.(,)7'0’ )20.

a€L( B()
Thus partitions in this case will not contribute to 2 c7.
TEP(a)

Case 2) For all k > q+2, Bk is a block of7r+ (d+1). In this case, we have q 2 0,

since otherwise we must have T = 7r+ (d+ 1) which we have already considered. Then

we can show
__ q+1 , _
QLRM If B : Bir+(d+1)
a€L(B)

0 else.

(4.3)

It is easy to see that if B 2 BMW“) then L(B) = {7r+(d+1)} and so that part is
clear. Also, if B = B,,+(d+1)\B,- for some 2 S i S q+2, then we have L(B) ӎ H1 and
so ZUELU?) n(T, o) = (—1)"q!. 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 {d,d + 1} C B, the second case in (4.3) will only occur if

d E Bj for j 79 i . So adding up all these contributions gives

 

q+2
1 q+1
T=_1qv ________
c ( )q §m_ai m
i¢j

In order to compute the sum over all T E P(a), it will be convenient to consider

all possible choices for the block of T containing d. So for T 3 7r + (d + 1) and

47

1_<_j£q+2,let

P(C¥,j) = {(B1,Bg,... ,B() I Bl/Bg/H./B( E P(C¥),d€ Bj}.

The sequence (Bl, B2, . . .

aj—l Ifj=1

 

6, :
Otj else,
so
m —1
P a, . = .
I ( j)| (61,...,6j—1,...,6q+2)
Thus we can see that
2
m—l ) (1+ 1
2: CT:( (—1)qq! Z
T€P(a,j) 61,co.,6j_1,...,6q+2 :;§m_ai

,Bg) is called an ordered set partition. Also define

_‘I_+_1
m

To obtain the sum over all T E P(a) we need to sum over all P(a, j) for 1 S j S q+2.

However, for 1 S r g m + 1, if we let k, be the number of blocks 3,, 1 S i S q + 2

which have size r, then in the sum over all P(a, j), each T E P(a) appears 113:1] kr!

times. Combining all this information, we see that

 

 

Z _ (-1)"q! (if m—l “if 1 _q+1
CT_Hm+1kl. 61... 6—1... 6 2 . m—(S m
T€P(a) r=l 7‘ 3:1 ’ ’ J ’ 1 11+ 2.:2‘ z
1963
Hence it suffices to show that
§( m _1 ) (If: 1 — q H 0
j=1 61,...,5j—1,...,(5q+2 i—2m_6' m '

48

Using the multinomial recurrence,

q+2
2( H m >
, 5,,...,5,—1,...,5,+2 5,,...,5,,...,5,,2’

1:1

we need only show that

if m—l 3‘: 1 _q+1 m
, 61,...,(5j—1,...,6q+2 , m—6,_ m 61,...,6j,...,6q+2 .

 

 

 

 

 

     

 

 

 

 

1:1 i=2
#1
However, we may express
q+2 q+2 q+2 m , (1+2
2( m — 1 ) Z 1 _ (61,...,6j,...,6q+2)61 Z 1
j=1 61,...,(Sj—1,...,6q+2 {am—6,. j=l m izzm—bi
#2 iii
( )q+2 q+2
_ 515q+2)
j=1 i: 2m
#1
( m ) q+2 q+2
_ 61 6; 6q+2 1 (S
— m m — 6 J
i=2 ‘ j=1
#i
( m (1+2
61 .,6 ,....5 +2) 2 1
= J Q (m 6')
m , m — 61

4.2 Some e-positivity Results

We wish to use this result 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, Ya is usually

not 6— positive. The only graphs which are obviously e—positive are the complete

 

 

49

graphs on n vertices, for which we have YKn = em], and their complements, which
yield Y?" = e1/2/.../,,. Even paths, with the vertices labeled sequentially, are not
e—positive, for we can compute that Yp3 = %€12/3 — %el3/2 + 'é'81/23 + %8123. However,
in this example we can notice that while Y]:3 is not e-positive, if we group the terms
according to their type and the size of the block which contains 3, the sum of these
coefficients will be non-negative.

This observation along with the proof of the previous lemma inspires us to define
equivalence classes reflecting the sets P(a). That is, if the block of 0 containing i is

B0,, and the block of T containing i is B”, we define
a E,- T iff A(o) = /\(T) and IBM] 2 Wm]-
In a similar manner, we can define
eazieTiffoE,T

and let (T) and em denote the equivalence classes of T and 6, respectively. We can

take formal sums of these equivalence classes and write expressions such as

2 eye” E,- Z C(r)e(r) where em = 2 ca.

06114 (Tlgld ”E(T)

We will refer to this equivalence relation as congruence modulo i.

Using this notation, we have Yp3 E3 %e(12/3) + §e<123), since 813/2 53 61/23. We will
say that a labeled graph G (and similarly YG) is (e)— positive if cm is non-negative for
all (T) g IId under some labeling of G and suitably chosen congruence. We notice that
the expression of YG for a labeled graph G may have all non-negative amalgamated
coefficients for congruence modulo i, but not for congruence modulo j, making the

definition for (e)-positivity seem to depend on the labeling of the graph. However,

50

the (e)-positivity of a graph is in fact not dependent on the labeling of the graph.
If a different labeling for an (e)-positive graph is chosen, then we need only change
the congruence class appropriately, to again see the (e)-positivity. This should be
clear from the Relabeling Proposition. That is, if 7(G) = H for some '7 such that
7(i) = j, and Ya E,- 2mg,“ cmem, then YH E,- 2mg” c(7(7))e(,(,)). So if G is
(e)-positive modulo i, then H is seen to be (e)-positive modulo j. Hence relabeling a
graph does not change its (e)-positivity. 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 4.1.2, the roles played by the elements at and

~

d+ 1 are essentially interchangeable. That is, if we let P(a) be the set of all partitions

of [d+ 1] which are less than or equal to 7r + (d+1), have blocks of size 011, . . . ,a; and

for which d is in a block of size a1, and let it E Hd be the partition 71 with d replaced

by d + 1, then the same proof will show that

l/lerl if Pia) = {if/d},

~

20; -1/|B«| ifP(a)={7“r+(d)}.
TEP(O)
0 else.

Note that here fr + (d) is the partition obtained from fr by inserting the element d

into the block of ii containing at + 1. This allows us to state a corollary in terms of

the congruence relationship just defined.

Corollary 4.2.1 For 7T 6 Ed,

_ 1 1
€nT=d+1 38(1r/d+1) - 36(1r+(d+1))

51

and

CnTZd Sew/d) - 36(7'r+(d))’

where b: |B,,|. I

The next lemma simply verifies that the induction operation respects the congru-

ence relation and should be clear without proof.

Lemma 4.2.2 Ify Ed T, then 67T2d+1 6,. I

From this we can extend induction to congruence classes in a well-defined manner:

600‘]: Z cmem if and only if en: 2 cTeT.
(Tlgnd+l TEHd+1
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 hope of obtaining a simpler (e)-positive graph. In order to see how

this procedure will affect Ya, we use the following lemma.

Lemma 4.2.3 Given a graph, G on d vertices define H = GErJKm. If Y0 = Z coed,

0611,,

then YH = E Caea/d+1,d+2,...,d+m-
0611,,

Proof. From previous statements it follows that

Y}; = Yaqm]

= Z: caeaqm]

06114

= E Coed/d+1,d+2,...,d+m-
dead

The result above naturally suggests that we use the notation G / vd+1 for the graph

GU{ud+1}. We are now in a position to prove the (e)-positivity of paths.

52
Proposition 4.2.4 For all d 2 1, Ypd is (e)—positiue.

Proof. We proceed by induction, having labeled Pd so that E(Pd) =
{v1v2,v2v3,... ,ud_1vd}. If d = 1, then we have Yp, = el and the proposition is
clearly true.

So we assume by induction that

YP. Ed 2 Gwen),
(7)6111:

where cm 2 0 for all (T) 6 11d. From our deletion-contraction recurrence, Corollary

4.2.1 and Lemma 4.2.3, we see that using e 2 mod“,

YPd+1 : YPd/vd+l — YPdT
Ed.“ 2 C(T)e(T/d+1) _ Z C(T)e(T)T
(agnd (7)914
1 C(T)
Ed+l Z (1 — m) C(r)e(T/d+1) + Z WBUHHID'
(ecu. T (”End T

Since we know that cm 2 O, and |BT| 2 1 for all T, this completes the induction
step and the proof. I
In the commutative context we will say that the symmetric function X0 is 6-
positive if all the coefficients in the expansion of the elementary symmetric functions
are non-negative. It is easy to see that we can use the (e)-positivity result for Ypd

and specialize it to show the e-positivity of X pd.

Corollary 4.2.5 X]:d is e—positiue. I

It is then natural to ask if cycles will also be (e)—positive, for when we delete an

edge of a cycle we obtain a path. While it is true that cycles will be (e)—positive,

53

a stronger relationship exists between paths and cycles. In fact, it turns out that
the coefficients in the (e)-expansion of paths will appear again as the coefficients in
the (e)-expansion of cycles with only a slight modification. For labeling purposes,

however, we will need the following lemma which follows easily from the Relabeling

Proposition.
Lemma 4.2.6 Ify 6 8d fixes d, then Y,(G) Ed Ya.

Proposition 4.2.7 For all d 2 2, if

YR, Ed ZOMBm, then Yo“, Ed+1 ZC(T)6(T+(d+l))7

where we have labeled the graphs so E(Pd) = {v1u2, v2u3, . .. ,vd_1vd} and E(Cd+1) =

{111112, 712713, - -- Wat—1714, vdvd+1a vd+lvll°

Proof. We proceed by induction on d. If d = 2, then Yp2 2 cm and Y0, = em,

and so the proposition holds for d = 2.

For the induction step, we assume that
Ya.-. Eat—1 2 Como
and also that

You Ed 2 C<r)6(r+(d))-

We notice that if e 2 mod“, then Cd+1 —— e does not have the standard labeling for

paths. But if we let 7 = (d+ 1)(1,d)(2,d — 1) - - - ([d—gl] , [134]) then we can use the

deletion—contraction recurrence to get

Y0.“ = WP...) — YCdT -

54

From our opening observation, since (1 + 1 is a fixed point for 7, this allows us to

deduce that

YCd-H Edi-1 YPd+1 _ YCdT '

In the proof of PrOposition 4.2.4 we saw that

YPd-H = YPd/vd-H — YPdT '

Combining these two equations gives

Yo,“ E(1+1 YPd/vd+1 — YPdT —YCdT - (4-4)

The demonstration of Proposition 4.2.4 also showed us that

 

C T
YPd :61 Z ((W T) ( lB)l) E(T/d)+ IBT —|C()‘8(T+(d))) (4‘5)

(T)

Applying Corollary 4.2.1 and Lemma 4.2.3 yields

_ C(T) C(T)

Cm C(r) ]

+ (B l(lBTl+1)e(T+(d)/d+l)_ (BTKIB l+ 1)e(r+(d )+(d+1))

 

 

and

_ 2: cm C< (r)
YPd/vdH =d+1 (0(1) + —]B l)8 e(r+(d)/d+1) _ '8 ——|'8(r/d, ,d+1)
(r) 7

respectively. By the induction hypothesis,

YCdT E(1+1 ZC(T)€(T+(d))T
(T)

541; ‘i—(T) ddl —c(—T)—€ ddl-
+ IBT—|—_—+1(e(_T+()/+) IBT|+1(T+()+(+))

55

Plugging these expressions for YPd/d'l'l’ YpdT, and chT into equation (4.4), grouping

the terms according to type, and simplifying gives

_ 6(7) C( )
Yo,H1 =d+1 2: (0(1) - Tia—l) e(T/d,d+l) + 'I‘BT—e(r+(d)+(d+l))-

(r) 7'

This corresponds to the expression in equation (4.5) for Ypd in exactly the desired
manner, and so we are done.

Since we know that Ypd_l is (e)—positive, for all d 2 3, we have an immediate

corollary.
Proposition 4.2.8 For all d 2 3, Yea, is (e)—positive. I
If we allow the variables to commute again, we can specialize to X0,-

Corollary 4.2.9 For all d 2 1, Xcd is e—positiue. I

We are also able to use our recurrence to show the (e)-positivity of complete

graphs with one edge removed.
Proposition 4.2.10 For d 2 2, ife = vd_1vd then

_ d — 2 1
Yin—e =d 31—16(11) + d __ lead—1w)-

 

Proof. Consider the complete graph K; and apply deletion-contraction to the edge

e = vd_1vd. Together with Corollary 4.2.1 this will give us

56

61d] = YK.

 

1
Ed YKre — flew-1W) + d _ 18([d])-

Simplifying gives the result. I

This also immediately specializes.

Corollary 4.2.11 For at Z 2,

XKd—e : d(d — 2)(d —‘ 2)!€d + (d —‘ 2)l€(d_1,1).

4.3 The (3+1)-free Conjecture

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 graph obtained from P where the edges
of G (P) are {up : u and v are incomparable as elements of P}. Then the (3+1)-free

Conjecture of Stanley and Stembridge [17] may be stated.
If P is (3+1)-free, then XGUJ) is e-positive.

A subset of the (3+1)-free graphs is the class of indifierence graphs. They are

57

characterized [16] as having vertices and edges

V = [n], and E = {uv : u,u belong to some I E C},

where C is a collection of intervals [i, j] = {i,i + 1, . . . , j} g [n]. We note that without

loss of generality, we can assume no interval in the collection is properly contained in
any other. These graphs are both (3+1)-free and (2+2)-free.

Indifference graphs have a nice structure suitable for our deletion-contraction tech-
niques. That is, if G is an indifference graph on n vertices with at least one edge,
then it is not hard to see that there is an edge (e = uhvn where [h,n] is the “last”
interval in the collection) for which both G — e and G /e are indifference graphs.
Thus we may inductively assume the (e)-positivity of indifference graphs with fewer
edges than G, and use deletion-contraction to obtain indifference graphs with fewer
edges. Unfortunately, the relationship between the coefficients in the (e)-expansion
of Yg-e and YG/e T is not entirely clear, so we have not been able to make this
method work on all indifference graphs. However, we are able to resolve a special
case. For any composition (ordered integer partition) of n, A = (A1, A2,. . ,Ak), let
A,- = 21.9. A,. A K; — chain is the indifference graph using the collection of intervals
{[1, A1], [A1, A2], . .. ,[Ak~_1, A),]}. This is just a string of complete graphs, whose sizes
are given by the parts of A, which are attached to one another sequentially at single
vertices. We notice that the K A-chain for A = (A1, A2, . .. ,Ak) can be obtained from
the KT-chain for T = (A1, A2, . . . ,Ak_1) by attaching the graph K), to its last vertex.

We will be able to handle this type of attachment for any graph G with vertices

{221,112, . .. ,vd}. Hence, we define G + Km to be the graph with

V(G + Km) = V(G) U {Ud+1,. . . ,vd+m_1}

58

and

E(G+Km) =E(G)U{e=u,u,-:i,j E [d,d+m+1]}.

Using deletion-contraction techniques, we are able to obtain information about the
(e)-expansion of G + Km in terms of the coefficients in the (e)-expansion of G. How-
ever, we will also need some more notation. For T E l'Id, we let 7r +i denote the
partition given by T with the additional i elements d + 1, d + 2,... ,d + i added to
B,,. This is in contrast to 7r + (i), which denotes the partition given by 1r with the

element i inserted into B7,. Finally, we follow Stanley in denoting the falling factorial

by

and the rising factorial by

(b),d§fb(b+1)~-(b+i—1).

We begin with a short study of the behavior of YG+KmTZ+j by proving the following

lemma.

Lemma 4.3.1 [fl 3 j < k g m, then YG+Kng+jEd YG+Km g“ .

Proof. For any partition, T of [d + m — 1],, define 6d+j(7r) to be the partition
0 obtained by inserting the element (1 + j into the block of 7r containing d, and
adding one to each element of T which is at least d + j. It should be easy to see
that mwTj‘sz m5 .1 +1.0,). Similarly, mnTSH‘: m5d+k(,,). Now consider the permutation
'y = (d+j,d+k,d+k—1,d+k—2, . . . ,d+j+1). We can see that yo(m,,Tj+j) = mag” .
This implies that y o (YG+KmTj+j) = YG+Kng+k . Noticing that d is a fixed point of

y, and so Lemma 4.2.6 applies will complete the proof. I

 

59

Lemma 4.3.2 If G is a graph on d vertices with

then

-1
d+m__ m C(1r)<m — 1)i [8(1r+i/d+i+1,...,d+m) _ e(1r+i+(d+m)/d+i+1,... ,d+m—1)]
ya... =...§j :
(1r) i=0 (b)i+1

where b = [8,].

Proof. We prove the lemma by induction on m. The case m = 1 is merely a
restatement of Corollary 4.2.1. So we may assume this lemma is true for YG+Kng+m,
and proceed to prove it for Ya+xm+1TZ+m+1 .

From Lemma 4.3.1, it follows that for 1 S j S m, we have

d+' d 1_ d d 1
YG+Kde JTd+m+ =d+m+l YG+Kde+de+m+ -

Now, from G +Km+1 we may delete the edge set {vdud+,~ : 1 S j S m} and combine

all the terms YGTZHTg‘LmH for 1 S j g m to obtain

d+m+1 _ d+m+1 d+m d+m+1
Yam,"+1 d =d+m+1 YGme d -mYG+Km d d
_ d+m+1 d+m d+m+1
=d+m+1 YGuKm d “ml/04.x... 4 (pm

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 4.1.2, Lemma

4.2.3 and the original hypothesis on Ya, that

C 7,)
YGme g+m+15d+m+l E: —(b" (6(1r1) — e(1r2)) ° (46)
(W)

’

 

60

where
T1=7r/d+1,... ,d+m/d+m+1,

r2=7r+(d+m+1)/d+1,... ,d+m.

Similarly, the induction hypothesis shows

 

c m(m - 1),- e — e e — 6
ml/ d+m d+m+1E E :§ : (7T)( (W3) (W4) _ ("5) (We)
G+Kde Td+m d+m+1 m i: 0 b)i+1 m _ i b + i + 1

where
7r3=rr+i/d+i+1,... ,d+m/d+m+1,

7r4=7r+i/d+i+1,...,d+m+1,
7r5=7r+i+(d+m)/d+i+1,... ,d+m—1/d+m+1,

T6=7r+i+(d+m)+(d+m+1)/d+i+1,...,d+m—1.

Simplifying the terms and combining both previous equations (4.6) and (4.7) gives

Y d+m+1:
G+Km+1 d —d+m+1

c 8m) — 5(1r2) m—l (8(7r3) — BUM) (m),- (e(7r5) - E(H)) (”1),-+1
Z "' (— 2 (b)... + 2 (b)... ) '

(7.) i=0 i=0

 

 

Note that modulo d+m+ 1 we have
(7T5): (n+i+1/d+i+2,... ,d+m/d+m+1) and

(7T6) = (7r+i+1+(d+m+1)/d+i+2,...,d+m).

 

61

So by shifting indices and simplifying, we obtain

d+m+1—
YG+Km+1Td =d+m+1

,

Z Em: C(1r)<m)i [6(1r+i/d+i+1,... ,d+m+l) — e(7r+i+(d+m+1)/d+i+l,... ,d+m)]
(bk-+1

(7r) i=0
which completes the induction step and the proof. I

This lemma is useful because it helps us to find an explicit formula for YG+Km+,
in terms of Y3. Once we have the formula, it will be easy to verify that if G is
(e)-positive, then so is G + Km“. For the induction step in establishing this explicit

formula, we will need the following observation.

Lemma 4.3.3 For any graph G on (1 vertices, and (i,j) 6 8d, then
YGTEHIEdH Y(i,j)(G)T;l+1 .

Proof: For any 7r 6 H4, we see directly from the definitions for induction and

the symmetric group action that

(233') 0 (771mm) = ”Marl?“ -
From this it follows that

(231') ° (YGTS‘+1) = Yuaxmlifl -

Since d + 1 is a fixed point of (i, j), Lemma 4.2.6 gives the result. I

We may now give the formula for YG+ K... H in terms of Y0.

62

Lemma 4.3.4 Ifm 2 1, and

Ya Ed 2 C(n)8(n),
("End

then

 

m—l
c 7. (m - 1).- . .
YG+Km+l Ed+m E E ( )(b)- [(b — m + Z)e(fi-) + (Z +1)€(7f)]
(«>914 i=0 ”+1

where b = [3,], and
Tr=7r+i/d+i+1,... ,d+m,

f=rr+i+(d+m)/d+i+1,... ,d+m—1.

Proof. We induct on m. If m = 1, then YG+K2 = YGwK, — YGTZ+1 . This shows

that

c (b — 1) c ,,
YG+K2 Ed+1 2: (Lb—_ehr/d+1) + %e(r+(d+1))) a
(7')

which verifies the base case.

To begin the induction step, we repeatedly utilize the deletion-contraction recur-

rence to delete the edges ud+,vd+m+1 for 0 S i S m, and obtain

YG+Km+2 Ed+m+1 YG+Km+1wvd+m+1 — mYG+Km+1Tgim+1 —YG+K,.,+1 3m“ - (4-8)
Note that we are able to combine all the terms from YG+Km+1TZ::n+1 together by the
previous observation, Lemma 4.3.3 since for all 1 g i g m there is a permutation
satisfying the correct conditions.

We now expand each of the terms in equation (4.8). For the first, using Lemma

4.2.3,

 

m-l
C 71’ (m _ 1>i . .
YG+Km+lwvd+m+1 Ed+m+1 Z Z ( )(b)'+1 [(b _ m + z)e(1r1) + (2 +1)e(1r2)] a
(w) i=0 '

 

63

where
T1=T+i/d+i+1,... ,d+m/d+m+1,

T227r+i+(d+m)/d+i+1,... ,d+m—1/d+m+1, and

For the second term, using Corollary 4.2.1, we have

+1..
mYG+Km+1Td+m+ :d+m+l

 

C(W)( (771),.“ b— m+t _ i+1 _
(2) m:- (b) )1+1 [ (60“) E(H)) + b + ’i + 1 (6(172) 6(7T4l)

m—Z
(7r) i=0

where
7r3=7r+i/d+i+1,... ,d+m+1, and

7T4=7r+i+(d+m)+(d+m+1)/d+i+1,... ,d+m—1.

And finally, using Lemma 4.3.2,

Cn)<
YG+Km+1Td+m+ l=d+m+1 22:76—- —(_—‘) e(_7r3) 60%))

(1r) i=0 b)i+l
where

7r5=7r+i+(d+m+1)/d+i+1,...,d+m.

Grouping the terms appropriately and shifting indices where needed we have mas-

sive cancellation, which yields

 

m c,r (m),- (b—(m+1)+i)e,r +(z‘+1)e,r
YG+Km+2 Ed+m+1 z: ( ) l (b)- ( 3) ( 5)].
(1r) i=0 1+1

This completes the induction step and the proof. I

Examining this lemma, we can see that in YG+Km+1 we have the same sign on

all the coefficients as we had in Y6, with the possible exception of the terms where

64

b< m — i. But it is easy to see that in this case we have

e(7r+i/d+i+1,...,d+m) Ed+m e(1r+m—i—lc—1+(d+m)/d+m—i—k,...,d+m—1)-

This means that in the expression for YG+ K... H as a sum over congruence classes mod-

ulo d + m, we can combine the coefficients on these terms. And so upon simplification,

the coefficient on e(,,+,-/d+,-+1P_.,d+m) will be:

 

(k — m + Z)<m _1>i (m -" Z — k)(m _1>m—i—k—1
( (k),+1 + (klm—i—k ) Cm,

where cm is the coefficient on em in Y0.
Adding these fractions by finding a common denominator, we see that this coef-

ficient is actually zero. corresponding This gives us the next result.

Theorem 4.3.5 If Ya is (e)-positive, then Your", is also (e)-positive. I

Notice that Proposition 4.2.4 follows easily from Theorem 4.3.5 and induction,

since for paths Pm+1 = Pm + K2. As a more general result we have the following

Corollary.
Corollary 4.3.6 If G is a KA-chain, then YG is (e)-positive. Hence, X0 is also

e-positive. I

We can also describe another class of (e)-positive graphs. We define a diamond
to be the indifference graph on the collection of intervals {[1, 3], [2,4]}. So a diamond

consists of two K 3’s sharing a common edge. Then the following holds.
Theorem 4.3.7 Let D be a diamond. IfG 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. We note that if G is a graph on d vertices, then we can think of G + D as

65

G with the additional vertices ud+1,ud+2,vd+3, and new edges constructed from the

intervals {[d, d + 2], [d + 1, d + 3]}. If we now delete and contract the edges ud+1vd+3

and vd+2vd+3, we see (using the apprOpriate symmetry) that

YG+D E(1+3 YG+K3s{d+3} — 2YG+K3T313 - (49)

By Lemma 4.3.4, if YG Ed Somem then
(T)

_ b—2 b—l 1 2
Yo+K3 =d+2 2%) Teen) + Ween) + gem) + mew.) .

(1r)
where
7T1=7T/d+1,d+2,
W2=7T+(d+1)/d+2,
mzuw+w+ayd+L
7r, =7r+(d+1)+(d+2),

b = |B,,|.
So by Corollary 4.2.1,

b—2 b—l
YG+K3T$igzd+3 E036”) [(W) (eh-n) — 80(1)) + ‘71));— (e(7'r2) _ 6&9)

1 2
+ (72—2) (eons) — 6W) + @ (em) _ 6650)]

where fr,- = n,/d+ 3, and 71;: T.- + (d+ 3).

Using Lemma 4.2.3 and plugging these equations into (4.9), we have

 

 

2e,-r b—2e,,l 2b—1e,,g 2e,“ 4e“:
[(<o +( )<n+ ( )<.)+ (a,_<.q_

YG+D E(1+3 260') b+ 1)2 b (b)2 ((9)2 (b)3

(T)

It should be clear that all these coefficients will be non-negative, provided that

the case b = 1 works out. But if b = 1, then we have 7r’1 —:—'d+3 T3. Hence the coefficient

 

66

on 6W1) is 9% + (,)—2);, which is zero for b =1. I

CHAPTER 5

Open Problems and Conjectures

5.1 Partitioning Acyclic Orientations

In this chapter we conclude with a few Open problems, and some philosophical ram-
blings on how one might attempt to answer them using our inductive machinery.
Some of these problems were first discussed in Stanley’s paper [15], and remain open

at this point. We begin with an approach to the (3+l)-free conjecture suggested by

Timothy Chow [3].
In the commutative setting, we know that if X0 = :cAeA, then
Al-n

Z c; = the number of acyclic orientations of G with j sinks.

l(A)=J'
This suggests that to show X0 is e-positive, we could partition the set of acyclic
orientations of G with j sinks into subsets so that each subset has cardinality c,\. For
each such orientation, Tim’s idea is to partition the vertices into V(G) = w{:1I/,- so
that |V,-| = A,- and each subset V,- contains exactly one sink of the orientation, labeled
1),. This vertex partition is formed as follows. We begin by placing each 22,- into V,.
For any other vertex, u, we place u in V} if there are paths originating from u which

terminate at the sinks 1),-wk, . .. ,1)”, and i = min{i,k, . .. ,m}.

67

68

This procedure works very nicely on paths, but to understand why it works, we need
the following Corollary to Theorem 4.2.4. We notice first that for any representative

T of (T), it is well-defined to take (T)! 2 Ti.

Corollary 5.1.1 If Ypd= Z CTe, :01 Z c ((,)e (T), then

Tend (T)Cl'ld

T!C(T) = IB—rl H (IBI — 1)

BET-Br
for every (T) Q Hd.

Proof. The proof is by induction (what else?). For our base case, Yp, = em is
enough to show the result holds. If we assume the induction hypothesis for Pd, then

from equation (4.4, we have

_ |B | - 1 0(1)
Yam =d+1 20(1) (—|TB—|— €(r/d+1) + 2 [B |e(r+(d+1))'
(r) T (r) T

Examining the coefficients in this expression based on our induction hypothesis and

then simplifying, we see that

B, —1 B
(T/d+1)!C(T)I——l—=CTIBr| II (IBI—1)'———— ' =c.H(IBI—1)

IBTI BET-B,- IBTII BET

and

 

C.
(r+(d+1))I—" = (IB.I+1)IB.I | I (lBl—l) — -.. (IB |+1) (IBl—l)
IBI IE I
" BET-B Ber—B.

This completes the induction step and the proof. I

Note that this expression for em automatically shows that it is non-negative,
but we can also use it to verify that Chow’s algorithm works for Pd. From the

congruence relationship, we see that (T) can be expressed as (1,2,. . . ,bl / b1 + 1, b1 +

69

122 v3

. v

Figure 5.1. The graphs G, H, and I

2, . . . ,b2/ . . . /bk_1 +1, . . . ,d). Given a partition, we need to see that there are exactly
[BTI User—B. (|B] — 1) orientations which the algorithm will map to (T). (Note that
all orientations of a path must be acyclic.) We notice that vb, could not be a sink
for any such orientation of Pd. If it were, then the existence of m would force
the algorithm to put both vb,“ and vb, into the same block, which was not the case.
Similarly v12, . .. ,vb,_, are also not candidates for sinks of such an orientation, but
vd is. This gives us [Bl] — 1 possibilities for the first sink, [B2] — 1 for the second,
etc., until we reach the last sink, for which we have |B,| choices. It is not hard to
see that each of these possibilities actually does give us an appropriate orientation
for the paths, and verifies the algorithm works in this case.

In order to see the algorithm’s failure to hold in general, as well as show the
promise for the existence of a modification, we consider the graphs G, H, and I given
in Figure 5.1.

For both the graphs G and H , the algorithm produces exactly the correct subset
partitions.

. 2 1
X0 = 1684 + 28(3,1), Whlle YG E4 36(141) + §€(123/4).

 

70

The partitions we obtain from the algorithm for G are [4] which occurs 16 times and

123/4, which occurs twice.
. 1 1
XH = 6085 + 126(4’1), Whlle YH E5 58([5D + "2‘€(1234/5).

The partitions we obtain for H are [5] which occurs 60 times and 1234/5, which occurs
12 times. We notice that not only do we have the correct number of partitions of a
given type, but we even have the partitions obtained matching the congruence classes.
That is, for G the algorithm only produces the partition 123 / 4 having type (3,1), just
as it only produces the partition 1234/ 5 for H. When we do the calculations for I,

however, the algorithm doesn’t produce the desired results. That is,

. 1 1 1 1
X1 = 2065 + 12801,1) + 4€(3,2) Whlle Y! 55 68([5])+3e(1/2345) + 66(1234/5) + 36(123/45).

In this case the algorithm produces [5] 20 times as expected, however the partition
1 / 2345 is produced 4 times, 1234/ 5 occurs 4 times, and 123/ 45 occurs 8 times. This
is not the desired outcome, for we want 12 of the type (4,1) and only 4 of the type
(3, 2). However, if we look closely at the coefficients in Y, we see that by taking 7r!c(,,)
we should get the numbers 20, 8, 4 and 4 just as we have, except these numbers are
not associated with the desired partitions. While this shows that there is indeed an
intimate relationship between the coefficients of Y1 and this algorithm, it is not clear

how to modify this algorithm to produce the correct associated partitions.

5.2 X0 and Trees

We will end with a note on one of the more interesting unsolved problems posed by

Stanley. We feel that our method has some promise in approaching this problem, but

have been unable to make it work so far.

 

71

 

T1 T2 T3
”U4
’03
c c c t a
v
v1 v2 v3 v4 v5 v1 v2 v3 1 v2 v4
’05
vs

Figure 5.2. The trees T1, T2, and T3.

We begin by noticing that if T is a tree on d vertices, we have XT(n) = n(n—1)d‘1.
Since X0 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 d = 9 [3] that XG will distinguish non-isomorphic

trees. This leads to the following question posed by Stanley, which I will give as a

conjecure.
Conjecture 5.2.1 [15] X0 distinguishes non-isomorphic trees.

To illustrate how we believe this problem may be approached using our deletion-
contraction techniques, we will consider the case d = 5, where the three different trees

labeled as in Figure 5.2. For these trees, we have the symmetric functions:

72

X7) = P5 — 2P(4,1) — 2P(3,2) + 3P(3,12) + 3P(22,1) — 4P(2,13) + P05)

YT1 E5 P(12345) — P(1/2345) — P(1234/5) — P(12/345) — P(123/45) + P(1/2/345)
+219(123/4/5) + 219(1/23/45) + P(12/34/5) — P(1/2/3/45) " 3P(12/3/4/5) + P(1/2/3/4/5)

XT2 = P5 — 3P(4,1) ‘- P(3,2) + 4P(3,12) + 2P(22,1) “ 4P(2,13) + P(15)

Y1} Es P(12345) — 2P(1/2345) - P(1234/5) — P(12/345) + 2P(1/2/345) + 219(123/4/5)
+P(12/34/5) + P(1/23/45) - 3P(12/3/4/5) — P(1/2/3/45) + P(1/2/3/4/5)

XT3 = P5 — 4P(4,1) + 6P(3,1’2) — 4P(2,13) + P(15)

YT3 E5 P(12345) - 3190/2345) — P(1234/5) + 3P(123/4/5) 'l' 3P(1/2/345)

"3P(12/3/4/5) - P(1/2/3/45) + P(1/2/3/4/5)-

We can see here that the XT, are distinct, as are the YT“ with respect to the
congruence relation. It is much more surprising that the XT, are distinct, however,

since it is easy to show the following proposition.

Proposition 5.2.2 For any graph G on d vertices with no loops or multiple edges,

YG is unique.

Proof. We know from equation (2.5) that YG = 2,, mm») for the stable parti-
tions P. Construct the graph H with vertex set V(G) = {v1,v2, . .. ,vd} and edge
set E(H) = {vivJ-I there exists a 7r(P) such that i, j are in the same block of 7r(P)}.
Since 7r(P) comes from a stable partition P of G, v,- and v, are in the same block of
some 7r(P) if and only if there is no edge viv, in G. Hence the graph H constructed

is the (edge) complement of G and so we can recover G from H. I.

From this proposition it is trivially true that YG distinguishes trees. It does not,
however, follow that YG will distinguish trees with respect to equivalence classes. It is
easy to see that this will be the case up to d = 8, since it is true for X a, but we need to

go further. It seems reasonable to expect to prove this using our deletion-contraction

 

73

techniques, since trees are reconstructible from their leaf-deleted subgraphs [9]. We
proceed in the following manner.

If T1 33 T2 then by the reconstructibility of trees there must exist labelings of
these trees so that vd is a leaf of T1, 1), is a leaf of T2 and T1 — vd 93 T2 — 5,. By
induction we will have YT1-vd $0M er—nd, and consequently, YT,_,,d id er—ad- Hence,
our recurrence gives us

YT1 = YTl—vd/vd - YTl—vdl
YT2 = er—ad/ad - er—adl -

We believe that from this relationship, we should be able to show that with respect
to the congruence classes, YG distinguishes non-isomorphic trees. However, even
though in the expansion of YT, = YT,_,, .1 )v d — YT,_,,d T we have terms from both
YT,_,,d/,,d and YT,_,,dT which do not match those from YT,_,~,d/,-,d and Yrs—5,1, we have
been unable to prove that the differences do not cancel out. Further, even if we
were able to show that with respect to congruence classes YT, $4 YT2, this does not

necessarily imply that XT, 7E XT2. We h0pe to overcome these difficulties in future

research.

BIBLIOGRAPHY

BIBLIOGRAPHY

[1] A. Blass and B. Sagan, Bijective proofs of two broken circuit theorems, J. Graph

Theory 10 (1986), 15-21.

[2] T. Chow, Symmetric Function Generalizations of Graph Polynomials, Ph.D. the-

sis, Massachusetts Institute of Technology, 1995.

[3] T. Chow, personal communication.

[4] P. Doubilet, On the Foundations of Combinatorial Theory. VII: Symmetric Func-

l5]

[6]

[7]

[9]

tions through the Theory of Distribution and Occupancy, Studies in Applied Math.
51 (1972), 377-396.

V. Gasharov, Incomparability graphs of (3+1)-free posets are s-positive, Discrete
Math. 157 (1996), 193—197

I. M. Gelfand, D. Krob, A. Lascoux, B. Leclerc, V. Retakh, J .-I. Thibon, Non-

commutative symmetric functions, preprint, 1994.

C. Greene and T. Zaslavsky, On the interpretation of Whitney numbers through
arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations
of graphs, Trans. Amer. Math. Soc. 280 (1983), 97-126.

D. Gebhard, Noncommutative symmetric functions and the chromatic polynomial,
Conference Proceedings at the 7th International Conference on Formal Power Se-

ries and Algebraic Combinatorics, Université de Marne-la-Vallée 1995.

F. Harary and E. Palmer, The reconstruction of a tree from its maximal subtrees,
Ganad. J. Math, 18 (1966), 803-810.

[10] I. G. Macdonald, “Symmetric Functions and Hall Polynomials,” Oxford Univer-

sity Press, Oxford, 1979.

74

75

[11] F. S. Roberts, From garbage to rainbows: Generalizations of graph coloring
and their applications, in “Graph Theory, Combinatorics, and Applications: Pro-
ceedings of the Sixth Quadrennial International Conference on the Theory and
Application of Graphs,” vol. 2, Y. Alavi, B. Chartrand, O. R. Oellermann, A. J.
Schwenk eds., pp. 1031-1052, John Wiley & Sons, Inc., New York, 1991.

[12] B. E. Sagan, “The Symmetric Group: Representations, Combinatorial Algo-
rithms, and Symmetric Functions,” Wadsworth & Brooks/Cole, Pacific Grove,
CA, 1991.

[13] R. P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171-178.

[14] R. P. Stanley, “Enumerative Combinatorics,” vol. 1, Wadsworth & Brooks/ Cole,
Pacific Grove, CA, 1986.

[15] R. P. Stanley, A symmetric function generalization of the chromatic polynomial
of a graph, Advances in Math. 111 (1995), 166-194.

[16] R. P. Stanley, Graph colorings and related symmetric functions: ideas and ap-
plications, preprint.

[17] R. P. Stanley and .I. Stembridge, On immanants of Jacobi-TIudi matrices and
permutations with restricted position, J. Combin. Theory (A) 62 (1993), 261-279.

[18] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J.
Math. 6 (1953), 80—91.

[19] H. Whitney, A logical expansion in mathematics, Bull. Amer. Mth. Soc. 38
(1932),572—579.

[20] T. Zaslavsky, Signed graphs, Discrete Applied Math. 4 (1982), 47-74.
[21] T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982), 215-228.

[22] T. Zaslavsky, Chromatic invariants of signed graphs, Discrete Math. 42 (1982),
287-312.

"‘((11))in)“