Ex(n;t)

From Combinatorics Wiki

Values shown in bold are known exact values. Other values are lower bounds. If two values are shown then they are the lower and upper bounds.

Table of some known values for ex(n;t) for n=1,2,...,50 and t=3,4,...,13.
n/t 3 4 5 6 7 8 9 10 11 12 13
1 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1
3 2 2 2 2 2 2 2 2 2 2 2
4 4 3 3 3 3 3 3 3 3 3 3
5 6 5 4 4 4 4 4 4 4 4 4
6 9 6 6 5 5 5 5 5 5 5 5
7 12 8 7 7 6 6 6 6 6 6 6
8 16 10 8 8 8 7 7 7 7 7 7
9 20 12 10 9 9 9 8 8 8 8 8
10 25 15 12 11 10 10 10 9 9 9 9
11 30 16 14 12 12 11 11 11 10 10 10
12 36 18 16 14 13 12 12 12 12 11 11
13 42 21 18 15 14 14 13 13 13 13 12
14 49 23 21 17 16 15 15 14 14 14 14
15 56 26 22 18 18 16 16 15 15 15 15
16 64 28 24 20 19 18 17 17 16 16 16
17 72 31 26 22 20 19 18 18 18 17 17
18 81 34 29 23 22 21 20 19 19 18 18
19 90 38 31 25 24 22 21 20 20 20 19
20 100 41 34 27 25 23 23 22 21 21 21
21 110 44 36 29 27 25 24 23 22 22 22
22 121 47 39 31 29 27 25 24 24 23 23
23 132 50 42 33 30 28 27 26 25 24 24
24 144 54 45 36 32 29 28 27 27 26 25
25 156 57 48 37 34 30 30 28 28 27 26
26 169 61 52 39 36 32 31 30 29 28 28
27 182 65 53 41 38 33-34 32 31 30 30 29
28 196 68 56 43 40 34-36 34 33 32 31 30
29 210 72 58 45 42 36-38 36 34 33 32 32
30 225 76 61 47 45 37-41 37-38 34 33 33
31 240 80 64 49 46 39-43 38-40 36 34 34
32 256 85 67 51 47 40-45 40-42 37 36 35
33 272 87 70 53-54 49 41-47 42-44 37 36
34 289 90 74 55-56 51 43-50 43-46 39 38
35 306 94 77 57-61 53 45-53 44-48 40 39
36 324 99 81 59-63 55 46-55 46-50 40
37 342 104 84 61-65 56-58 47 48-52 42
38 361 109 88 62-68 58-60 49 49-54 43
39 380 114 92 64-70 60-63 51 50-56
40 400 120 96 67-73 62-65 53 52-58
41 420 124 100 69-75 64-67 54 54-60
42 441 129 105 71-77 65-69 56 55-62
43 462 134 106-108 73-80 67-71 58 57-64
44 484 139 108-112 75-82 69-73 60 59-66
45 506 144 110-116 77-85 71-76 61 60-68
46 529 150 114-119 80-87 73-78 63 61-70
47 552 156 118-123 82-90 75-80 65 63-72
48 576 162 122-127 84-92 77-82 67 64-74


49 600 168 125-131 87-95 79-84 69 66-76
50 625 175 130-135 81-87 70 68-78


The following table is the key to the colors in the table presented above:

Color References
* Folklore.
* Mantel's theorem for t=3 [1]
* Garnick, Kwong and Lazebnik[2].
* Garnick and Nieuwejaar[3].
* E. Abajo and A. Diánez [4]
* E. Abajo and A. Diánez [5]
* Tang et al. [6]
* Delorme et al. [7]
* Delorme et al. [8]
* Marshall et al. [9]
* K. Marshall and Y. Lin [10]


References

  1. Mantel's theorem
  2. 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
  3. D. K. Garnick and N.A. Nieuwejaar, Non-isomorphic extremal graphs without three-cycles or four-cycles, JCMCC, 12 (1992), 33--56
  4. E. Abajo, A. Diánez, Size of Graphs with High Girth, Electronic Notes in Discrete Mathematics 29 (2007) 179--183
  5. E. Abajo, A. Diánez, Exact values of ex(v;{C3,C4,... , Cn}), Discrete Applied Mathematics 158 (2010) 1869--1878
  6. J. Tang, Y. Lin, M. Miller, C. Balbuena, Construction of EX graphs, Special Issue of International Journal of Computer Mathematics (2009)
  7. C. Delorme, E. Flandrin, Y. Lin, M. Miller and J. Ryan, On Extremal Graphs with Bounded Girth Electronic Notes in Discrete Mathematics, Volume 34, 1 August 2009, Pages 653-657
  8. C. Delorme, E. Flandrin, Y. Lin, M. Miller, K. Marshall and J. Ryan, New exact values of ex(n;6), preprint
  9. K. Marshall, M. Miller and J. Ryan, Extremal Graphs without Cycles of length 8 or less, preprint
  10. K. Marshall and Y. Lin, Extremal {C3,C4,.. ,C9}-free graphs, submitted IWOCA 2011t