A198300 Square array M(k,g), read by antidiagonals, of the Moore lower bound on the order of a (k,g)-cage.

3, 4, 4, 5, 6, 5, 6, 8, 10, 6, 7, 10, 17, 14, 7, 8, 12, 26, 26, 22, 8, 9, 14, 37, 42, 53, 30, 9, 10, 16, 50, 62, 106, 80, 46, 10, 11, 18, 65, 86, 187, 170, 161, 62, 11, 12, 20, 82, 114, 302, 312, 426, 242, 94, 12, 13, 22, 101, 146, 457, 518, 937, 682, 485, 126, 13

Offset: 1

Author

Jason Kimberley, Oct 27 2011

Keywords

• nonn
• tabl
• easy
• base

Comments

k >= 2; g >= 3.

The base k-1 reading of the base 10 string of A094626(g).

Exoo and Jajcay Theorem 1: M(k,g) <= A054760(k,g) with equality if and only if: k = 2 and g >= 3; g = 3 and k >= 2; g = 4 and k >= 2; g = 5 and k = 2, 3, 7 or possibly 57; or g = 6, 8, or 12, and there exists a symmetric generalized n-gon of order k - 1.

Examples

			This is the table formed from the antidiagonals for k+g = 5..20:
3   4   5   6    7    8    9     10    11    12    13    14    15   16  17 18
4   6  10  14   22   30    46    62    94   126   190   254   382  510 766
5   8  17  26   53   80   161   242   485   728  1457  2186  4373 6560
6  10  26  42  106  170   426   682  1706  2730  6826 10922 27306
7  12  37  62  187  312   937  1562  4687  7812 23437 39062
8  14  50  86  302  518  1814  3110 10886 18662 65318
9  16  65 114  457  800  3201  5602 22409 39216
10 18  82 146  658 1170  5266  9362 42130
11 20 101 182  911 1640  8201 14762
12 22 122 222 1222 2222 12222
13 24 145 266 1597 2928
14 26 170 314 2042
15 28 197 366
16 30 226
17 32
18
		

References

• E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci. Tokyo, Sect. 1A, 20 (1973) 191-208.
• R. M. Damerell, On Moore graphs, Proc. Cambridge Phil. Soc. 74 (1973) 227-236.

Links

• Jason Kimberley, Table of n, a(n) for n = 1..20100 (k+g = 5..204)
• Jason Kimberley, Table of n, k+g, k, g, M(k,g)=a(n) for k+g = 5..204 (n = 1..20100)
• G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
• Gordon Royle, Cages of higher valency

Crossrefs

Moore lower bound on the order of a (k,g) cage: this sequence (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7), 2*A053698 (g=8), 2*A053699 (g=10), 2*A053700 (g=12), 2*A053716 (g=14), 2*A053716 (g=16), 2*A102909 (g=18), 2*A103623 (g=20), 2*A060885 (g=22), 2*A105067 (g=24), 2*A060887 (g=26), 2*A104376 (g=28), 2*A104682 (g=30), 2*A105312 (g=32).

Cf. A054760 (the actual order of a (k,g)-cage).

Programs

Magma

ExtendedStringToInt:=func;
M:=func;
k_:=2;g_:=3;
anti:=func;
[anti(kg):kg in[5..15]];

Mathematica

Table[Function[g, FromDigits[#, k - 1] &@ IntegerDigits@ SeriesCoefficient[x (1 + x)/((1 - x) (1 - 10 x^2)), {x, 0, g}]][n - k + 3], {n, 2, 12}, {k, n, 2, -1}] // Flatten (* Michael De Vlieger, May 15 2017 *)

Formula

M(k,2i) = 2 sum_{j=0}^{i-1}(k-1)^j = string "2"^i read in base k-1.

M(k,2i+1) = (k-1)^i + 2 sum_{j=0}^{i-1}(k-1)^j = string "1"*"2"^i read in base k-1.

Recurrence:

M(k,3) = k + 1,

M(k,2i) = M(k,2i-1) + (k-1)^(i-1),

M(k,2i+1) = M(k,2i) + (k-1)^i.