Skip to main content
added 16 characters in body
Source Link
GMB
  • 1.4k
  • 9
  • 17

The Triangle Removal Lemma states:

For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by removing at most $\epsilon n^2$ edges.

(This is a special case of the more general Graph Removal Lemma -- see here for a survey.)

There has been a lot of interesting work optimizing the tradeoff between $\epsilon$ and $\delta$ in this lemma. I am wondering if the relationship between the exponents has been studied. For example, is it known if any graph on $\delta n^{2.9}$ triangles may be made triangle-free by removing at most $\epsilon n^{1.9}$ edges?

The Triangle Removal Lemma states:

For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph with at most $\delta n^3$ triangles may be made triangle-free by removing at most $\epsilon n^2$ edges.

(This is a special case of the more general Graph Removal Lemma -- see here for a survey.)

There has been a lot of interesting work optimizing the tradeoff between $\epsilon$ and $\delta$ in this lemma. I am wondering if the relationship between the exponents has been studied. For example, is it known if any graph on $\delta n^{2.9}$ triangles may be made triangle-free by removing at most $\epsilon n^{1.9}$ edges?

The Triangle Removal Lemma states:

For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by removing at most $\epsilon n^2$ edges.

(This is a special case of the more general Graph Removal Lemma -- see here for a survey.)

There has been a lot of interesting work optimizing the tradeoff between $\epsilon$ and $\delta$ in this lemma. I am wondering if the relationship between the exponents has been studied. For example, is it known if any graph on $\delta n^{2.9}$ triangles may be made triangle-free by removing at most $\epsilon n^{1.9}$ edges?

Source Link
GMB
  • 1.4k
  • 9
  • 17

Generalizations of the Triangle Removal Lemma to smaller exponents

The Triangle Removal Lemma states:

For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph with at most $\delta n^3$ triangles may be made triangle-free by removing at most $\epsilon n^2$ edges.

(This is a special case of the more general Graph Removal Lemma -- see here for a survey.)

There has been a lot of interesting work optimizing the tradeoff between $\epsilon$ and $\delta$ in this lemma. I am wondering if the relationship between the exponents has been studied. For example, is it known if any graph on $\delta n^{2.9}$ triangles may be made triangle-free by removing at most $\epsilon n^{1.9}$ edges?