« first day (2912 days earlier)      last day (2313 days later) » 
00:00 - 22:0022:00 - 00:00

Anonymous
22:00
*number of
Anonymous
Hmmm
I played around with it in Mathematica: 1) make a tree graph on N nodes, 2) go through the list of vertices and delete with probability p, 3) count the connected components
And then repeat 2),3) enough times to get statistics.
Anonymous
Are you acquainted with the Mathematica graph package?
Anonymous
I need to learn it sometime
Somewhat. Not a master but I’m familiar with the basics
Anonymous
22:03
I think we can attempt it mathematically
Anonymous
connected components = vertices - edges
Anonymous
So you are deleting vertices with probability p
Trouble is, how many edges are you deleting?
It’ll depend on the degree of the node
Anonymous
Thinking :P
It does suggest a useful insight though: you want to remove many edges while not removing many vertices
Anonymous
22:06
Isn't the probability of an edge being removed same as the probability of any one of its adjacent vertices being removed?
Anonymous
And these are all independent probabilities
Anonymous
We can just multiply them
Only one of the nodes needs to be removed to delete the edge
But that just changes it to “at least one of them”
Anonymous
Yeah, so it's an either or situation
Anonymous
Hmmm
22:08
So that’s 1-(1-p)^2
Anonymous
Exactly
And we do know how many vertices / edges we start with
Anonymous
Right
So that may be enough
Anonymous
Initially there is only one connected component
Anonymous
22:10
So if there were n number of nodes
Anonymous
There would have been n-1 edges
Anonymous
I guess that does the job
We can expect to remove p*n vertices and (1-(1-p)^2)*(n-1) edges
Anonymous
So the number of connected components = $(n - np) - ((n -1) - (1-(1-p)^2)(n-1))$ ?
I think so
Anonymous
22:13
Now it's just calculus...lol
Anonymous
Plug into mathematica
Anonymous
I hope we're not missing something
Sanity check: if p=0 we get 1 component and if p=1 we get 0
Which checks out
Anonymous
Yup
Anonymous
22:17
Wolfram gives $p_{\text{max}} = (-2 + n)/(2 (-1 + n))$
neat
Will check that against MMA when I get a chance
Anonymous
So it's simply a function of the tree size. That's really neat! :D
The edge probability was a good thought
Anonymous
22:21
It was an interesting problem. Do let me know if you come across more of these :)
A hard follow up to this would be the probability distribution for the number of connected components
Anonymous
@Semiclassical Yeah, there's usually a relation between the edges and vertices in these problems
Anonymous
@Semiclassical Well, we do know how the number of components varies with p and N
Anonymous
That's shouldn't be too tough, no?
Yeah, true
Anonymous
22:28
@Semiclassical Do you remember the proof for edges + connected components = vertices btw?
Anonymous
I can't recall it completely
Nope
Actually, hmm
For a tree, Euler’s formula v-e+f=2 with f=1
Anonymous
Aha
Anonymous
Now I just need to recall the proof for Euler characteristic :P
And if you’ve got n such trees in a forest, then summing Euler’s formula for each tree gives the number of components
Yeah, I’m not remembering it either
There’s probably a more direct proof for a tree anyways
Anonymous
22:34
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent. It is commonly denoted by χ {\displaystyle \chi } (Greek lower-case letter chi). The Euler characteristic was originally defined for polyhedra and used to prove various theorems about them, including the classification of the Platonic solids. Leonhard Euler, for whom...
Anonymous
It's given here ^
Like, if you attach a new node to an old one, then the vertex and edge counts both go up buly one
Anonymous
Long read ... lol
And that’s the only way you can add nodes since you don’t want to create loops
Anonymous
Right, right
22:36
The niggling doubt I have is that the set of nodes being deleted isn’t independent of the set of edges being deleted
Anonymous
They're sure related
One interesting thing with your result above: the ideal probability goes to 1/2 as n-> infinity
Anonymous
Oh, I feel v-e = 1 is pretty intuitive now. The key is that you can't form loops. So you can prove it for n = 1,2 and then general k and k+1....basically induction
Anonymous
@Semiclassical Yup
Anonymous
22:41
Nice observation
Anonymous
So for large trees just delete half of the nodes. I dunno why but that would be my first instinct too if I' were to do the maximum number of trees by deleting nodes thing...i.e. just delete half the nodes
another way to look at that: if you delete a leaf of a tree, the number of edges and vertices both decrease by one (so long as there's any nodes left)
so just keep cutting leaves until you're left with one vertex
one probably would want to formalize that, of course
Anonymous
Right. That's basically the reverse induction
Anonymous
Delete 1 node. Verify. Delete k nodes and prove it for k+1
Anonymous
Nah, wait
Anonymous
22:47
We can't verify it for the delete 1 node case, because we don't know a priori that v-e=1 :P
Anonymous
We can just assume it is true initially and keep verifying that the relation remains invariant after every deletion until the end
sounds right
the reverse order is a nice way to understand it, but the forward order is how you'd prove it
Anonymous
*by node, I meant leaf node there btw
Anonymous
@Semiclassical Yeah, I guess so. I think it's possible to do the whole proof in the reverse fashion too though
probably
i mean, once you've done n-1 deletions, you've only got one node left
and it won't be connected to anything
Anonymous
22:52
If you notice the Euler's formula proof on Wikipedia, they are doing the proof by deletion of triangles
yeah
lol, take a look at this: en.wikipedia.org/wiki/…
that algorithm sounds familiar to what we're doing
Anonymous
Nice. Yeah, that's exactly what we're doing :D
Anonymous
> Algorithm to convert a Prüfer sequence into a tree
(except for keeping track of what each leaf was attached to, of course)
Anonymous
That sounds more interesting ^
22:56
yep
Anonymous
{4,4,4,5}
Anonymous
back to a tree
Anonymous
Oh, so take the guy just larger than the largest number in the set
Anonymous
i.e. 6
Anonymous
Connect 5 to it
Anonymous
22:57
Then notice there are 3 4's
Anonymous
Got it. Makes sense :)
you can't connect 4 to 6 without creating a cycle, so you connect it to 123 and 5
neat-o
Anonymous
Yup!
Anonymous
Feeling sleepy now...lol
Anonymous
22:59
Cya!
23:15
Night
00:00 - 22:0022:00 - 00:00

« first day (2912 days earlier)      last day (2313 days later) »