Re:Elegant six-page proof reveals the emergence of random st...
by layer8 on Monday April 25, 2022 @09:35PM
(#31163022)
Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?
[ Parent
| on HN ]
Re:Elegant six-page proof reveals the emergence of random st...
by nawgz on Monday April 25, 2022 @09:46PM
(#31163079)
It seems to me most graph problems that people care about are monotonic under adding edges. Actually, I can't think of a single problem in graph theory I've done where that wouldn't hold.
Re:Elegant six-page proof reveals the emergence of random st...
by cevi on Monday April 25, 2022 @09:58PM
(#31163160)
Being a https://en.wikipedia.org/wiki/Perfect_graph is not monotonic under adding edges, and it's certainly an interesting property for a graph to have! (But yes, most interesting properties are monotonic under adding edges)
Re:Elegant six-page proof reveals the emergence of random st...
by thaumasiotes on Monday April 25, 2022 @10:44PM
(#31163426)
> It seems to me most graph problems that people care about are monotonic under adding edges. Actually, I can't think of a single problem in graph theory I've done where that wouldn't hold.
https://en.wikipedia.org/wiki/Braess%27s_paradox is very famous.
Re:Elegant six-page proof reveals the emergence of random st...
by thomasahle on Monday April 25, 2022 @10:43PM
(#31163423)
You are right! Luckily that's the definition of a graph property .
Something that definitely won't work: The parity of the number of edges.
Still, it's pretty general.