Computation -- Sage

def B(n,k): if 0<=k and k<=n: return binomial(n,k) return 0 def f(i,v,r): return min([2*ceil(i/(v-2*r)),2*ceil((r-i)/(v-2*r))+1]) def E(i,j,v,r): return sum([(-1)^t*B(j,t)*B(r-j,i-t)*B(v-r-j,i-t) for t in [0..j]]) def Kneser(v,r): #d = ceil((r-1)/(v-2*r))+1 evals=[] for j in [0..r]: evals.append((sum([f(i,v,r)*E(i,j,v,r) for i in [0..r]]),(v-2*j+1)*B(v,j)/(v-j+1))) return evals

html('') for r in [2..6]: for n in [(2*r+1)..17]: K = Kneser(n,r) K.sort() K.reverse() T = graphs.KneserGraph(n,r).distance_matrix().eigenvalues(extend=False) L = [] for t in set(T): L.append((t,T.count(t))) L.sort() L.reverse() print "Kneser graph with n = "+str(n)+" and r = "+str(r) print "\t",K print "\t",L

Kneser graph with n = 5 and r = 2
	[(15, 1), (0, 4), (-3, 5)]
	[(15, 1), (0, 4), (-3, 5)]
Kneser graph with n = 6 and r = 2
	[(22, 1), (1, 5), (-3, 9)]
	[(22, 1), (1, 5), (-3, 9)]
Kneser graph with n = 7 and r = 2
	[(30, 1), (2, 6), (-3, 14)]
	[(30, 1), (2, 6), (-3, 14)]
Kneser graph with n = 8 and r = 2
	[(39, 1), (3, 7), (-3, 20)]
	[(39, 1), (3, 7), (-3, 20)]
Kneser graph with n = 9 and r = 2
	[(49, 1), (4, 8), (-3, 27)]
	[(49, 1), (4, 8), (-3, 27)]
Kneser graph with n = 10 and r = 2
	[(60, 1), (5, 9), (-3, 35)]
	[(60, 1), (5, 9), (-3, 35)]
Kneser graph with n = 11 and r = 2
	[(72, 1), (6, 10), (-3, 44)]
	[(72, 1), (6, 10), (-3, 44)]
Kneser graph with n = 12 and r = 2
	[(85, 1), (7, 11), (-3, 54)]
	[(85, 1), (7, 11), (-3, 54)]
Kneser graph with n = 13 and r = 2
	[(99, 1), (8, 12), (-3, 65)]
	[(99, 1), (8, 12), (-3, 65)]
Kneser graph with n = 14 and r = 2
	[(114, 1), (9, 13), (-3, 77)]
	[(114, 1), (9, 13), (-3, 77)]
Kneser graph with n = 15 and r = 2
	[(130, 1), (10, 14), (-3, 90)]
	[(130, 1), (10, 14), (-3, 90)]
Kneser graph with n = 16 and r = 2
	[(147, 1), (11, 15), (-3, 104)]
	[(147, 1), (11, 15), (-3, 104)]
Kneser graph with n = 17 and r = 2
	[(165, 1), (12, 16), (-3, 119)]
	[(165, 1), (12, 16), (-3, 119)]
Kneser graph with n = 7 and r = 3
	[(82, 1), (2, 14), (-2, 6), (-7, 14)]
	[(82, 1), (2, 14), (-2, 6), (-7, 14)]
Kneser graph with n = 8 and r = 3
	[(100, 1), (4, 7), (-1, 28), (-5, 20)]
	[(100, 1), (4, 7), (-1, 28), (-5, 20)]
Kneser graph with n = 9 and r = 3
	[(146, 1), (8, 8), (-1, 48), (-6, 27)]
	[(146, 1), (8, 8), (-1, 48), (-6, 27)]
Kneser graph with n = 10 and r = 3
	[(203, 1), (13, 9), (-1, 75), (-7, 35)]
	[(203, 1), (13, 9), (-1, 75), (-7, 35)]
Kneser graph with n = 11 and r = 3
	[(272, 1), (19, 10), (-1, 110), (-8, 44)]
	[(272, 1), (19, 10), (-1, 110), (-8, 44)]
Kneser graph with n = 12 and r = 3
	[(354, 1), (26, 11), (-1, 154), (-9, 54)]
	[(354, 1), (26, 11), (-1, 154), (-9, 54)]
Kneser graph with n = 13 and r = 3
	[(450, 1), (34, 12), (-1, 208), (-10, 65)]
	[(450, 1), (34, 12), (-1, 208), (-10, 65)]
Kneser graph with n = 14 and r = 3
	[(561, 1), (43, 13), (-1, 273), (-11, 77)]
	[(561, 1), (43, 13), (-1, 273), (-11, 77)]
Kneser graph with n = 15 and r = 3
	[(688, 1), (53, 14), (-1, 350), (-12, 90)]
	[(688, 1), (53, 14), (-1, 350), (-12, 90)]
Kneser graph with n = 16 and r = 3
	[(832, 1), (64, 15), (-1, 440), (-13, 104)]
	[(832, 1), (64, 15), (-1, 440), (-13, 104)]
Kneser graph with n = 17 and r = 3
	[(994, 1), (76, 16), (-1, 544), (-14, 119)]
	[(994, 1), (76, 16), (-1, 544), (-14, 119)]
Kneser graph with n = 9 and r = 4
	[(405, 1), (5, 42), (0, 8), (-1, 48), (-21, 27)]
	[(405, 1), (5, 42), (0, 8), (-1, 48), (-21, 27)]
Kneser graph with n = 10 and r = 4
	[(483, 1), (9, 75), (-7, 90), (-12, 35), (-12, 9)]
	[(483, 1), (9, 75), (-7, 90), (-12, 44)]
Kneser graph with n = 11 and r = 4
	[(623, 1), (18, 10), (2, 110), (-3, 165), (-12, 44)]
	[(623, 1), (18, 10), (2, 110), (-3, 165), (-12, 44)]
Kneser graph with n = 12 and r = 4
	[(918, 1), (33, 11), (3, 154), (-3, 275), (-17, 54)]
	[(918, 1), (33, 11), (3, 154), (-3, 275), (-17, 54)]
Kneser graph with n = 13 and r = 4
	[(1302, 1), (54, 12), (4, 208), (-3, 429), (-23, 65)]
	[(1302, 1), (54, 12), (4, 208), (-3, 429), (-23, 65)]
Kneser graph with n = 14 and r = 4
	[(1790, 1), (82, 13), (5, 273), (-3, 637), (-30, 77)]
	[(1790, 1), (82, 13), (5, 273), (-3, 637), (-30, 77)]
Kneser graph with n = 15 and r = 4
	[(2398, 1), (118, 14), (6, 350), (-3, 910), (-38, 90)]
	[(2398, 1), (118, 14), (6, 350), (-3, 910), (-38, 90)]
Kneser graph with n = 16 and r = 4
	[(3143, 1), (163, 15), (7, 440), (-3, 1260), (-47, 104)]
	[(3143, 1), (163, 15), (7, 440), (-3, 1260), (-47, 104)]
Traceback (click to the left of this block for traceback)
...
__SAGE__

Kneser graph with n = 5 and r = 2
	[(15, 1), (0, 4), (-3, 5)]
	[(15, 1), (0, 4), (-3, 5)]
Kneser graph with n = 6 and r = 2
	[(22, 1), (1, 5), (-3, 9)]
	[(22, 1), (1, 5), (-3, 9)]
Kneser graph with n = 7 and r = 2
	[(30, 1), (2, 6), (-3, 14)]
	[(30, 1), (2, 6), (-3, 14)]
Kneser graph with n = 8 and r = 2
	[(39, 1), (3, 7), (-3, 20)]
	[(39, 1), (3, 7), (-3, 20)]
Kneser graph with n = 9 and r = 2
	[(49, 1), (4, 8), (-3, 27)]
	[(49, 1), (4, 8), (-3, 27)]
Kneser graph with n = 10 and r = 2
	[(60, 1), (5, 9), (-3, 35)]
	[(60, 1), (5, 9), (-3, 35)]
Kneser graph with n = 11 and r = 2
	[(72, 1), (6, 10), (-3, 44)]
	[(72, 1), (6, 10), (-3, 44)]
Kneser graph with n = 12 and r = 2
	[(85, 1), (7, 11), (-3, 54)]
	[(85, 1), (7, 11), (-3, 54)]
Kneser graph with n = 13 and r = 2
	[(99, 1), (8, 12), (-3, 65)]
	[(99, 1), (8, 12), (-3, 65)]
Kneser graph with n = 14 and r = 2
	[(114, 1), (9, 13), (-3, 77)]
	[(114, 1), (9, 13), (-3, 77)]
Kneser graph with n = 15 and r = 2
	[(130, 1), (10, 14), (-3, 90)]
	[(130, 1), (10, 14), (-3, 90)]
Kneser graph with n = 16 and r = 2
	[(147, 1), (11, 15), (-3, 104)]
	[(147, 1), (11, 15), (-3, 104)]
Kneser graph with n = 17 and r = 2
	[(165, 1), (12, 16), (-3, 119)]
	[(165, 1), (12, 16), (-3, 119)]
Kneser graph with n = 7 and r = 3
	[(82, 1), (2, 14), (-2, 6), (-7, 14)]
	[(82, 1), (2, 14), (-2, 6), (-7, 14)]
Kneser graph with n = 8 and r = 3
	[(100, 1), (4, 7), (-1, 28), (-5, 20)]
	[(100, 1), (4, 7), (-1, 28), (-5, 20)]
Kneser graph with n = 9 and r = 3
	[(146, 1), (8, 8), (-1, 48), (-6, 27)]
	[(146, 1), (8, 8), (-1, 48), (-6, 27)]
Kneser graph with n = 10 and r = 3
	[(203, 1), (13, 9), (-1, 75), (-7, 35)]
	[(203, 1), (13, 9), (-1, 75), (-7, 35)]
Kneser graph with n = 11 and r = 3
	[(272, 1), (19, 10), (-1, 110), (-8, 44)]
	[(272, 1), (19, 10), (-1, 110), (-8, 44)]
Kneser graph with n = 12 and r = 3
	[(354, 1), (26, 11), (-1, 154), (-9, 54)]
	[(354, 1), (26, 11), (-1, 154), (-9, 54)]
Kneser graph with n = 13 and r = 3
	[(450, 1), (34, 12), (-1, 208), (-10, 65)]
	[(450, 1), (34, 12), (-1, 208), (-10, 65)]
Kneser graph with n = 14 and r = 3
	[(561, 1), (43, 13), (-1, 273), (-11, 77)]
	[(561, 1), (43, 13), (-1, 273), (-11, 77)]
Kneser graph with n = 15 and r = 3
	[(688, 1), (53, 14), (-1, 350), (-12, 90)]
	[(688, 1), (53, 14), (-1, 350), (-12, 90)]
Kneser graph with n = 16 and r = 3
	[(832, 1), (64, 15), (-1, 440), (-13, 104)]
	[(832, 1), (64, 15), (-1, 440), (-13, 104)]
Kneser graph with n = 17 and r = 3
	[(994, 1), (76, 16), (-1, 544), (-14, 119)]
	[(994, 1), (76, 16), (-1, 544), (-14, 119)]
Kneser graph with n = 9 and r = 4
	[(405, 1), (5, 42), (0, 8), (-1, 48), (-21, 27)]
	[(405, 1), (5, 42), (0, 8), (-1, 48), (-21, 27)]
Kneser graph with n = 10 and r = 4
	[(483, 1), (9, 75), (-7, 90), (-12, 35), (-12, 9)]
	[(483, 1), (9, 75), (-7, 90), (-12, 44)]
Kneser graph with n = 11 and r = 4
	[(623, 1), (18, 10), (2, 110), (-3, 165), (-12, 44)]
	[(623, 1), (18, 10), (2, 110), (-3, 165), (-12, 44)]
Kneser graph with n = 12 and r = 4
	[(918, 1), (33, 11), (3, 154), (-3, 275), (-17, 54)]
	[(918, 1), (33, 11), (3, 154), (-3, 275), (-17, 54)]
Kneser graph with n = 13 and r = 4
	[(1302, 1), (54, 12), (4, 208), (-3, 429), (-23, 65)]
	[(1302, 1), (54, 12), (4, 208), (-3, 429), (-23, 65)]
Kneser graph with n = 14 and r = 4
	[(1790, 1), (82, 13), (5, 273), (-3, 637), (-30, 77)]
	[(1790, 1), (82, 13), (5, 273), (-3, 637), (-30, 77)]
Kneser graph with n = 15 and r = 4
	[(2398, 1), (118, 14), (6, 350), (-3, 910), (-38, 90)]
	[(2398, 1), (118, 14), (6, 350), (-3, 910), (-38, 90)]
Kneser graph with n = 16 and r = 4
	[(3143, 1), (163, 15), (7, 440), (-3, 1260), (-47, 104)]
	[(3143, 1), (163, 15), (7, 440), (-3, 1260), (-47, 104)]
^CTraceback (most recent call last):            T = graphs.KneserGraph(n,r).distance_matrix().eigenvalues(extend=False)
  File "", line 1, in <module>
    
  File "/tmp/tmpY_3eNY/___code___.py", line 4, in <module>
    exec compile(u'for r in (ellipsis_range(_sage_const_2 ,Ellipsis,_sage_const_6 )):\n    for n in (ellipsis_range((_sage_const_2 *r+_sage_const_1 ),Ellipsis,_sage_const_17 )):\n        K = Kneser(n,r)\n        K.sort()\n        K.reverse()\n        T = graphs.KneserGraph(n,r).distance_matrix().eigenvalues(extend=False)\n        L = []\n        for t in set(T):\n            L.append((t,T.count(t)))\n        L.sort()\n        L.reverse()\n        print "Kneser graph with n = "+str(n)+" and r = "+str(r)\n        print "\\t",K\n        print "\\t",L
  File "", line 6, in <module>
    
  File "/home/sage/build/sage-6.2/local/lib/python2.7/site-packages/sage/graphs/generators/families.py", line 125, in KneserGraph
    g.add_edge(s,t)
  File "/home/sage/build/sage-6.2/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 9037, in add_edge
    if not self.allows_loops() and u==v:
  File "/home/sage/build/sage-6.2/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 1932, in allows_loops
    return self._backend.loops(None)
  File "c_lib.pyx", line 176, in sage.ext.c_lib.sage_python_check_interrupt (sage/ext/c_lib.c:1696)
  File "c_lib.pyx", line 73, in sage.ext.c_lib.sig_raise_exception (sage/ext/c_lib.c:872)
KeyboardInterrupt
__SAGE__

K = Kneser(8,3) K.sort() K.reverse() K

[(100, 1), (4, 7), (-1, 28), (-5, 20)]

[(100, 1), (4, 7), (-1, 28), (-5, 20)]

T = graphs.KneserGraph(8,3).distance_matrix().eigenvalues(extend=False) L = [] for t in set(T): L.append((t,T.count(t))) L.sort() L.reverse() L

[(100, 1), (4, 7), (-1, 28), (-5, 20)]

[(100, 1), (4, 7), (-1, 28), (-5, 20)]

Computation

3188 days ago by butler