New answers tagged

3

It at least doesn't work out that for every maximum independent set there is a 3-coloring of the graph which 2-colors the independent set. Here is a counterexample to that stronger version of your question: The circles represent vertices. You can also easily check that the graph is 3-regular and isn't $K_4$. Open circles define the maximum independent set ...


3

He doesn't cite any references for it and Google doesn't return any results so I don't think he is really quoting from anywhere. The idea that a proof is a "construction" (a term in intuitionistic/constructive mathematics with a very close meaning to what we call algorithm nowadays) goes back to at least Luitzen Egbertus Jan Brouwer. Note that Brouwer ...


6

You're missing the (obvious but) unstated caveat of "with high probability", I think. If you're hashing randomly, there's some chance all items choose the same two buckets. With high probability, you can get constant load. I think I recall this was first shown to me by Alan Frieze, but I can't recall the reference. Cuckoo hashing provides another way of ...


1

Try Google scholar search for "cuckoo hashing" or https://en.wikipedia.org/wiki/Cuckoo_hashing — that is, the answer to your question is the subject you say you are already reading. Cuckoo hashing is exactly the technique for moving elements to achieve constant load. If you do all the insertions and moves before you do any queries, you get an offline ...



Top 50 recent answers are included