Isomorphisms between random graphs

Abstract: Consider two independent ErdH{o}s-R'enyi

G (N, 1 / 2)

graphs. We show that with probability tending to

1

as

N o i n f t y

, the largest induced isomorphic subgraph has size either

l f l o o r x_{N} - v a r e p s i l o n_{N} f l o o r

or

l f l o o r x_{N} + v a r e p s i l o n_{N} f l o o r

, where

x_{N} = 4 l o g_{2} N - 2 l o g_{2} l o g_{2} N - 2 l o g_{2} (4 / e) + 1

and

v a r e p s i l o n_{N} = (4 l o g_{2} N)^{- 1 / 2}

. Using similar techniques, we also show that if

G a m m a_{1}

and

G a m m a_{2}

are independent

G (n, 1 / 2)

and

G (N, 1 / 2)

random graphs, then

G a m m a_{2}

contains an isomorphic copy of

G a m m a_{1}

as an induced subgraph with high probability if

n l e l f l o o r y_{N} - v a r e p s i l o n_{N} f l o o r

and does not contain an isomorphic copy of

G a m m a_{1}

as an induced subgraph with high probability if

n > l f l o o r y_{N} + v a r e p s i l o n_{N} f l o o r

, where

y_{N} = 2 l o g_{2} N + 1

and

v a r e p s i l o n_{N}

is as above.

This page was built for publication: Isomorphisms between random graphs