Ex(n;4)
From Combinatorics Wiki
ex(n;4)
P.Erdös ^{[1]} conjectured that ex(n;4)=(1/2 + o(1))^{3/2} n^{3/2}.
Garnick et al. demonstrated that extremal graphs include:
- Stars K_{1,n-1} and Paths P_{n} for n ≤ 4,
- Moore graphs:
- EX(5;4)={C_{5}} the cycle;
- ex(10;4)= 15 is attained by the Petersen graph ;
- ex(50;4)=175 is attained by the Hoffman-Singleton graph;
- ex(3250;4) is attained by the Moore graph with girth 5 and degree 57 if it exists.
- C_{6} is an element of EX(6;4).
- polarity graphs.
Large graphs, constructed by researches interested in The Cage Problem, provide good constructive lower bounds for the extremal number. These graphs are listed in the table when the number of vertices is less than 204. The higher order graphs produce the following lower bounds. ex_{l}(240;4)=1560, ex_{l}(288;4)=2016, ex_{l}(312;4)=2340,ex_{l}(336;4)=2688, ex_{l}(448;4)=3808, ex_{l}(480;4)=4320,ex_{l}(512;4)=4864 and ex_{l}(576;4)=5760.
Abajo, Balbuena and Di ́anez give the following constructive lower bounds for the extremal number:
- ex_{l}(2q^{2}+q;4)=q^{2}(q+1)+(q+1)ex(q;4) where q>1 is a prime power.
- ex_{l}(2q^{2}+q-h;4)=q^{2}(q+1)+(q+1)ex(q;4)-hq+e where q=8,9,11, e=-h for h=1,2 and e=-2 for h=3,...,q+1.
The following table lists the known values and constructive lower bounds for ex(n;4) for n < 204. If the value is known then it is shown in bold text.
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 1 | 2 | 3 | 5 | 6 | 8 | 10 | 12 |
10 | 15 | 16 | 18 | 21 | 23 | 26 | 28 | 31 | 34 | 38 |
20 | 41 | 44 | 47 | 50 | 54 | 57 | 61 | 65 | 68 | 72 |
30 | 76 | 80 | 85 | 87 | 90 | 95 | 99 | 104 | 109 | 114 |
40 | 120 | 124 | 129 | 134 | 139 | 144 | 150 | 156 | 162 | 168 |
50 | 175 | 176 | 178 | 181 | 185 | 188 | 192 | 195 | 199 | 203 |
60 | 207 | 212 | 216 | 221 | 226 | 231 | 235 | 240 | 245 | 250 |
70 | 255 | 260 | 265 | 271 | 278 | 285 | 291 | 298 | 305 | 312 |
80 | 320 | 322 | 327 | 334 | 341 | 348 | 355 | 362 | 369 | 376 |
90 | 384 | 392 | 399 | 407 | 415 | 423 | 432 | 436 | 438 | 440 |
100 | 443 | 445 | 447 | 450 | 452 | 458 | 465 | 472 | 480 | 488 |
110 | 496 | 504 | 512 | 520 | 528 | 536 | 544 | 552 | 560 | 568 |
120 | 576 | 585 | 593 | 602 | 611 | 620 | 630 | 634 | 638 | 641 |
130 | 644 | 647 | 650 | 653 | 657 | 666 | 674 | 683 | 692 | 700 |
140 | 709 | 717 | 726 | 735 | 744 | 753 | 762 | 771 | 780 | 789 |
150 | 798 | 808 | 817 | 827 | 837 | 847 | 858 | 862 | 865 | 868 |
160 | 871 | 873 | 875 | 878 | 880 | 883 | 886 | 892 | 901 | 910 |
170 | 920 | 930 | 932 | 935 | 938 | 941 | 949 | 958 | 968 | 977 |
180 | 986 | 995 | 1004 | 1013 | 1022 | 1032 | 1042 | 1052 | 1062 | 1072 |
190 | 1082 | 1092 | 1102 | 1112 | 1122 | 1132 | 1142 | 1152 | 1163 | 1173 |
200 | 1184 | 1195 | 1206 | 1218 | 1223 | 1227 | 1231 | 1236 | 1240 | 1245 |
The following table is the key to the colors in the table presented above:
Color | References |
* | Abajo, Balbuena and Di ́anez ^{[2]} |
* | Exoo and Jajcay ^{[3]} |
* | Garnick, Kwong and Lazebnik^{[4]}. |
* | Garnick and Nieuwejaar^{[5]}. |
* | Marshall ^{[6]}. |
References
- ↑ P. Erdös, Some recent progress on the extremal problems in graph theory, Congr. Numer. 14 (1975) 3--14
- ↑ E. Abajo, C. Balbuena, A. Di ́anez, New families of graphs without short cycles and large size, Discrete Applied Mathematics 158 (2010), 1127–-1135
- ↑ G. Exoo and R. Jajcay (2008), "Dynamic cage survey", The Electronic Journal of Combinatorics, Dynamic survey DS16 PDF version
- ↑ D. K. Garnick and Y. H. H. Kwong, F. Lazebnik, Extremal graphs without three-cycles or four-cycles, J. Graph Theory, 17 (1993), 633--645
- ↑ D. K. Garnick and N.A. Nieuwejaar, Non-isomorphic extremal graphs without three-cycles or four-cycles, JCMCC, 12 (1992), 33--56
- ↑ K Marshall, Interpolated lower bounds due to known large graphs.