Lubotzky-Phillips-Sarnak Graphs

This page is inspired by Neil Sloanes ``Challenge Problems: Independent Sets in Graphs'' page (http://www2.research.att.com/~njas/doc/graphs.html). It contains a collection of the graphs described by Lubotzky, Phillips and Sarnak [Ramanujan graphs, Combinatorica 8 (1988), 261-277] (and in [G. Davidoff, P. Sarnak, A. Valette, Elementary number theory, group theory, and Ramanujan graphs. London Mathematical Society Student Texts, 55. Cambridge University Press, Cambridge, 2003. x+144 pp.]) in DIMACS format (see http://dimacs.rutgers.edu/Challenges/).

In all these cases, there is a gap between the cardinality of the largest independent set found and the known upper bounds on the independence number, leaving room for improvement either through implementation or theory. In all these cases, the Hoffman bound is tighter than the Lubotzky-Phillips-Sarnak bound.

We denote LPS(p,q) the graph denoted Xp,q by Lubotzky, Phillips and Sarnak. The DIMACS text files were generated by Randy Elzinga using MATLAB; details of the construction can be found here (PDF 74K). The parameter q is always 13, hence all these graphs have 13(132-1)/2 = 1092 vertices.

The graphs

LPS(3,13):
4-regular, girth 9, diameter 8,
Lower bound on independence number: 445 (witness),
Upper bound on independence number: 491 (Hoffman bound).

LPS(17,13):
18-regular, girth 3, diameter 4,
Lower bound on independence number: 218 (witness),
Upper bound on independence number: 331 (Hoffman bound).

LPS(23,13):
24-regular, girth 3, diameter 3,
Lower bound on independence number: 234 (witness),
Upper bound on independence number: 273 (Hoffman bound).

LPS(29,13):
30-regular, girth 3, diameter 3,
Lower bound on independence number: 173 (witness),
Upper bound on independence number: 256 (Hoffman bound).

LPS(43,13):
44-regular, girth 3, diameter 3,
Lower bound on independence number: 110 (witness),
Upper bound on independence number: 207 (Hoffman bound).

LPS(53,13):
54-regular, girth 3, diameter 3,
Lower bound on independence number: 156 (witness),
Upper bound on independence number: 198 (Hoffman bound).

LPS(61,13):
62-regular, girth 3, diameter 3,
Lower bound on independence number: 98 (witness),
Upper bound on independence number: 200 (Hoffman bound).

LPS(101,13):
102-regular, girth 3, diameter 2,
Lower bound on independence number: 104 (witness),
Upper bound on independence number: 156 (Hoffman bound).

LPS(103,13):
104-regular, girth 3, diameter 3,
Lower bound on independence number: 64 (witness),
Upper bound on independence number: 171 (Hoffman bound).

LPS(113,13):
114-regular, girth 3, diameter 2,
Lower bound on independence number: 84 (witness),
Upper bound on independence number: 152 (Hoffman bound).

LPS(127,13):
128-regular, girth 3, diameter 2,
Lower bound on independence number: 53 (witness),
Upper bound on independence number: 135 (Hoffman bound).

LPS(157,13):
158-regular, girth 3, diameter 2,
Lower bound on independence number: 66 (witness),
Upper bound on independence number: 136 (Hoffman bound).


Largest independent set found in LPS/p3q13: 445 vertices.

1 3 8 9 10 11 14 20 22 23 27 31 32 33 34
35 37 40 41 42 44 46 51 55 56 57 58 61 62 63
64 65 70 71 77 80 82 85 89 90 91 92 95 97 104
109 110 115 119 120 122 131 132 133 139 140 142 145 146 150
151 152 157 158 161 162 170 172 174 175 176 177 179 181 183
184 185 186 187 188 190 191 192 193 196 200 201 205 207 211
212 213 214 215 219 221 222 225 227 229 231 233 235 237 242
244 245 247 248 249 251 254 258 265 266 269 274 275 279 283
284 286 288 289 291 292 296 297 298 302 305 309 311 314 315
316 317 324 326 331 334 335 337 339 342 343 344 345 346 348
350 356 360 361 362 365 366 367 369 372 375 378 380 384 385
386 390 391 392 393 398 399 402 408 410 411 413 414 416 419
420 421 422 424 428 431 432 434 439 440 445 447 452 454 460
461 464 465 466 470 471 473 474 477 478 482 484 486 489 495
497 498 500 501 504 510 517 518 520 522 523 528 529 534 535
540 541 543 544 547 552 553 554 559 561 562 564 566 567 568
576 577 578 583 585 586 589 590 591 593 595 598 604 611 612
620 622 624 627 630 631 632 637 641 645 649 651 654 655 656
661 663 666 667 668 670 673 678 679 682 685 686 688 689 690
691 695 700 701 708 709 711 712 713 714 715 716 718 720 724
727 728 729 731 732 733 734 735 736 737 742 743 744 746 750
754 755 757 758 760 761 763 768 769 770 771 775 777 778 779
781 783 784 787 788 792 793 796 799 800 801 802 803 804 805
806 809 811 814 817 820 823 827 831 834 837 838 839 841 850
851 855 858 859 863 865 868 870 874 876 879 883 885 888 891
893 898 899 902 906 907 909 913 915 918 919 920 922 923 924
925 927 932 933 942 943 947 951 952 956 958 960 967 968 969
970 975 976 978 981 987 990 997 998 1004 1005 1011 1012 1015 1016
1017 1018 1019 1023 1024 1028 1031 1033 1035 1039 1041 1044 1046 1049 1051
1058 1064 1072 1073 1078 1079 1085 1086 1088 1090


Largest independent set found in LPS/p17q13: 218 vertices.

1 5 7 8 10 11 12 25 26 31 35 36 40 41 48
50 51 52 54 55 62 66 70 83 88 89 90 100 101 106
115 119 122 124 125 126 127 129 135 139 141 143 144 151 152
155 160 161 165 167 170 171 175 180 181 182 185 187 189 192
194 200 202 203 212 227 235 243 253 257 263 265 268 275 277
284 286 291 299 301 302 303 309 316 318 324 325 338 339 342
346 348 350 353 354 357 359 365 368 374 390 393 397 405 411
415 422 423 432 435 439 442 444 446 448 449 466 484 502 506
507 508 515 518 521 522 523 525 532 538 542 543 547 549 551
554 557 559 564 568 570 573 579 586 587 594 601 604 606 609
610 614 626 635 645 655 666 673 690 695 697 702 707 711 712
713 714 727 730 749 751 757 763 774 781 786 790 811 815 823
826 827 831 837 848 849 857 859 861 869 879 883 892 893 905
920 924 932 934 943 948 950 951 957 959 961 967 970 975 994
995 1022 1038 1045 1068 1080 1081 1083


Largest independent set found in LPS/p23q13: 234 vertices.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
76 77 78 85 89 91 95 97 101 103 107 109 113 115 119
121 125 127 131 133 137 139 143 145 149 151 155 157 161 170
176 182 188 194 200 206 212 218 224 230 236 242 254 255 260
261 266 267 272 273 278 279 284 285 290 291 296 297 302 303
308 309 314 315 320 321 326 327 340 346 352 358 364 370 376
382 388 394 400 406 412 425 431 437 443 449 455 461 467 473
479 485 491 497 508 510 514 516 520 522 526 528 532 534 538
540 544 546 550 552 556 558 562 564 568 570 574 576 580 582
673 679 685 691 697 703 709 715 721 727 733 739 745 762 768
774 780 786 792 798 804 810 816 822 828 834 927 933 939 945
951 957 963 969 975 981 987 993 999


Largest independent set found in LPS/p29q13: 173 vertices.

4 7 9 11 15 16 45 49 52 54 62 72 73 74 78
80 102 105 106 107 109 115 116 118 121 125 126 130 134 142
153 160 167 171 174 175 178 186 200 201 213 215 217 226 228
231 239 246 250 253 256 265 276 278 280 282 285 288 292 295
299 300 303 316 326 332 333 338 346 362 389 392 395 399 408
411 435 449 452 458 460 468 474 476 479 480 486 487 492 497
499 503 504 533 543 550 565 570 579 590 593 596 607 608 609
618 622 623 624 627 629 642 645 653 655 661 686 700 706 709
711 718 719 740 741 753 755 757 763 768 770 773 775 777 784
787 789 799 810 811 814 819 825 840 842 843 855 857 858 863
879 889 890 891 901 914 936 951 964 965 968 969 974 983 994
997 1023 1037 1050 1055 1065 1084 1088

Largest independent set found in LPS/p43q13: 110 vertices.

5 11 12 24 26 58 59 72 74 80 99 101 108 121 132
149 156 175 176 179 180 194 202 203 208 248 253 256 258 259
287 293 302 316 332 336 342 344 348 350 362 363 400 401 417
429 437 453 455 457 473 476 488 503 505 506 512 514 528 553
561 577 582 585 592 594 597 600 607 608 626 630 634 635 644
658 660 673 677 687 696 699 705 710 719 721 722 725 729 742
753 765 772 779 789 798 805 856 905 927 934 938 954 964 970
971 979 1002 1054 1056

Largest independent set found in LPS/p53q13: 156 vertices.

2 7 11 15 19 22 24 45 64 71 74 78 81 89 96
97 123 140 144 145 148 159 161 164 168 193 195 204 206 211
219 220 222 230 233 239 257 259 268 270 278 285 293 302 304
307 321 340 350 352 359 366 378 380 381 385 397 401 417 419
424 426 428 444 452 455 457 459 461 463 477 496 505 514 516
524 525 527 531 533 559 576 578 580 587 588 590 597 598 605
623 637 642 654 657 658 675 701 709 718 728 731 734 739 742
750 751 752 757 771 773 782 784 787 794 798 802 813 816 846
854 859 861 868 876 880 887 890 899 915 932 933 935 937 942
958 964 968 975 991 996 1003 1006 1011 1028 1030 1033 1038 1039 1040
1041 1042 1055 1074 1085 1090

Largest independent set found in LPS/p61q13: 98 vertices.

13 17 24 43 44 46 60 68 73 75 78 87 104 105 109
115 124 126 142 161 164 165 166 178 210 222 224 236 252 256
258 273 280 297 299 300 305 315 341 350 358 359 361 362 365
368 396 402 404 407 419 450 454 461 463 470 496 505 512 513
529 530 556 566 567 573 583 593 675 684 709 710 715 745 767
789 811 815 817 835 853 854 855 877 904 905 907 924 943 946
954 959 962 985 989 1011 1054 1060

Largest independent set found in LPS/p101q13: 104 vertices.

3 14 26 31 41 60 63 70 79 93 95 103 106 117 123
126 132 142 160 170 175 181 188 193 198 202 229 243 248 262
273 278 285 288 326 348 354 364 365 371 391 424 440 443 451
462 472 482 488 503 505 510 542 544 553 554 578 613 624 634
645 655 664 665 669 684 709 726 737 740 749 750 773 783 790
801 812 822 825 827 837 845 846 855 884 887 893 901 904 911
952 956 971 987 993 996 1006 1012 1047 1049 1063 1081 1088 1092

Largest independent set found in LPS/p103q13: 64 vertices.

12 13 19 28 33 89 103 106 112 113 121 122 132 168 170
192 193 208 234 253 262 267 268 287 299 315 324 335 349 366
367 382 385 394 406 420 421 424 438 453 461 470 477 528 566
581 681 760 764 807 834 843 851 863 867 886 897 920 973 991
1042 1046 1084 1087

Largest independent set found in LPS/p113q13: 84 vertices.

2 9 25 26 29 34 35 36 40 49 54 69 86 91 109
114 116 131 143 147 152 159 175 179 182 200 202 219 233 255
261 264 276 284 305 306 314 346 370 371 419 420 467 480 486
491 493 500 507 510 514 516 524 542 562 605 611 613 634 679
681 682 715 722 746 760 764 768 787 791 803 804 823 833 856
861 894 904 927 939 942 1002 1010 1069

Largest independent set found in LPS/p127q13: 53 vertices.

4 13 18 21 29 36 61 81 99 135 193 233 259 280 288
314 325 331 334 337 344 371 419 434 439 447 467 486 516 547
551 579 604 605 622 637 659 685 686 690 727 746 761 812 866
884 888 907 929 991 1035 1038 1064

Largest independent set found in LPS/p157q13: 66 vertices.

2 10 12 35 43 47 61 85 97 140 144 150 153 164 188
196 212 223 244 260 280 281 284 302 306 309 312 319 326 337
341 342 345 401 414 422 443 458 462 466 568 571 583 603 606
611 623 625 652 671 683 718 724 808 830 834 865 873 932 965
983 986 1018 1026 1032 1035