This worksheet contains data and computations related to the article "On distinguishing trees by their chromatic symmetric functions", by Jeremy L. Martin, Matthew Morin, and Jennifer D. Wagner (arXiv:math.CO/0609339), henceforth [MMW]. It was last modified by Jeremy L. Martin on 5/16/07 and may be freely used and shared for any noncommercial research purpose.Load Maple's combinat package and John Stembridge's SF package, freely available at http://www.math.lsa.umich.edu/~jrs/maple.html#SFwith(combinat):
read("/home/jmartin/maple/SF2.4v.txt"): ## you will presumably need to change the location of the file!
withSF():Convert a list of integers to a power-sum symmetric functionP := lambda -> mul(cat(p,kk),kk=lambda):Define the monomial symmetric functionsdual_basis(m,h):The number y (l, i, j) defined in [MMW]psi := proc(lambda,a,b)
option remember:
local n,kk,ell:
ell := nops(lambda):
n := add(kk,kk=lambda):
binomial(ell-1,ell-n+a+b) *
add( binomial(lambda[kk]-1,a),kk=1..ell ):
end:The symmetric function Q = Q(n) whose scalar product with X(T) is the connector polynomial of T.(This is called Y instead of Q in [MMW], but Maple reserves the symbol Y for something else.)Theta := proc(n)
option remember:
expand(add(add( (-1)^(a+b)*'x'^a*'y'^b *
add(psi(lambda,a,b) * P(lambda)/zee(lambda), lambda=Par(n)),
b=0..n-1),a=1..n-1))
end:Conjecture 6 of [MMW] (the "positivity conjecture") states that (-1)(number of even parts of l) y (l, i, j) >= 0 for all l, i, j.
Conjecture 7 of [MMW] (the "integrality conjecture") states that zl y (l, i, j) is an integer for all l, i, j. The following loop verifies these conjectures for small n ; I have run it for n <= 17. The outer loop runs over n (the number of vertices), and the inner loop over all partitions l of n. The algorithm extracts the coefficient of l in Q(n) by taking the scalar product with ml (the dual basis to the hl ). The first counterexample to each conjecture is printed out, and all counterexamples are recorded in the lists NonPositiveLambdas, NonIntegralLambdas. The time to check each n seems to be O(2n ). On my computer (a Dell Precision 370 running Maple under Linux), it took about 17 minutes (just over 1000 seconds) to check the case n = 17.NonPositiveLambdas := []:
NonIntegralLambdas := []:
n := 2:
while true do
## while n <= 17 do
## you can change the value of 17 if desired
tm := time():
T := toh(Theta(n)):
for lambda in Par(n) do
xi := scalar(Theta(n), m[op(lambda)]):
EvenParts := 0: for i in lambda do if type(i,even) then EvenParts := EvenParts + 1 fi od:
if not type((-1)^EvenParts*xi, polynom(positive)) then
NonPositiveLambdas := [op(NonPositiveLambdas), lambda]:
if NonPositiveLambdas=[] then print("Positivity Conjecture fails for ",lambda) fi
fi:
if not type(zee(lambda)*xi, polynom(integer)) then
NonIntegralLambdas := [op(NonIntegralLambdas), lambda]:
if NonIntegralLambdas=[] then print("Integrality Conjecture fails for ",lambda) fi
fi:
od:
print(n,time()-tm,' seconds'): ## keep track of time
n := n+1:
od:
NonPositiveLambdas;
NonIntegralLambdas;