16
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ I wonder if you'd get good results by drawing graphs at random from some distribution and applying the probabilistic method. $\endgroup$ – user2357112 Jul 26 '16 at 23:47
  • $\begingroup$ The requirement of the graph to be simple is not necessary, isn't it? Any other graph will just waste edges without increasing amount of simple paths. $\endgroup$ – klm123 Jul 27 '16 at 6:42
  • $\begingroup$ @klm123: Depends on whether we consider a path to be a sequence of vertices or a sequence of edges. In the latter case, a non-simple graph of the form A==O==O==O...O==B would have $2^{495}$ paths. $\endgroup$ – Henning Makholm Jul 27 '16 at 7:47
  • $\begingroup$ What is the reason that you've posted that question with 990 edges? Seems like a bit of an arbitrary choice? For a puzzle something with lesser edges seems more appropriate without changing the actual task, or am I missing something important here? $\endgroup$ – BmyGuest Jul 30 '16 at 22:22
  • 2
    $\begingroup$ @BmyGuest: What I'm really interested in is how the maximal number of paths grows as a function of the number of edges, but fixing a particular number to compare solutions for seemed to make it work better as a puzzle. Choosing it to be large was to force the task to be about finding a good principle for constructing the graph rather than micro-optimizations that's just about who does the best brute-force search. It should still be small enough that the number of paths would fit into a floating-point double. 990 rather than 1000 was to make the complete-graph example work exactly. $\endgroup$ – Henning Makholm Jul 30 '16 at 23:23
4
$\begingroup$

$2.11×10^{135}$

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

enter image description here

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

Let's calculate number of paths. I number 2-vertice layers from 0 to 197. CD is 0th, GH is 197th. 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.

enter image description here

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: enter image description here
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-vertice 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: enter image description here
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.

$\endgroup$
  • $\begingroup$ I just checked and the peak for a structure of exactly $990$ edges made only from chains of (the same) of these $A\leftrightarrow B$ units consisting of a complete graph on $n$ vertices and $\lfloor\frac{n}2\rfloor$ connections to $B$ and the others to $A$ is indeed at $n=5$. $\endgroup$ – Jonathan Allan Jul 30 '16 at 20:11
  • $\begingroup$ @JonathanAllan, yes, it's the same as after 3 vertices (+A&B) you need to stop connecting all to A and all to B. Since number of paths in a complete graph is not ~x^n you need to change strategy when increase size of one "link". $\endgroup$ – klm123 Jul 30 '16 at 20:51
  • $\begingroup$ Yep, I am looking at such splitting from simple chains... $\endgroup$ – Jonathan Allan Jul 30 '16 at 20:53
  • $\begingroup$ Oh wow ... the most recent addition has a limiting $\frac1m \log_2 p$ of $0.4543$, beating everything so far. Why didn't I even try that myself? That gives a whopping $2.112\times 10^{135}$ paths. $\endgroup$ – Henning Makholm Jul 31 '16 at 10:56
  • $\begingroup$ @HenningMakholm, yup. I've just got the exactly same result. Thanks, now I'm sure that there are no mistakes. I guess number 3 is too beautiful and popular, so you haven't tried 2 ;) $\endgroup$ – klm123 Jul 31 '16 at 11:16
11
$\begingroup$

2.34×10129

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.

$\endgroup$
  • $\begingroup$ @HenningMakholm, so, is it as good as your solutions or one can still do better? $\endgroup$ – klm123 Jul 29 '16 at 5:31
  • $\begingroup$ @klm123: I can do better :-) Will probably write an answer over the weekend. $\endgroup$ – Henning Makholm Jul 30 '16 at 13:55
  • $\begingroup$ @HenningMakholm, nice! F's solution looks unbeatable for me, if there are something better the puzzle must be amazing. I still hope to find other graphs on my own. $\endgroup$ – klm123 Jul 30 '16 at 14:32
  • $\begingroup$ According to this paper this is maximal for a directed graph of $990$ edges because $990 \pmod 9 = 0$. $\endgroup$ – Jonathan Allan Jul 30 '16 at 18:45
  • $\begingroup$ @JonathanAllan: Interesting find! But strangely enough the graph in this answer is essentially undirected. $\endgroup$ – Henning Makholm Jul 30 '16 at 19:18
7
$\begingroup$

1.323×10118

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}$

$\endgroup$
4
$\begingroup$

8.159×10130

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 $m=0$, are $$ \begin{array}{c|c|c|c|r} m & \mathit{\#paths} & \mathit{\#vertices} & \frac1m \log_2(\mathit{\#paths}) & \mathit{\#paths}^{990/m} \\ \hline 0 & 0 & 1 & & 0 \\ 1 & 1 & 2 & 0.0000 & 1 \\ 2 & 1 & 3 & 0.0000 & 1 \\ 3 & 2 & 3 & 0.3333 & 2.187 \cdot 10^{99} \\ 4 & 2 & 4 & 0.2500 & 3.198 \cdot 10^{74} \\ 5 & 4 & 4 & 0.4000 & 1.614 \cdot 10^{119} \\ 6 & 5 & 4 & 0.3870 & 2.138 \cdot 10^{115} \\ 7 & 7 & 5 & 0.4011 & 3.319 \cdot 10^{119} \\ 8 & 10 & 5 & 0.4152 & 5.623 \cdot 10^{123} \\ 9 & 15 & 5 & 0.4341 & 2.344 \cdot 10^{129} \\ 10 & 20 & 6 & 0.4322 & 6.338 \cdot 10^{128} \\ 11 & 26 & 6 & 0.4273 & 2.226 \cdot 10^{127} \\ 12 & 37 & 6 & 0.4341 & 2.380 \cdot 10^{129} \\ 13 & 48 & 6 & 0.4296 & 1.079 \cdot 10^{128} \\ 14 & 68 & 7 & 0.4348 & 3.842 \cdot 10^{129} \\ 15 & 96 & 7 & 0.4390 & 6.759 \cdot 10^{130} \\ 16 & 129 & 7 & 0.4382 & 3.915 \cdot 10^{130} \\ 17 & 169 & 8 & 0.4353 & 5.516 \cdot 10^{129} \\ 18 & 240 & 8 & 0.4393 & 8.159 \cdot 10^{130} \end{array} $$

(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^{130}$ for $m = 18$.

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

$\endgroup$
  • $\begingroup$ Nice job. But it is unclear for me: what is m, what is the first sequence and where do you see "4 paths for 5 edges" and "15 paths for 9 edges" in this sequence? $\endgroup$ – klm123 Jul 30 '16 at 19:00
  • $\begingroup$ m is the number of edges. I hope the table makes things a bit clearer... $\endgroup$ – Falk Hüffner Jul 30 '16 at 22:05
  • 1
    $\begingroup$ Can you show your $m=18$ graph? According to my calculations, my "lattice girder" construction ought to have a limiting $\frac1m\log_2p$ of $0.4396$, but $990$ edges is not enough for it to actually outperform $0.4393$. $\endgroup$ – Henning Makholm Jul 30 '16 at 23:39
  • $\begingroup$ @HenningMakholm, I've found the graph for m=18 too. Check out my answer. $\endgroup$ – klm123 Jul 31 '16 at 7:42
2
$\begingroup$

7.96×10130 9.099×10130

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

drawing of graph described below

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$).

$\endgroup$
  • $\begingroup$ Nice. I'm thinking maybe a small-world-type or similar, less regularly connected network with many $K_5$ clusters may be a winner, but have yet to formulate a strategy! $\endgroup$ – Jonathan Allan Jul 30 '16 at 20:18
  • $\begingroup$ Could you explain the values in the matrix in more details, please? For example, 6 in 2nd row, 1st column. An example for it in layers 106-108, n-1 = 107, n = 108, right? And I can see 3*2*2 =12 possibilities. and this is only for the case when the second path doesn't go further, if you consider other cases it should be even more... $\endgroup$ – klm123 Jul 31 '16 at 10:21
  • $\begingroup$ @klm123: The $6$ counts the ways to to extend an (a)-situation such as [..106] in the example to a (b)-situation such as [..107]. We already have a A-to-106 path; in order to produce a A-to-107 path and a 107-to-107 path, the only choices are first which of the three nodes on level 107 we connect the A-to-106 path to, and then which of the two remaining nodes on level 107 will constitute the 107-to-107 path. So that covers the first term in $b_{107}=6a_{106}+12b_{106}$. $\endgroup$ – Henning Makholm Jul 31 '16 at 10:42
  • $\begingroup$ @HenningMakholm, I see, when you construct [.. 107] you need to add a beginning of a disjoint path, which includes one node only, and there are only 2 possibilities for it. Thanks. $\endgroup$ – klm123 Jul 31 '16 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.