Multigraphs (only) satisfy a weak triangle removal lemma
| dc.creator | Shapira, Asaf | |
| dc.creator | Yuster, Raphael | |
| dc.date | 2009-02-03 | |
| dc.date.accessioned | 2026-07-07T12:37:21Z | |
| dc.date.available | 2026-07-07T12:37:21Z | |
| dc.description | The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can be extended to multi-graphs (or equivalently, weighted graphs). In this short paper we rule out the possibility of such an extension by showing that there are multi-graphs with only n^{2+o(1)} triangles that are still far from being triangle-free. On the other hand, we show that for some g(n)=ω(1), if a multi-graph (or weighted graph) has only g(n)n^2 triangles then it must be close to being triangle-free. The proof relies on variants of the Ruzsa-Szemerédi theorem. | |
| dc.identifier | https://arxiv.org/abs/0902.0580 | |
| dc.identifier | http://arxiv.org/abs/0902.0580 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/218411 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D99 | |
| dc.title | Multigraphs (only) satisfy a weak triangle removal lemma | |
| dc.type | text |