4712.sagews

# Katherine Edwards and Andrew D. King
# Bounding the fractional chromatic number of K_Delta-free graphs
# Supplemental material: computations
#
# This script gives, for a given Delta >= 6, an epsilon such that a
# K_Delta-free graph with maximum degree Delta has fractional
# chromatic number at most Delta-epsilon.

# USER INPUT: VALUE OF DELTA

Delta = 6   #Set choice of Delta.

omega = Delta-1


#Compute p(Delta,d) for d = 0, 1, ..., Delta
p = [0] * (Delta+1)
for d in range(0,Delta+1):
    total = 0
    for i in range(4):
        total += (4-i) * binomial(d,i) * ((omega-4)/(omega))^(d-i) * ((4/omega)^(i))
    total = total/4 #probability of candidacy (no neighbours in $S_\omega$).
    p[d] = total/(Delta+1-d) #p(Delta,d) = probability of selection (being in $S$).


#Set muk = mu_k(Delta)
muk = [0] * (Delta+1)
for k in range(0,Delta+1):
    muk[k] = min(p[0:k+1])

#Set mu = mu(Delta) = mu_Delta(Delta)
mu = muk[Delta]

#Compute tyk = $\tilde y_k(Delta)$ for k=1, 2, ... Delta-2
tyk = [0] * (Delta-1)
for k in range(1,4): #k = 1, 2, 3
    tyk[k] = (1/2)*(Delta-1-k) / ( (1/2) + mu - (1/2)*(k*mu) )
for k in range(4,Delta-1): #k = 4, ... , Delta-2
    tyk[k] = (1/2)*(Delta-1-k) / ( (1/2) + mu - (1/2)*(k*muk[Delta+1-k]) )

#Compute $\tilde y(Delta)$
ty = min(min(tyk[1:Delta-1]),omega-3)

#Compute our final epsilon.
epsilon = ty * mu


print 'For Delta  = ',Delta
print '  Epsilon  = ',epsilon
print '           = ',1.0*epsilon
print '          ~=  1 /',1.0/epsilon

For Delta = 6 Epsilon = 153/3431 = 0.0445934129991256 ~= 1 / 22.4248366013072