April 2020

[R.D. Silverman]

Originally Posted by uau

Well if you assume an unlabeled graph, you could label it arbitrarily. But the adjacency matrix necessarily implies an ordering of the graph nodes. So I interpreted it as: "find an adjacency matrix such that the probability will be close to 70% when doing 10 steps from the state where the node corresponding to the first row is the only infected node".

I don't quite get the point here? Sure the complete graph has maximal probability. But we're not trying to find maximal probability, we're trying to get close to 70%. So if we find that a size 5 complete graph has probability >70%, now what?

Thank you. I misread the problem as ">= 70.00%".

[LaurV]

Originally Posted by R.D. Silverman

But the labeling is arbitrary... Any node for a given graph can be labeled 'A'.

Right. So? (how does this change the puzzle? It does not)
The puzzle is well formulated. I also get their number for the example, with a little Excel calculation.

(edit: @virgo: you forgot the possibility of reverse infection, for example, B can also be infected by E, not only by A, assume he is lucky for 7 days, and meantime E gets the disease, by A-D-E or even A-C-D-E route, then B gets it in the eighth day, from E).

OTOH, the problem seems quite easy by brute force, 8 vertices, there are \(C_8^2=28\) possible edges, the matrix in fact is triangular (symmetric on the first diagonal, which is zero always), so there are just 28 bits of entropy, the search space is 2^28, less than a billion possible cases. This should be an extremely easy, few hours, pari "struggle" to calculate all probabilities and sort them in a list.

(I didn't solve it yet, no time, but one idea would be to check if the probability of complete graph \(K_8\) is higher than 70%, first, to be sure there IS a solution. Then, start cutting edges in some fashion).

[R.D. Silverman]

Originally Posted by LaurV

Right. So? (how does this change the puzzle? It does not)
The puzzle is well formulated. I also get their number for the example, with a little Excel calculation.

OTOH, the problem is quite easy by brute force, 8 vertices, there are \(C_8^2=28\) possible edges, the matrix in fact is triangular (symmetric on the first diagonal, which is zero always), so there are just 28 bits of entropy,).

Actually it is much less, because we are only need consider labelled connected graphs.
There are less than 2000000 such with 8 nodes. See http://oeis.org/A001187

[R.D. Silverman]

Originally Posted by uau

<snip>

Sure the complete graph has maximal probability.

We agree. But I seek a formal proof.

[LaurV]

Originally Posted by R.D. Silverman

Actually it is much less, because we are only need consider labelled connected graphs.
There are less than 2000000 such with 8 nodes. See http://oeis.org/A001187

You re totally right about connected graphs. However I was talking about "brute force" and I didn't actually think to a way to enumerate connected graphs without generating all of them and check which is connected and which not. That is why I was talking about starting from the complete graph. With a clever way to generate only the connected graphs, the puzzle is even simpler. But not by much. The number is still in 200M, not 2^28, but also not 2M. I guess you typo-ed, or didn't see that the sequence on OEIS is zero-indexed (yes, there are 4 labeled connected graphs with 3 nodes, see here). For comparison, there are 251'548'592 to test, versus 2^28=268'435'456. Non-connected graphs are very few here. Of course, you still may eliminate the symmetries, but checking for such, will be slower than generating all 2^28 graphs.

[R.D. Silverman]

Originally Posted by LaurV

Right. So? (how does this change the puzzle? It does not)
.

Consider the following graph:

A-----B-------C

vs.

B-----A------C

If the infected person is A he/she can infect two people on the first iteration in the second
graph, but not the first.

[LaurV]

This is not what you initially said. I learned from you, to read it as it is, and not to interpret it. The two examples are the same, if I can label arbitrary the A node. Yes, the labeling is arbitrary. I always put A in the middle. Think about it. Arbitrary labeling means that, given a graph, I can label it the way I want. For 3 nodes, you have 4 cases (of connected, labeled graphs), but 2 are symmetric (A--C--B and A--B--C give the same probability), so you have to test 3 of them for probability, assuming you have a fast way to detect the symmetry. If not, you must test all 4. (Now, if you read the continuation of the discussion in the thread, you can see it was just nitpicking (or, better said, picking on you )).

Anyhow, this problem is extremely easy, once you come with the conditioned probability formula (which is actually the hardest part). Then, one way or the other, you have about 2-3 hundred millions cases to test. You can make a nice sorted list, in full, in memory, and pick the closest to 70 for the answer, but also provide the "full solution" to amaze the puzzle makers

Edit: I have some vague idea about how I will spend my weekend tomorrow

[R.D. Silverman]

Originally Posted by LaurV

This is not what you initially said. I learned from you, to read it as it is, and not to interpret it. The two examples are the same, if I can label arbitrary the A node. Yes, the labeling is arbitrary. I always put A in the middle.

The issue is not the labeling. It is assumed that A is the person infected at t=0.
The question is where A is placed on the graph.

Anyhow, this problem is extremely easy, once you come with the conditioned probability formula (which is actually the hardest part).

I disagree. I think this is the easy part.

[virgo]

Originally Posted by uau

Yes, my calculations match the provided answer for the example graph.

can you give me probabilities after day 1~9?
I think its about how to calculate complementary event, but I still get wrong numbers
thanks,

[LaurV]

Originally Posted by R.D. Silverman

I disagree. I think this is the easy part.

Maybe for you...

[tgan]

Originally Posted by virgo

can you give me probabilities after day 1~9?
I think its about how to calculate complementary event, but I still get wrong numbers
thanks,

I am also having the same results 24.xxx and not 29.xxx
https://mersenneforum.org/images/smi...tra/picard.png