Disjoint isomorphic balanced clique subdivisions

Abstract: A thoroughly studied problem in Extremal Graph Theory is to find the best possible density condition in a host graph

G

for guaranteeing the presence of a particular subgraph

H

in

G

. One such classical result, due to Bollob'{a}s and Thomason, and independently Koml'{o}s and Szemer'{e}di, states that average degree

O (k^{2})

guarantees the existence of a

K_{k}

-subdivision. We study two directions extending this result. On the one hand, Verstra"ete conjectured that the quadratic bound

O (k^{2})

would guarantee already two vertex-disjoint isomorphic copies of a

K_{k}

-subdivision. On the other hand, Thomassen conjectured that for each

k i n m a t h b b N

there is some

d = d (k)

such that every graph with average degree at least

d

contains a balanced subdivision of

K_{k}

, that is, a copy of

K_{k}

where the edges are replaced by paths of equal length. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on

d (k)

remains open. In this paper, we show that the quadratic bound

O (k^{2})

suffices to force a balanced

K_{k}

-subdivision. This gives the optimal bound on

d (k)

needed in Thomassen's conjecture and implies the existence of

O (1)

many vertex-disjoint isomorphic

K_{k}

-subdivisions, confirming Verstra"ete's conjecture in a strong sense.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Disjoint isomorphic balanced clique subdivisions