The minimum degree removal lemma thresholds

Abstract: The graph removal lemma is a fundamental result in extremal graph theory which says that for every fixed graph

H

and

v a r e p s i l o n > 0

, if an

n

-vertex graph

G

contains

v a r e p s i l o n n^{2}

edge-disjoint copies of

H

then

G

contains

d e l t a n^{v (H)}

copies of

H

for some

d e l t a = d e l t a (v a r e p s i l o n, H) > 0

. The current proofs of the removal lemma give only very weak bounds on

d e l t a (v a r e p s i l o n, H)

, and it is also known that

d e l t a (v a r e p s i l o n, H)

is not polynomial in

v a r e p s i l o n

unless

H

is bipartite. Recently, Fox and Wigderson initiated the study of minimum degree conditions guaranteeing that

d e l t a (v a r e p s i l o n, H)

depends polynomially or linearly on

v a r e p s i l o n

. In this paper we answer several questions of Fox and Wigderson on this topic.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: The minimum degree removal lemma thresholds