Jacopo Notarstefano
Reputation
1,200
Top tag
Next privilege 2,000 Rep.
 Jan25 comment What is the name of a graph structure with 'ports'? In the context of Distributed Systems theory, I've seen it called simply a "graph with a port labeling". Example: goo.gl/w0DmEe Jan17 comment Would there be no input or input does not exist? Unfortunately, the same symbol is used. See here for a definition. Jan17 comment Would there be no input or input does not exist? Are you sure this problem isn't asking about the preimage of $g$, instead of its inverse (which isn't a function)? Jan16 awarded Informed Jan16 awarded Organizer Jan16 revised Finding the Optimum Point on a Curve Graph theory is an unrelated branch of mathematics. Jan16 suggested approved edit on Finding the Optimum Point on a Curve Jan12 comment What does $\chi(Tree)\leq 2$ mean in graph theory? Let me also add that the quantity you mentioned is called the branching factor, and is sometimes denoted $b$ (en.wikipedia.org/wiki/Branching_factor). Jan12 answered What does $\chi(Tree)\leq 2$ mean in graph theory? Jan10 comment How to calculate the expected maximum tree size in a pseudoforest Uh, I just noticed that that product telescopes, which results in a much simpler formula for $C(\tau)$! Jan10 comment How to calculate the expected maximum tree size in a pseudoforest To help your intuition: the numerator assigns the nodes according to the elements of the partition, but we are counting twice some assignments; in particular we count $k!$ times the assignments where $k$ elements of the partition of the same size split the same subset of nodes. Here's similar argument (fourth bullet point): math.stackexchange.com/a/393606/4471 Jan10 revised How to calculate the expected maximum tree size in a pseudoforest Fix two typos. Jan10 comment How to calculate the expected maximum tree size in a pseudoforest Almost. $C(\tau)$ is ${n \choose t_1} \cdot {n-t_1 \choose t_2} \cdot {n-t_1-t_2 \choose t_3} \cdot \dots \cdot {n-t_1-\dots-t_{r-1} \choose t_r}$ divided by their multiplicities. That formula has a few typos, which I'm going to fix now. Jan9 revised How to calculate the expected maximum tree size in a pseudoforest Fix mistake. Jan9 revised How to calculate the expected maximum tree size in a pseudoforest Add intuitive explanation of formula. Jan9 answered How to calculate the expected maximum tree size in a pseudoforest Jan7 accepted Minimal number of moves needed to solve a “Lights Out” variant Jan7 comment Minimal number of moves needed to solve a “Lights Out” variant Thank you for linking to that paper: I had a strong suspicion that this problem was NP-hard, it's nice to see it proven. Thank you also for your code: it's a bit hard to understand completely, but I think I understood the gist of it. Jan2 comment Efficient method for finding the number of combinations of values so that the sum is a certain number Unless your problem has some special structure you can exploit, you're out of luck: en.wikipedia.org/wiki/Subset_sum_problem Dec21 comment How many “good” graphs of size $n$ are there? Thank you very much for the Additional observations paragraph! I was thinking of submitting another question asking "Why are those two quantities equal?".