Maximize the number of paths

Question

You have exactly 990 edges. Assemble them into a simple undirected graph with two distinguished vertices A and B, such that the number of different simple paths from A to B is as large as you can make it.

One example. 990 edges is precisely what you need to create a complete graph on 45 vertices. Call one of the 45 vertices A and another B. Then the number of paths from A to B is $$ 1 + 43 + 43\cdot42 + 43\cdot42\cdot41 + \cdots + 43! = \lfloor 43!\cdot e\rfloor \approx 1.64\times 10^{53} $$

Another example. We can do much better than that, though. For example consider this graph:

A---O---O---O---O.....O---O---B
 \ / \ / \ / \ /       \ / \ /
  O   O   O   O         O   O

made of 330 triangles. Here there are $2^{330}\approx 2.19\times 10^{99}$ simple paths from A to B.

How many paths can you make, and how? I know that solutions with plenty more than $10^{100}$ paths exist, but have no particular reason to believe that what I'm thinking of is optimal.

Most paths win. Answers must state the number of paths in ordinary scientific notation, and must explain clearly how the paths were counted (in addition to explaining how to construct the graph they're counted in, of course). It is acceptable to compute a lower bound instead of an exact count.

(Inspired by this math.SE question, but I don't think anyone will be able to prove a maximum, so it's more a puzzle than an exact question.)

Answer 1

$2.11×10^{135}$

If I'm not mistaken the following grid must give the optimal result:

where are 990/5 = 198 layers with 2 vertices.

Let's calculate number of paths. I number 2-vertex layers from 0 to 197. CD is $0^{th}$, GH is $197^{th}$. There are 3 different possibilities at each transition between two layers:

1. straight

   / / __

2. vertical + straight

       __
   

   |\ | | \ |

3. zigzag

   ---

   /
   /\ _\

A rule here is that you can make vertical line only at the beginning of the transition. I call type 1 and type 2 open and type 3 - closed. After open transition you can have any other transition, but after closed you can have only type 1. Let's call number of paths, which lead to open layer $i$: $a_i$ and n of paths, which lead to closed layer $i$: $b_i$.
$a_0 = 2$, $b_0 = 0$ (see the vertical-line-rule above).

Open pattern can be followed by 4 open (type 1 and 2) or by 2 closed. Closed patern can be followed only by 2 open (type 1). Thereby: $$ \begin{pmatrix} a_{n} \\ b_{n} \end{pmatrix} = \begin{pmatrix} 4 & 2\\ 2 & 0 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ b_{n-1} \end{pmatrix} $$

Finally, to reach B-point after last layer we can use 2 ways if we ended with open pattern and 1 way with closed. So the total number of paths are:

$$ \begin{pmatrix}2&0\end{pmatrix} \begin{pmatrix} 4 & 2\\ 2 & 0 \end{pmatrix}^{197} \begin{pmatrix} 2 \\ 1 \end{pmatrix} $$

The result is $10^{135.325} = 2.11\cdot10^{135}$.

To be sure I haven't made mistakes, I have compared my calculations for 20 vertices and 45 edges graph with recursive program. They do agree.

The "inductive prove" (guess based) that most probably you can't do better you can find below.

---

The old answer:

@Falk Hüffner, gave the improved number $6.76 \cdot 10^{130}$ and the fact that you need to use 15 edges per "link" in the "chain", but there is still no prove and no example of the "link", which allows you to achieve this number. So let me do it here and give some extrapolations, which allows to imagine a probable optimal solution.

First, my chain of thoughts:
I got noted that @Henning Makholm (3 edges -> 2 paths), @Roland (5 edges -> 4 paths) and @f'' (9 edges -> 15 paths) can be reached easily from the complete graphs (for 3,4 and 5 vertices correspondingly) by rejecting the most useless edges. In case of 3 vertices there are no edges to reject. In case of 4 and 5 vertices you need to reject the one who connects A to B directly (and adds only 1 path).

Now, if we take complete graph on 6 vertices and will reject edges, which connect A to B via only 1 vertices we will get a graph, which have 10 edges and 20 paths. Which leads to $6.34 \cdot 10^{128}$ and is quite close to result with 5 vertices.

Here comes the example for current max-paths:
But you can improve result if you take 7 vertices and reject edges, which connect A to B via only 1 vertices. You will have 96 paths per 15 edges. And $6.76 \cdot 10^{130}$ paths for 990 edges.
To do so you need to take complete graph on 5 vertices (10 edges) and any 3 of them connect to A and other 2 connect to B.

Complete graph on 5 vertices allows you to reach any point from any-other point in $1+3+3\cdot 2+3\cdot 2+1$ = 16 paths. Plus you have 3 different ways to reach A and 2 ways to reach B, this leads to $16 \cdot 3 \cdot 2$ = 96 paths. Then $96^{990/15} \approx 6.76 \cdot 10^{130}$.

And the extrapolation:
When you try the same trick with 8 vertices, you will get $(65\cdot3\cdot3)^{990/(15+3+3)} \approx 2.83\cdot 10^{130}$ which is already smaller and since 990 is not dividable by 21 the actual result will be even worse.
Let's try now to reject also paths with 2 vertices. This is achieved in the following configuration:
And the result here is exactly the same as with 7 vertices: 15 edges and 96 paths.

So I suppose to improve this you need to consider 9 vertices and reject all paths via 0,1 and 2 vertices (I still need to figure out how to build and count this, may be it is even to reject all paths, which go through 2 vertices only).
Now, it looks like you need to add 2 vertices and reject 1-vertex longer path each time. Finally, we can guess here that the most optimal result will be a complete graph on X vertices with all paths via 0,1,2,...,(X-5)/2 vertices excluded. So if you stretch it between A and B you should see a chain with width of ~2 vertices.

---

P.S. Another @Falk Hüffner result $8.16 \cdot 10^{130}$ with 18 edges and 240 paths in "link" is achieved in the following configuration of the link:
This configuration follows the general sense rule, which I mentioned above: you need to take complete graph and rid of most useless links (those, which contribute to the shortest paths).
Unfortunately it was hard for me to consider all possibilities on paper, but my program confirmed that there are exactly 240 paths.

Answer 2

2.34×10¹²⁹

An improvement on Roland's answer. Connect two nodes $u,v$ to three nodes $x,y,z$ in a triangle. This uses nine edges and makes 15 paths from$u$ to $v$:$$uxv\\uxyv\\uxyzv\\uxzv\\uxzyv\\uyv\\uyxv\\uyxzv\\uyzv\\uyzxv\\uzv\\uzxv\\uzxyv\\uzyv\\uzyxv$$

Put $110$ of these in a row for a total of $15^{110}\approx2.34\times10^{129}$ paths.

Answer 3

1.323×10¹¹⁸

As a baseline:

  o   o   o       o
 /|\ /|\ /|\     /|\
A | o | o | o ... | B
 \|/ \|/ \|/     \|/ 
  o   o   o       o

This is an iteration of a 5-edge, 4-simple-path pattern, giving $4^{(990/5)} = 1.61...*100^{119}$ paths.

The four paths through a segment are:

 /\    /|   |\
o  o  o | o | o
    \/  |/ \|

The total number of paths appears to decrease as splitting for this pattern increases. For N=3, seen below, 8-edge, 9-path segments give $1.223*10^{118}$ paths, N=4 gives $10^{108}$, N=5 gives $10^{99}$, and so on.

 /|\ /|\ /|\  
A-|-o-|-o-|-o ... B
 \|/ \|/ \|/ 

In practice, some splittings don't divide 990 edges. N=3 could be applied in 120 segments with 6 N=2 segments: $9^{120}*4^6=1.323*10^{118}$

Answer 4

8.159×10¹³⁰

This is not a complete answer, since I don't state the actual construction nor give a proof for the number of paths, but I thought I'd share it anyway.

I've tried to find the maximum for small $m$, using a brute-force computer program based on https://github.com/falk-hueffner/tinygraph.

The optima, starting at 𝑚=0, are

𝑚	#paths	#vertices	1/𝑚 ⋅ log2(#paths)	#paths990/𝑚
0	0	1		0
1	1	2	0.0000	1
2	1	3	0.0000	1
3	2	3	0.3333	2.187 ⋅ 1099
4	2	4	0.2500	3.198 ⋅ 1074
5	4	4	0.4000	1.614 ⋅ 10119
6	5	4	0.3870	2.138 ⋅ 10115
7	7	5	0.4011	3.319 ⋅ 10119
8	10	5	0.4152	5.623 ⋅ 10123
9	15	5	0.4341	2.344 ⋅ 10129
10	20	6	0.4322	6.338 ⋅ 10128
11	26	6	0.4273	2.226 ⋅ 10127
12	37	6	0.4341	2.380 ⋅ 10129
13	48	6	0.4296	1.079 ⋅ 10128
14	68	7	0.4348	3.842 ⋅ 10129
15	96	7	0.4390	6.759 ⋅ 10130
16	129	7	0.4382	3.915 ⋅ 10130
17	169	8	0.4353	5.516 ⋅ 10129
18	240	8	0.4393	8.159 ⋅ 10130

(interestingly, not in OEIS). Thus, the values 4 paths for 5 edges and 15 paths for 9 edges given by Roland and f'' are optimal.

Using the gadget chaining method of Roland's and f'''s answers, we get only slight improvements, e.g. 8.159 * 10¹³⁰ for 𝑚 = 18.

The number of vertices of the optimal graphs (also in the above table) are close to the minimum possible for 𝑚 edges, indicating that this kind of long sparse construction will not yield something close to the optimum.

Answer 5

7.96×10¹³⁰ 9.099×10¹³⁰

The best I have come up with is this "lattice girder" graph (here shown with one possible path highlighted in red):

Between A and B there are 111 layers of 3 nodes each, except that layers 0 and 110 only have 2 nodes. Each node in a layer is connected to each node in the next layer, and in addition the two nodes on layers 0 and 110 are connected to each other.

To count the number of paths, consider the number of ways the part of the path that lies on layer $n$ or below:

• (a) If the path passes from layer $n$ to layer $n+1$ exactly once, the part up until layer $n$ is just a simple path that ends on layer $n$. (This is the case for example at layers 5, 106, and 108 in the above example path).
• (b) If the path passes from layer $n$ to $n+1$, then sometime later back to later $n$ and later yet up to $n+1$, the "part up until $n$", consists of two disjoint paths: One that goes from $A$ to a node on layer $n$, and one that starts and ends on layer $n$. (This is the case at layers 1 through 4 of the example path). As a special case, the second of these paths may consist of just a single layer-$n$ node (as in layer 4 or 107).
• (c) Finally the path may pass back and forth between layers $n$ and $n+1$ three times, in which case the "part up until $n$" consists of a path from $A$ to layer $n$, disjoint from two subpaths that start and end on layer $n$. (Because the layer has only three nodes, the subpaths in this case will both be single nodes). Layer 105 is an example of this.

Calling the number of partial solutions of each kind $a_n$, $b_n$, and $c_n$ respectively, we can write down a recurrence: $$ \begin{pmatrix} a_{n} \\ b_{n} \\ c_{n} \end{pmatrix} = \begin{pmatrix} 3 & 6 & 6 \\ 6 & 12 & 0 \\ 6 & 0 & 0 \end{pmatrix} \begin{pmatrix} a_{n-1} \\ b_{n-1} \\ c_{n-1} \end{pmatrix} $$ Most of the coefficients here just account for the different orders the nodes in layer $n$ may be visited in, but the $12$ in the middle has an extra factor of $2$ corresponding to whether the path doubles back at layer $n$ (like in layer 4 of the example) or passes through it three times (like in layers 1, 2, and 3).

The largest eigenvalue of the matrix on the right is 15.5266, so for a long girder, every 9 more edges will multiply the number of paths by 15.5266, comparing to just 15 for 9 more edges in the solution by f''.

One can count $(a_0,b_0,c_0)=(4,2,0)$ by hand, and conversely when we reach layer 110, the final number of paths is $4a_{109}+2b_{109}$, or with everything unfolded, $$ \begin{pmatrix}4&2&0\end{pmatrix} \begin{pmatrix} 3 & 6 & 6 \\ 6 & 12 & 0 \\ 6 & 0 & 0 \end{pmatrix}^{109} \begin{pmatrix} 4 \\ 2 \\ 0\end{pmatrix} $$

According to Wolfram Alpha the base-10 logarithm of this is 130.959, and $10^{0.959}=0.099$, so our final count is $$ 9.099 \times 10^{130} $$ narrowly beating the best of Falk Hüffner's results.

---

(Edited with more efficient ends of the girder, inspired by klm123's solution).

---

Repeating the same analysis for 4 nodes per layer gives a factor of about 106 per 16 edges, which is strictly worse ($106^{9/16}=13.8 < 15.52$). Alternating between 3 and 4 nodes per layer (in an attempt to reduce the cost of a layer-to-layer network) gives 958 per 24 edges, which is worse yet ($958^{9/24}=13.1$).