Jacopo Notarstefano
Reputation
1,357
Top tag
Next privilege 2,000 Rep.
 Feb 27 awarded Good Question Jan 25 awarded Popular Question Dec 19 comment Does this algorithm for Graph Realization work? As noted above, this answers the question as written, but only sketches an argument for why the algorithm appears to work in practice (provided one also keeps track of the edges). I won't probably ask a followup question on that, but I welcome anyone to do so! Dec 19 accepted Does this algorithm for Graph Realization work? Dec 16 comment Does this algorithm for Graph Realization work? Ah, yes, the argument in 1. clearly implies that the algorithm is underspecified and requires an additional data structure to keep track of the edges. I also like the argument in 2. to show that the Havel-Hakimi strategy and the other one are roughly "dual", which is why I was having trouble finding a counterexample. I will keep the question open a few more days in case someone manages to find one, though. Dec 15 comment Existence of Non-Commutative $4 \times 4$ Matrix Multiplication Algorithm I'm reminded of this question of mine. I wasn't asking the same thing, but the problems of inverting and multiplying are strongly related. Dec 15 comment Does this algorithm for Graph Realization work? Apologies for your misunderstanding as well — hopefully the edit I just made will clarify the point you raised in your answer. Dec 15 revised Does this algorithm for Graph Realization work? Clarify a misunderstood detail. Dec 14 comment Does this algorithm for Graph Realization work? Apologies for the confusion: I'm not asking about the Havel-Hakimi algorithm, but for the algorithm below (the one connecting a vertex of highest degree with a vertex of lowest degree). Dec 14 asked Does this algorithm for Graph Realization work? Dec 6 awarded Yearling Nov 1 awarded Announcer Oct 25 comment How many words of length $7$ can we assemble if each letter should appear at least twice. The answer is ok, but the explanation simply isn't there. For all I know, you could have peeked your solution from someone else, so I would still give 0 marks for this. Sep 19 awarded Popular Question Sep 4 answered At least how many numbers should be selected from the set {1, 5, 9, 13, …125} to be assured that two of the numbers selected have a sum of 146? Aug 20 answered Every simple graph with no loops and more than one vertex has at least 2 vertices of the same degree. May 28 awarded Notable Question May 9 awarded Notable Question Jan 25 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 Jan 17 comment Would there be no input or input does not exist? Unfortunately, the same symbol is used. See here for a definition.