IBM - Personal communication

This web page contains a table of the independence numbers of Paley graphs for graphs of size less than 7000. The first column is the size of the Paley graph, the second column is the independence number and the third column is the time in seconds my program required to compute the independence number. For some definitions and related material see my paper Lower Bounds for Small Diagonal Ramsey Numbers .

         P      I(G(P))      Compute time
        13         3            0.000007                                        
        17         3            0.000007                                        
        29         4            0.000009                                        
        37         4            0.000011                                        
        41         5            0.000011                                        
        53         5            0.000015                                        
        61         5            0.000019                                        
        73         5            0.000025                                        
        89         5            0.000037                                        
        97         6            0.000038                                        
       101         5            0.000033                                        
       109         6            0.000065                                        
       113         7            0.000050                                        
       137         7            0.000120                                        
       149         7            0.000103                                        
       157         7            0.000147                                        
       173         8            0.000185                                        
       181         7            0.000224                                        
       193         7            0.000290                                        
       197         8            0.000143                                        
       229         9            0.000347                                        
       233         7            0.000602                                        
       241         7            0.000732                                        
       257         7            0.000864                                        
       269         8            0.000484                                        
       277         8            0.000887                                        
       281         7            0.000752                                        
       293         8            0.000978                                        
       313         8            0.001793                                        
       317         9            0.001500                                        
       337         9            0.001334                                        
       349         9            0.000749                                        
       353         9            0.002125                                        
       373         8            0.002208                                        
       389         9            0.001775                                        
       397         9            0.002170                                        
       401         9            0.002111                                        
       409         9            0.002106                                        
       421         9            0.004104                                        
       433        11            0.002067                                        
       449         9            0.003862                                        
       457        11            0.002235                                        
       461        11            0.003928                                        
       509         9            0.005487                                        
       521         9            0.009585                                        
       541        11            0.004708                                        
       557        11            0.009513                                        
       569         9            0.016556                                        
       577        10            0.005372                                        
       593        11            0.004671                                        
       601        11            0.005425                                        
       613        12            0.009734                                        
       617        11            0.006137                                        
       641        11            0.020892                                        
       653        11            0.008248                                        
       661        11            0.022175                                        
       673        11            0.019888                                        
       677        11            0.019734                                        
       701        10            0.015739                                        
       709        10            0.034223                                        
       733        11            0.051571                                        
       757        11            0.026281                                        
       761        11            0.013380                                        
       769        11            0.057141                                        
       773        11            0.030352                                        
       797         9            0.084038                                        
       809        11            0.045653                                        
       821        12            0.039114                                        
       829        11            0.034601                                        
       853        13            0.022427                                        
       857        13            0.055505                                        
       877        13            0.053422                                        
       881        11            0.047707                                        
       929        13            0.048097                                        
       937        11            0.081391                                        
       941        11            0.086923                                        
       953        11            0.074663                                        
       977        13            0.088209                                        
       997        13            0.057973                                        
      1009        11            0.150143                                        
      1013        11            0.186595                                        
      1021        11            0.208893                                        
      1033        11            0.214028                                        
      1049        11            0.183206                                        
      1061        12            0.160141                                        
      1069        12            0.086815                                        
      1093        12            0.228292                                        
      1097        12            0.135008                                        
      1109        11            0.375034                                        
      1117        12            0.270319                                        
      1129        13            0.177004                                        
      1153        13            0.355548                                        
      1181        12            0.364227                                        
      1193        11            0.229219                                        
      1201        13            0.153348                                        
      1213        13            0.385951                                        
      1217        13            0.385859                                        
      1229        12            0.368887                                        
      1237        13            0.119625                                        
      1249        13            0.184837                                        
      1277        11            0.985318                                        
      1289        15            0.276777                                        
      1297        13            0.445316                                        
      1301        13            0.210889                                        
      1321        13            0.264771                                        
      1361        12            0.984924                                        
      1373        14            0.593265                                        
      1381        12            0.963412                                        
      1409        13            0.459101                                        
      1429        13            0.523972                                        
      1433        13            1.142867                                        
      1453        12            0.725411                                        
      1481        15            0.501307                                        
      1489        13            1.476071                                        
      1493        12            0.933219                                        
      1549        13            1.717272                                        
      1553        13            1.354756                                        
      1597        13            1.353653                                        
      1601        13            1.478373                                        
      1609        13            1.169198                                        
      1613        14            0.438527                                        
      1621        13            2.505310                                        
      1637        13            2.124091                                        
      1657        13            2.402308                                        
      1669        13            2.090278                                        
      1693        14            1.945108                                        
      1697        13            1.298699                                        
      1709        13            1.541647                                        
      1721        13            2.387255                                        
      1733        13            1.720724                                        
      1741        17            0.686220                                        
      1753        13            1.743254                                        
      1777        15            0.763413                                        
      1789        13            1.168310                                        
      1801        14            1.340100                                        
      1861        13            5.474797                                        
      1873        13            4.516053                                        
      1877        15            2.941568                                        
      1889        15            0.666935                                        
      1901        14            3.832357                                        
      1913        15            2.856852                                        
      1933        13            4.554835                                        
      1949        14            1.699544                                        
      1973        13            3.637919                                        
      1993        13            4.595217                                        
      1997        14            2.540470                                        
      2017        13            7.596363                                        
      2029        14            2.171696                                        
      2053        13            3.744369                                        
      2069        14            3.979653                                        
      2081        14            3.200946                                        
      2089        14            3.434666                                        
      2113        13            5.017495                                        
      2129        13            4.638498                                        
      2137        13            7.053780                                        
      2141        13            8.996544                                        
      2153        13            5.862014                                        
      2161        17            3.253700                                        
      2213        15            3.093256                                        
      2221        15            2.848334                                        
      2237        13            8.739523                                        
      2269        14            9.434536                                        
      2273        15            3.558563                                        
      2281        17            1.287725                                        
      2293        15            2.738433                                        
      2297        15            8.065717                                        
      2309        15            6.551955                                        
      2333        14            6.335688                                        
      2341        13           16.091866                                        
      2357        15           11.946546                                        
      2377        13           14.079785                                        
      2381        13           25.010178                                        
      2389        16            4.865674                                        
      2393        14           18.669997                                        
      2417        15           12.416451                                        
      2437        15           10.890214                                        
      2441        14           15.866624                                        
      2473        14           19.938588                                        
      2477        15           14.280774                                        
      2521        15           14.174413                                        
      2549        15            6.334592                                        
      2557        15           10.532561                                        
      2593        13           38.559454                                        
      2609        15           24.960383                                        
      2617        15           30.454765                                        
      2621        16            5.649500                                        
      2633        15           20.874122                                        
      2657        15           24.426053                                        
      2677        15           13.954597                                        
      2689        17           14.446509                                        
      2693        16            9.644279                                        
      2713        15           28.441826                                        
      2729        19            2.618208                                        
      2741        13           38.519333                                        
      2749        15           12.836313                                        
      2753        15           11.210253                                        
      2777        15           38.143524                                        
      2789        15           22.066494                                        
      2797        15           30.775191                                        
      2801        14           47.120004                                        
      2833        15           14.991742                                        
      2837        15           15.880804                                        
      2857        15           43.360516                                        
      2861        16           22.271826                                        
      2897        15           14.088529                                        
      2909        15           58.160507                                        
      2917        15           39.513078                                        
      2953        15           25.042091                                        
      2957        15           22.312524                                        
      2969        17           14.299944                                        
      3001        17           43.112469                                        
      3037        16           42.156233                                        
      3041        15           91.165062                                        
      3049        16           54.985819                                        
      3061        15           89.569896                                        
      3089        15           73.562767                                        
      3109        15           77.951441                                        
      3121        15           71.437270                                        
      3137        17           18.893293                                        
      3169        19           15.208318                                        
      3181        16           77.447867                                        
      3209        15           47.123829                                        
      3217        17           42.959340                                        
      3221        16           29.315167                                        
      3229        15          110.638680                                        
      3253        16           61.397669                                        
      3257        15           96.693266                                        
      3301        17           67.422031                                        
      3313        17           32.157069                                        
      3329        15           60.862807                                        
      3361        17           17.301038                                        
      3373        15           47.560711                                        
      3389        15          102.601171                                        
      3413        15           65.349836                                        
      3433        17           32.566060                                        
      3449        15           59.725850                                        
      3457        17           80.374357                                        
      3461        16          117.611192                                        
      3469        17           60.255806                                        
      3517        17           36.465540                                        
      3529        19           18.291067                                        
      3533        16           90.225348                                        
      3541        15          133.701601                                        
      3557        17           81.583647                                        
      3581        17           46.768318                                        
      3593        16          127.906172                                        
      3613        15          193.974084                                        
      3617        17           82.179805                                        
      3637        16          177.227322                                        
      3673        19           47.330734                                        
      3677        15          125.006894                                        
      3697        15          214.241735                                        
      3701        17           54.188442                                        
      3709        16          196.507414                                        
      3733        17           59.141275                                        
      3761        17           80.127531                                        
      3769        17           86.886251                                        
      3793        17          174.679481                                        
      3797        17           49.898096                                        
      3821        17          234.925174                                        
      3833        19           91.573525                                        
      3853        15          309.739387                                        
      3877        16           88.356253                                        
      3881        17          236.937520                                        
      3889        17           86.418935                                        
      3917        17          208.995221                                        
      3929        19           94.322855                                        
      3989        16          321.176847                                        
      4001        17          158.129269                                        
      4013        15          221.335041                                        
      4021        16          350.624034                                        
      4049        17          123.475066                                        
      4057        17           95.676238                                        
      4073        17           82.513800                                        
      4093        15          531.699791                                        
      4129        17          212.068500                                        
      4133        16          436.828083                                        
      4153        17          140.551218                                        
      4157        17          305.599743                                        
      4177        17          118.311222                                        
      4201        17          324.029508                                        
      4217        15          332.032256                                        
      4229        17          225.792990                                        
      4241        17          166.980902                                        
      4253        16          230.540834                                        
      4261        17          367.650757                                        
      4273        17          245.352831                                        
      4289        17          429.944562                                        
      4297        17          551.510878                                        
      4337        17          160.760985                                        
      4349        17          167.164567                                        
      4357        17          125.499862                                        
      4373        17          388.400173                                        
      4397        17          290.753925                                        
      4409        17          491.425883                                        
      4421        17          508.484897                                        
      4441        15          652.696527                                        
      4457        15          622.196858                                        
      4481        17          525.356566                                        
      4493        19          407.034832                                        
      4513        17          393.121655                                        
      4517        17          660.825287                                        
      4549        17          670.463904                                        
      4561        17          651.830974                                        
      4597        17          371.946932                                        
      4621        17          770.248782                                        
      4637        17          971.181135                                        
      4649        17          454.350578                                        
      4657        17          375.762366                                        
      4673        17          690.943064                                        
      4721        17          324.084560                                        
      4729        17          285.336186                                        
      4733        17          460.404880                                        
      4789        17         1123.879110                                        
      4793        16          561.733008                                        
      4801        19          454.407240                                        
      4813        17          486.628880                                        
      4817        17          985.273473                                        
      4861        18          303.699549                                        
      4877        17          399.737197                                        
      4889        19          455.799284                                        
      4909        17          387.931275                                        
      4933        17          779.367855                                        
      4937        17          995.304878                                        
      4957        17          582.158323                                        
      4969        17          450.793464                                        
      4973        17          635.263253                                        
      4993        17          649.512720                                        
      5009        18          452.040643                                        
      5021        16         1699.930703                                        
      5077        19         1039.649479                                        
      5081        17         1728.411815                                        
      5101        17         1334.500731                                        
      5113        19          289.765951                                        
      5153        17          510.318298                                        
      5189        17          638.578261                                        
      5197        16         1978.801436                                        
      5209        19          315.253774                                        
      5233        17         1330.902767                                        
      5237        18          950.256062                                        
      5261        17         1464.873822                                        
      5273        21          691.491310                                        
      5281        17         1389.458136                                        
      5297        17         1171.860088                                        
      5309        17         2187.538571                                        
      5333        17          999.891795                                        
      5381        18         1732.441370                                        
      5393        17         2361.278046                                        
      5413        18          869.170992                                        
      5417        19          725.675949                                        
      5437        17          972.540526                                        
      5441        17         2152.385514                                        
      5449        17         1363.437785                                        
      5477        17          980.855529                                        
      5501        16         1834.078119                                        
      5521        19          476.460763                                        
      5557        17         1904.292306                                        
      5569        18         1161.662621                                        
      5573        19         1340.567765                                        
      5581        17         1038.393086                                        
      5641        19         1912.572846                                        
      5653        17         3956.425758                                        
      5657        18         1253.345864                                        
      5669        17         3448.368779                                        
      5689        19         1499.865191                                        
      5693        17         3736.500569                                        
      5701        17         3834.152908                                        
      5717        17         2954.532677                                        
      5737        17         1432.181630                                        
      5741        18          909.483291                                        
      5749        18         1406.002342                                        
      5801        17         3641.505481                                        
      5813        17         4298.503993                                        
      5821        17         4102.030167                                        
      5849        17         4197.883107                                        
      5857        17         4728.425267                                        
      5861        17         1795.845985                                        
      5869        17         4677.236205                                        
      5881        19          887.553960                                        
      5897        17         3518.535617                                        
      5953        17         2066.597348                                        
      5981        17         4822.357179                                        
      6029        18         4140.311782                                        
      6037        19         1820.431672                                        
      6053        17         2030.064196                                        
      6073        19         2740.631401                                        
      6089        17         2542.541001                                        
      6101        18         2200.690523                                        
      6113        19         2541.136080                                        
      6121        18         2781.605084                                        
      6133        18         4476.917290                                        
      6173        17         7505.557813                                        
      6197        17         4852.137364                                        
      6217        19         1168.800517                                        
      6221        17         2983.757576                                        
      6229        19         3933.857243                                        
      6257        19         2762.010228                                        
      6269        17         3426.205518                                        
      6277        17         7471.050558                                        
      6301        19         2593.935525                                        
      6317        19         2873.981866                                        
      6329        19         2703.417342                                        
      6337        17         9862.973450                                        
      6353        17         4381.020172                                        
      6361        18         6235.792381                                        
      6373        17         6550.961531                                        
      6389        19         4070.616821                                        
      6397        18         7084.050552                                        
      6421        17         4765.196983                                        
      6449        19         1604.462722                                        
      6469        17         5609.277048                                        
      6473        19         4910.024754                                        
      6481        17         4897.979267                                        
      6521        21         2888.354216                                        
      6529        17         4553.512724                                        
      6553        19         5388.416230                                        
      6569        19         1882.608740                                        
      6577        19         3270.935085                                        
      6581        17        11063.210265                                        
      6637        18         5140.718001                                        
      6653        19         2574.798856                                        
      6661        19         7750.966270                                        
      6673        19         2334.400835                                        
      6689        19         2251.387632                                        
      6701        17        13085.247154                                        
      6709        17         6467.994968                                        
      6733        18         7214.095653                                        
      6737        18         9874.193841                                        
      6761        20         3868.291140                                        
      6781        19         2325.315091                                        
      6793        19         3681.520311                                        
      6829        18        13813.111353                                        
      6833        19         7129.099826                                        
      6841        17        13641.084521                                        
      6857        17        17407.028989                                        
      6869        19         2891.963385                                        
      6917        18         8068.283225                                        
      6949        18        11558.841513                                        
      6961        19         7667.036558                                        
      6977        18         6666.677116                                        
      6997        17        10683.233208                                        

[ IBM Research home page | James B. Shearer's home page | Up ]
[ IBM home page | Order | Search | Contact IBM | Legal ]