Timeline for Deleting triangles in a graph
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 23, 2021 at 0:59 | history | bounty ended | Isky Mathews | ||
| S Sep 23, 2021 at 0:59 | history | notice removed | Isky Mathews | ||
| Sep 16, 2021 at 18:30 | vote | accept | Hauke Reddmann | ||
| Sep 16, 2021 at 0:35 | comment | added | Isky Mathews | Having put a bounty on this question, I would be primarily interested in bounds (for the number of edges needed to remove triangles) related closely in some sense to the number of edges, for example related to the maximum degree or the chromatic number or the Cheeger constant. | |
| Sep 15, 2021 at 23:49 | answer | added | Tony Huynh | timeline score: 3 | |
| Sep 15, 2021 at 22:40 | comment | added | Wojowu | Here are some results which should be of interest: 1. The triangle removal lemma, which asserts that if a graph on $n$ vertices has $o(n^3)$ vertices, then those can be removed by deleting $o(n^2)$ edges. 2. By Turan's theorem, a triangle-free graph can have at most $\sim n^2/4$ edges. So starting with a complete graph, you need to remove at least $\sim n^2/4$ edges to remove all triangles. I'm not sure about the NP question, since I don't know what decision problem you have here. | |
| S Sep 15, 2021 at 22:26 | history | bounty started | Isky Mathews | ||
| S Sep 15, 2021 at 22:26 | history | notice added | Isky Mathews | Authoritative reference needed | |
| Oct 5, 2020 at 15:01 | comment | added | Hauke Reddmann | Yes, there should be a bijection (for the variant question). (The graphs I deal with don't have O(n^2) size, but rather O(n*log(n)) - the question is a spinoff of binary search - , so I expect such a bijection to exist.) | |
| Oct 5, 2020 at 13:40 | comment | added | Ray Butterworth | Is this equivalent to: 1) find the set of all triangles; 2) find a set of edges, exactly one from each triangle? | |
| Oct 5, 2020 at 9:48 | history | asked | Hauke Reddmann | CC BY-SA 4.0 |