The density Turán problem

Publication date 4 September 2012

Abstract: Let

H

be a graph on

n

vertices and let the blow-up graph

G [H]

be defined as follows. We replace each vertex

v_{i}

of

H

by a cluster

A_{i}

and connect some pairs of vertices of

A_{i}

and

A_{j}

if

(v_{i}, v_{j})

was an edge of the graph

H

. As usual, we define the edge density between

A_{i}

and

A_{j}

as

d (A_{i}, A_{j}) = f r a c e (A_{i}, A_{j}) | A_{i} | | A_{j} | .

We study the following problem. Given densities

g a m m a_{i j}

for each edge

(i, j) i n E (H)

. Then one has to decide whether there exists a blow-up graph

G [H]

with edge densities at least

g a m m a_{i j}

such that one cannot choose a vertex from each cluster so that the obtained graph is isomorphic to

H

, i.e, no

H

appears as a transversal in

G [H]

. We call

d_{c r i t} (H)

the maximal value for which there exists a blow-up graph

G [H]

with edge densities

d (A_{i}, A_{j}) = d_{c r i t} (H)

((v_{i}, v_{j}) i n E (H))

not containing

H

in the above sense. Our main goal is to determine the critical edge density and to characterize the extremal graphs.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: The density Turán problem