Dömötör Pálvölgyi
59 followers
59 followers
Posts
Post has attachment
And this time, let me recommend from cstheory.SE a problem that imho should be instead on Mathoverflow:

https://cstheory.stackexchange.com/questions/36979/bipartite-matching-with-degree-domination

It asks whether in every bipartite graph there is a matching where every unmatched vertex "accepts its fate" because each of its matched neighbors has a strictly larger degree. Such a natural condition!
Post has attachment
Here's another recommendation from Mathoverflow:

https://mathoverflow.net/questions/281573/variant-of-graph-coloring

It is well-known that finding a minimum s-t cut in a graph can be solved in polynomial time. But what happens if instead of s and t, our input has three vertices, t1, t2, t3, and out goal is to find a three-partition of the vertices with the minimum number of edges that go between the parts? This question is equivalent to (the first interesting case of) the above question.
Post has attachment
In case you're on MO, you must have seen this question as it has a bounty, but if not, here you go:

https://mathoverflow.net/questions/278397/probability-of-good-colorings-in-randomly-colored-graphs

The definitions are a little long, so it wouldn't make much point to repeat them here, but from the title you can guess what it's about. Quite surprising that no one could prove a better bound on r.
Post has attachment
This is the second edition of recommended by dom from MO. What's so surprising here is that even the simplest versions of the question are wide open. Can we get an O(1)-coloring for any dimension with bounded monochromatic components in the square of the k-dim grid graph or do even k-colorings always contain a large monochromatic component?

https://mathoverflow.net/questions/52825/coloring-mathbb-zk
Post has attachment
MO: A discrete version of Lebesgue's density theorem

I've realized that instead of clogging my browser's bookmarks with recent Mathoverflow questions I find nice and can't solve, it's better to instead clog my g+ feed with them! So here is our very first edition of "recommended by dom" from MO:

https://mathoverflow.net/questions/278548/finding-a-semi-sparse-vertex-in-a-grid

Feel free to leave here witty remarks that would be inappropriate on MO!
Post has attachment